| 2013 | Prior-independent mechanisms for scheduling. | Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan |
| 2013 | Approximation resistance from pairwise independent subgroups. | Siu On Chan |
| 2013 | Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. | Deeparnab Chakrabarty, C. Seshadhri |
| 2013 | A o(n) monotonicity tester for boolean functions over the hypercube. | Deeparnab Chakrabarty, C. Seshadhri |
| 2013 | Random lattice triangulations: structure and algorithms. | Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer |
| 2013 | A complete dichotomy rises from the capture of vanishing signatures: extended abstract. | Jin-Yi Cai, Heng Guo, Tyson Williams |
| 2013 | Extending continuous maps: polynomiality and undecidability. | Martin Cadek, Marek Krcl, Jir Matousek, Luks Vokrnek, Uli Wagner |
| 2013 | Explicit lower bounds via geometric complexity theory. | Peter Brgisser, Christian Ikenmeyer |
| 2013 | Simplex partitioning via exponential clocks and the multiway cut problem. | Niv Buchbinder, Joseph Naor, Roy Schwartz |
| 2013 | Succinct sampling from discrete distributions. | Karl Bringmann, Kasper Green Larsen |
| 2013 | An information complexity approach to extended formulations. | Mark Braverman, Ankur Moitra |
| 2013 | From information to exact communication. | Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein |
| 2013 | Product-state approximations to quantum ground states. | Fernando G. S. L. Brando, Aram W. Harrow |
| 2013 | Quantum de finetti theorems under local measurements with applications. | Fernando G. S. L. Brando, Aram W. Harrow |
| 2013 | Classical hardness of learning with errors. | Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehl |
| 2013 | Equivalence of deterministic one-counter automata is NL-complete. | Stanislav Bhm, Stefan Gller, Petr Jancar |
| 2013 | On the impossibility of approximate obfuscation and applications to resettable cryptography. | Nir Bitansky, Omer Paneth |
| 2013 | Recursive composition and bootstrapping for SNARKS and proof-carrying data. | Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer |
| 2013 | New bounds for matching vector families. | Abhishek Bhowmick, Zeev Dvir, Shachar Lovett |
| 2013 | Coevolutionary opinion formation games. | Kshipra Bhawalkar, Sreenivas Gollapudi, Kamesh Munagala |
| 2013 | Every locally characterized affine-invariant property is testable. | Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett |
| 2013 | Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]. | Aaron Bernstein |
| 2013 | A new family of locally correctable codes based on degree-lifted algebraic geometry codes. | Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf |
| 2013 | On the concrete efficiency of probabilistically-checkable proofs. | Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer |
| 2013 | On the complexity of trial and error. | Xiaohui Bei, Ning Chen, Shengyu Zhang |