| 2013 | A PRG for lipschitz functions of polynomials with applications to sparsest cut. Daniel M. Kane, Raghu Meka |
| 2013 | A complete dichotomy rises from the capture of vanishing signatures: extended abstract. Jin-Yi Cai, Heng Guo, Tyson Williams |
| 2013 | A new approach to computing maximum flows using electrical flows. Yin Tat Lee, Satish Rao, Nikhil Srivastava |
| 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 | A node-capacitated okamura-seymour theorem. James R. Lee, Manor Mendel, Mohammad Moharrami |
| 2013 | A o(n) monotonicity tester for boolean functions over the hypercube. Deeparnab Chakrabarty, C. Seshadhri |
| 2013 | A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu |
| 2013 | An information complexity approach to extended formulations. Mark Braverman, Ankur Moitra |
| 2013 | Answering n Jonathan R. Ullman |
| 2013 | Approximating k-median via pseudo-approximation. Shi Li, Ola Svensson |
| 2013 | Approximation resistance from pairwise independent subgroups. Siu On Chan |
| 2013 | Approximation resistance on satisfiable instances for predicates with few accepting inputs. Sangxia Huang |
| 2013 | Attribute-based encryption for circuits. Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee |
| 2013 | Average-case lower bounds for formula size. Ilan Komargodski, Ran Raz |
| 2013 | Beyond worst-case analysis in private singular vector computation. Moritz Hardt, Aaron Roth |
| 2013 | Bottom-k and priority sampling, set similarity and subset sums with minimal independence. Mikkel Thorup |
| 2013 | Byzantine agreement in polynomial expected time: [extended abstract]. Valerie King, Jared Saia |
| 2013 | Classical hardness of learning with errors. Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé |
| 2013 | Coevolutionary opinion formation games. Kshipra Bhawalkar, Sreenivas Gollapudi, Kamesh Munagala |
| 2013 | Combinatorial walrasian equilibrium. Michal Feldman, Nick Gravin, Brendan Lucier |
| 2013 | Communication lower bounds using directional derivatives. Alexander A. Sherstov |
| 2013 | Composable and efficient mechanisms. Vasilis Syrgkanis, Éva Tardos |
| 2013 | Constraint satisfaction, packet routing, and the lovasz local lemma. David G. Harris, Aravind Srinivasan |
| 2013 | Delegation for bounded space. Yael Tauman Kalai, Ran Raz, Ron D. Rothblum |
| 2013 | Differential privacy for the analyst via private equilibrium computation. Justin Hsu, Aaron Roth, Jonathan R. Ullman |
| 2013 | Efficient rounding for the noncommutative grothendieck inequality. Assaf Naor, Oded Regev, Thomas Vidick |
| 2013 | Equivalence of deterministic one-counter automata is NL-complete. Stanislav Böhm, Stefan Göller, Petr Jancar |
| 2013 | Every locally characterized affine-invariant property is testable. Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett |
| 2013 | Explicit lower bounds via geometric complexity theory. Peter Bürgisser, Christian Ikenmeyer |
| 2013 | Extending continuous maps: polynomiality and undecidability. Martin Cadek, Marek Krcál, Jirí Matousek, Lukás Vokrínek, Uli Wagner |
| 2013 | Fast approximation algorithms for the diameter and radius of sparse graphs. Liam Roditty, Virginia Vassilevska Williams |
| 2013 | Fast hamiltonicity checking via bases of perfect matchings. Marek Cygan, Stefan Kratsch, Jesper Nederlof |
| 2013 | Fast routing table construction using small messages: extended abstract. Christoph Lenzen, Boaz Patt-Shamir |
| 2013 | From information to exact communication. Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein |
| 2013 | Going after the k-SAT threshold. Amin Coja-Oghlan, Konstantinos Panagiotou |
| 2013 | Homomorphic fingerprints under misalignments: sketching edit and shift distances. Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat |
| 2013 | How robust are linear sketches to adaptive inputs? Moritz Hardt, David P. Woodruff |
| 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 | Interactive channel capacity. Gillat Kol, Ran Raz |
| 2013 | Interactive proofs of proximity: delegating computation in sublinear time. Guy N. Rothblum, Salil P. Vadhan, Avi Wigderson |
| 2013 | Inverting well conditioned matrices in quantum logspace. Amnon Ta-Shma |
| 2013 | Large-treewidth graph decompositions and applications. Chandra Chekuri, Julia Chuzhoy |
| 2013 | Lee-Yang theorems and the complexity of computing averages. Alistair Sinclair, Piyush Srivastava |
| 2013 | Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. David Eisenstat, Philip N. Klein |
| 2013 | List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. Venkatesan Guruswami, Chaoping Xing |
| 2013 | Low rank approximation and regression in input sparsity time. Kenneth L. Clarkson, David P. Woodruff |
| 2013 | Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. Xiangrui Meng, Michael W. Mahoney |
| 2013 | Low-rank matrix completion using alternating minimization. Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi |
| 2013 | Lower bounds for RAMs and quantifier elimination. Miklós Ajtai |
| 2013 | Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]. Aaron Bernstein |
| 2013 | Majority is stablest: discrete and SoS. Anindya De, Elchanan Mossel, Joe Neeman |
| 2013 | Max flows in O(nm) time, or better. James B. Orlin |
| 2013 | Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. Xi Chen, Xiaorui Sun, Shang-Hua Teng |
| 2013 | Multidimensional approximate agreement in Byzantine asynchronous systems. Hammurabi Mendes, Maurice Herlihy |
| 2013 | Natural proofs versus derandomization. Ryan Williams |
| 2013 | Net and prune: a linear time algorithm for euclidean distance problems. Sariel Har-Peled, Benjamin Adam Raichel |
| 2013 | New bounds for matching vector families. Abhishek Bhowmick, Zeev Dvir, Shachar Lovett |
| 2013 | New independent source extractors with exponential improvement. Xin Li |
| 2013 | Non-black-box simulation from one-way functions and applications to resettable security. Kai-Min Chung, Rafael Pass, Karn Seth |
| 2013 | Non-black-box simulation in the fully concurrent setting. Vipul Goyal |
| 2013 | On the complexity of trial and error. Xiaohui Bei, Ning Chen, Shengyu Zhang |
| 2013 | On the concrete efficiency of probabilistically-checkable proofs. Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer |
| 2013 | On the impossibility of approximate obfuscation and applications to resettable cryptography. Nir Bitansky, Omer Paneth |
| 2013 | On the list decodability of random linear codes with large error rates. Mary Wootters |
| 2013 | Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. Deeparnab Chakrabarty, C. Seshadhri |
| 2013 | Optimal euclidean spanners: really short, thin and lanky. Michael Elkin, Shay Solomon |
| 2013 | Polynomial-time perfect matchings in dense hypergraphs. Peter Keevash, Fiachra Knox, Richard Mycroft |
| 2013 | Prior-independent mechanisms for scheduling. Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan |
| 2013 | Product-state approximations to quantum ground states. Fernando G. S. L. Brandão, Aram W. Harrow |
| 2013 | Quantum de finetti theorems under local measurements with applications. Fernando G. S. L. Brandão, Aram W. Harrow |
| 2013 | Quasi-polynomial hitting-set for set-depth-Δ formulas. Manindra Agrawal, Chandan Saha, Nitin Saxena |
| 2013 | Quasipolynomial-time canonical form for steiner designs. László Babai, John Wilmes |
| 2013 | Random lattice triangulations: structure and algorithms. Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer |
| 2013 | Recursive composition and bootstrapping for SNARKS and proof-carrying data. Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer |
| 2013 | Reusable garbled circuits and succinct functional encryption. Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich |
| 2013 | Shielding circuits with groups. Eric Miles, Emanuele Viola |
| 2013 | Simple deterministic algorithms for fully dynamic maximal matching. Ofer Neiman, Shay Solomon |
| 2013 | Simplex partitioning via exponential clocks and the multiway cut problem. Niv Buchbinder, Joseph Naor, Roy Schwartz |
| 2013 | Simultaneous auctions are (almost) efficient. Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier |
| 2013 | Solving large optimization problems using spectral graph theory. Gary L. Miller |
| 2013 | Some trade-off results for polynomial calculus: extended abstract. Chris Beck, Jakob Nordström, Bangsheng Tang |
| 2013 | Sparsest cut on bounded treewidth graphs: algorithms and hardness results. Anupam Gupta, Kunal Talwar, David Witmer |
| 2013 | Sparsity lower bounds for dimensionality reducing maps. Jelani Nelson, Huy L. Nguyen |
| 2013 | Statistical algorithms and a lower bound for detecting planted cliques. Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao |
| 2013 | Stochastic combinatorial optimization via poisson approximation. Jian Li, Wen Yuan |
| 2013 | Strong ETH holds for regular resolution. Christopher Beck, Russell Impagliazzo |
| 2013 | Structured recursive separator decompositions for planar graphs in linear time. Philip N. Klein, Shay Mozes, Christian Sommer |
| 2013 | Succinct sampling from discrete distributions. Karl Bringmann, Kasper Green Larsen |
| 2013 | Superlinear advantage for exact quantum algorithms. Andris Ambainis |
| 2013 | Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 Dan Boneh, Tim Roughgarden, Joan Feigenbaum |
| 2013 | Tatonnement beyond gross substitutes?: gradient descent to the rescue. Yun Kuen Cheung, Richard Cole, Nikhil R. Devanur |
| 2013 | Testing subdivision-freeness: property testing meets structural graph theory. Ken-ichi Kawarabayashi, Yuichi Yoshida |
| 2013 | The approximate rank of a matrix and its algorithmic applications: approximate rank. Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala |
| 2013 | The complexity of finite-valued CSPs. Johan Thapper, Stanislav Zivný |
| 2013 | The complexity of non-monotone markets. Xi Chen, Dimitris Paparas, Mihalis Yannakakis |
| 2013 | The geometry of differential privacy: the sparse and approximate cases. Aleksandar Nikolov, Kunal Talwar, Li Zhang |
| 2013 | The loss of serving in the dark. Yossi Azar, Ilan Reuven Cohen, Iftah Gamzu |
| 2013 | The orbit problem in higher dimensions. Ventsislav Chonev, Joël Ouaknine, James Worrell |
| 2013 | The power of deferral: maintaining a constant-competitive steiner tree online. Albert Gu, Anupam Gupta, Amit Kumar |
| 2013 | Tight bounds for online vector bin packing. Yossi Azar, Ilan Reuven Cohen, Seny Kamara, F. Bruce Shepherd |
| 2013 | Witness encryption and its applications. Sanjam Garg, Craig Gentry, Amit Sahai, Brent Waters |