| 2013 | How robust are linear sketches to adaptive inputs? | Moritz Hardt, David P. Woodruff |
| 2013 | Beyond worst-case analysis in private singular vector computation. | Moritz Hardt, Aaron Roth |
| 2013 | Net and prune: a linear time algorithm for euclidean distance problems. | Sariel Har-Peled, Benjamin Adam Raichel |
| 2013 | List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. | Venkatesan Guruswami, Chaoping Xing |
| 2013 | Sparsest cut on bounded treewidth graphs: algorithms and hardness results. | Anupam Gupta, Kunal Talwar, David Witmer |
| 2013 | The power of deferral: maintaining a constant-competitive steiner tree online. | Albert Gu, Anupam Gupta, Amit Kumar |
| 2013 | Non-black-box simulation in the fully concurrent setting. | Vipul Goyal |
| 2013 | Attribute-based encryption for circuits. | Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee |
| 2013 | Reusable garbled circuits and succinct functional encryption. | Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich |
| 2013 | Witness encryption and its applications. | Sanjam Garg, Craig Gentry, Amit Sahai, Brent Waters |
| 2013 | Statistical algorithms and a lower bound for detecting planted cliques. | Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao |
| 2013 | Combinatorial walrasian equilibrium. | Michal Feldman, Nick Gravin, Brendan Lucier |
| 2013 | Simultaneous auctions are (almost) efficient. | Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier |
| 2013 | Optimal euclidean spanners: really short, thin and lanky. | Michael Elkin, Shay Solomon |
| 2013 | Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. | David Eisenstat, Philip N. Klein |
| 2013 | Majority is stablest: discrete and SoS. | Anindya De, Elchanan Mossel, Joe Neeman |
| 2013 | Fast hamiltonicity checking via bases of perfect matchings. | Marek Cygan, Stefan Kratsch, Jesper Nederlof |
| 2013 | Going after the k-SAT threshold. | Amin Coja-Oghlan, Konstantinos Panagiotou |
| 2013 | Low rank approximation and regression in input sparsity time. | Kenneth L. Clarkson, David P. Woodruff |
| 2013 | Non-black-box simulation from one-way functions and applications to resettable security. | Kai-Min Chung, Rafael Pass, Karn Seth |
| 2013 | The orbit problem in higher dimensions. | Ventsislav Chonev, Jol Ouaknine, James Worrell |
| 2013 | Tatonnement beyond gross substitutes?: gradient descent to the rescue. | Yun Kuen Cheung, Richard Cole, Nikhil R. Devanur |
| 2013 | Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. | Xi Chen, Xiaorui Sun, Shang-Hua Teng |
| 2013 | The complexity of non-monotone markets. | Xi Chen, Dimitris Paparas, Mihalis Yannakakis |
| 2013 | Large-treewidth graph decompositions and applications. | Chandra Chekuri, Julia Chuzhoy |