| 2013 | Efficient rounding for the noncommutative grothendieck inequality. | Assaf Naor, Oded Regev, Thomas Vidick |
| 2013 | Solving large optimization problems using spectral graph theory. | Gary L. Miller |
| 2013 | Shielding circuits with groups. | Eric Miles, Emanuele Viola |
| 2013 | Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. | Xiangrui Meng, Michael W. Mahoney |
| 2013 | Multidimensional approximate agreement in Byzantine asynchronous systems. | Hammurabi Mendes, Maurice Herlihy |
| 2013 | Stochastic combinatorial optimization via poisson approximation. | Jian Li, Wen Yuan |
| 2013 | Approximating k-median via pseudo-approximation. | Shi Li, Ola Svensson |
| 2013 | New independent source extractors with exponential improvement. | Xin Li |
| 2013 | Fast routing table construction using small messages: extended abstract. | Christoph Lenzen, Boaz Patt-Shamir |
| 2013 | A new approach to computing maximum flows using electrical flows. | Yin Tat Lee, Satish Rao, Nikhil Srivastava |
| 2013 | A node-capacitated okamura-seymour theorem. | James R. Lee, Manor Mendel, Mohammad Moharrami |
| 2013 | Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. | Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan |
| 2013 | Average-case lower bounds for formula size. | Ilan Komargodski, Ran Raz |
| 2013 | Interactive channel capacity. | Gillat Kol, Ran Raz |
| 2013 | Structured recursive separator decompositions for planar graphs in linear time. | Philip N. Klein, Shay Mozes, Christian Sommer |
| 2013 | Byzantine agreement in polynomial expected time: [extended abstract]. | Valerie King, Jared Saia |
| 2013 | A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. | Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu |
| 2013 | Polynomial-time perfect matchings in dense hypergraphs. | Peter Keevash, Fiachra Knox, Richard Mycroft |
| 2013 | Testing subdivision-freeness: property testing meets structural graph theory. | Ken-ichi Kawarabayashi, Yuichi Yoshida |
| 2013 | A PRG for lipschitz functions of polynomials with applications to sparsest cut. | Daniel M. Kane, Raghu Meka |
| 2013 | Delegation for bounded space. | Yael Tauman Kalai, Ran Raz, Ron D. Rothblum |
| 2013 | Low-rank matrix completion using alternating minimization. | Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi |
| 2013 | Approximation resistance on satisfiable instances for predicates with few accepting inputs. | Sangxia Huang |
| 2013 | Differential privacy for the analyst via private equilibrium computation. | Justin Hsu, Aaron Roth, Jonathan R. Ullman |
| 2013 | Constraint satisfaction, packet routing, and the lovasz local lemma. | David G. Harris, Aravind Srinivasan |