| 2013 | Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. | Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2013 | Estimating the Distance from Testable Affine-Invariant Properties. | Hamed Hatami, Shachar Lovett |
| 2013 | The Moser-Tardos Framework with Partial Resampling. | David G. Harris, Aravind Srinivasan |
| 2013 | Approximating Minimization Diagrams and Generalized Proximity Search. | Sariel Har-Peled, Nirman Kumar |
| 2013 | Online Node-Weighted Steiner Forest and Extensions via Disk Paintings. | Mohammad Taghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi |
| 2013 | Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. | Venkatesan Guruswami, Patrick Xia |
| 2013 | Explicit Subspace Designs. | Venkatesan Guruswami, Swastik Kopparty |
| 2013 | Fully Dynamic (1+ e)-Approximate Matchings. | Manoj Gupta, Richard Peng |
| 2013 | Quantum 3-SAT Is QMA1-Complete. | David Gosset, Daniel Nagaj |
| 2013 | Strong Backdoors to Bounded Treewidth SAT. | Serge Gaspers, Stefan Szeider |
| 2013 | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. | Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, Brent Waters |
| 2013 | Playing Non-linear Games with Linear Oracles. | Dan Garber, Elad Hazan |
| 2013 | Rational Protocol Design: Cryptography against Incentive-Driven Adversaries. | Juan A. Garay, Jonathan Katz, Ueli Maurer, Bjrn Tackmann, Vassilis Zikas |
| 2013 | Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors. | Harold N. Gabow, Piotr Sankowski |
| 2013 | Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. | Michael A. Forbes, Amir Shpilka |
| 2013 | Average Case Lower Bounds for Monotone Switching Networks. | Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook |
| 2013 | Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. | Vitaly Feldman, Jan Vondrk |
| 2013 | Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring. | Vida Dujmovic, Pat Morin, David R. Wood |
| 2013 | Local Privacy and Statistical Minimax Rates. | John C. Duchi, Michael I. Jordan, Martin J. Wainwright |
| 2013 | Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers. | Andrew Drucker |
| 2013 | PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring. | Irit Dinur, Venkatesan Guruswami |
| 2013 | Learning Sums of Independent Integer Random Variables. | Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
| 2013 | The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. | Marek Cygan, Dniel Marx, Marcin Pilipczuk, Michal Pilipczuk |
| 2013 | Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. | Marek Cygan |
| 2013 | Chasing the K-Colorability Threshold. | Amin Coja-Oghlan, Dan Vilenchik |