| 2010 | A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. Daniele Micciancio, Panagiotis Voulgaris |
| 2010 | A full characterization of quantum advice. Scott Aaronson, Andrew Drucker |
| 2010 | A quantum lovász local lemma. Andris Ambainis, Julia Kempe, Or Sattath |
| 2010 | A shorter proof of the graph minor algorithm: the unique linkage theorem. Ken-ichi Kawarabayashi, Paul Wollan |
| 2010 | A sparse Johnson: Lindenstrauss transform. Anirban Dasgupta, Ravi Kumar, Tamás Sarlós |
| 2010 | A strong direct product theorem for disjointness. Hartmut Klauck |
| 2010 | Almost tight bounds for rumour spreading with conductance. Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi |
| 2010 | An improved LP-based approximation for steiner tree. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità |
| 2010 | An invariance principle for polytopes. Prahladh Harsha, Adam R. Klivans, Raghu Meka |
| 2010 | An optimal ancestry scheme and small universal posets. Pierre Fraigniaud, Amos Korman |
| 2010 | Approximate sparse recovery: optimizing time and measurements. Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss |
| 2010 | Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx |
| 2010 | Approximations for the isoperimetric and spectral profile of graphs and related parameters. Prasad Raghavendra, David Steurer, Prasad Tetali |
| 2010 | Are many small sets explicitly small? Michel Talagrand |
| 2010 | Augmenting undirected node-connectivity by one. László A. Végh |
| 2010 | BQP and the polynomial hierarchy. Scott Aaronson |
| 2010 | Bayesian algorithmic mechanism design. Jason D. Hartline, Brendan Lucier |
| 2010 | Bilipschitz snowflakes and metrics of negative type. James R. Lee, Mohammad Moharrami |
| 2010 | Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan |
| 2010 | Budget constrained auctions with heterogeneous items. Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala |
| 2010 | Changing base without losing space. Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup |
| 2010 | Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Mohsen Bayati, David Gamarnik, Prasad Tetali |
| 2010 | Complexity theory for operators in analysis. Akitoshi Kawamura, Stephen A. Cook |
| 2010 | Conditional hardness of precedence constrained scheduling on identical machines. Ola Svensson |
| 2010 | Connectivity oracles for failure prone graphs. Ran Duan, Seth Pettie |
| 2010 | Detecting high log-densities: an Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan |
| 2010 | Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich |
| 2010 | Differential privacy under continual observation. Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum |
| 2010 | Distributed computation in dynamic networks. Fabian Kuhn, Nancy A. Lynch, Rotem Oshman |
| 2010 | Efficiency improvements in constructing pseudorandom generators from one-way functions. Iftach Haitner, Omer Reingold, Salil P. Vadhan |
| 2010 | Efficiently learning mixtures of two Gaussians. Adam Tauman Kalai, Ankur Moitra, Gregory Valiant |
| 2010 | Erratum for: on basing one-way functions on NP-hardness. Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz |
| 2010 | Extensions and limits to vertex sparsification. Frank Thomson Leighton, Ankur Moitra |
| 2010 | Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. Aleksander Madry |
| 2010 | Graph expansion and the unique games conjecture. Prasad Raghavendra, David Steurer |
| 2010 | Hardness amplification in proof complexity. Paul Beame, Trinh Huynh, Toniann Pitassi |
| 2010 | How to compress interactive communication. Boaz Barak, Mark Braverman, Xi Chen, Anup Rao |
| 2010 | Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices. James B. Orlin |
| 2010 | Improving exhaustive search implies superpolynomial lower bounds. Ryan Williams |
| 2010 | Interactive privacy via the median mechanism. Aaron Roth, Tim Roughgarden |
| 2010 | Load balancing and orientability thresholds for random hypergraphs. Pu Gao, Nicholas C. Wormald |
| 2010 | Local list-decoding and testing of random linear codes from high error. Swastik Kopparty, Shubhangi Saraf |
| 2010 | Maintaining a large matching and a small vertex cover. Krzysztof Onak, Ronitt Rubinfeld |
| 2010 | Matroid matching: the power of local search. Jon Lee, Maxim Sviridenko, Jan Vondrák |
| 2010 | Measuring independence of datasets. Vladimir Braverman, Rafail Ostrovsky |
| 2010 | Message passing algorithms: a success looking for theoreticians. Andrea Montanari |
| 2010 | Multi-parameter mechanism design and sequential posted pricing. Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan |
| 2010 | Near-optimal extractors against quantum storage. Anindya De, Thomas Vidick |
| 2010 | Non-commutative circuits and the sum-of-squares problem. Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
| 2010 | Oblivious RAMs without cryptogrpahic assumptions. Miklós Ajtai |
| 2010 | Odd cycle packing. Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2010 | On the complexity of #CSP. Martin E. Dyer, David Richerby |
| 2010 | On the complexity of circuit satisfiability. Ramamohan Paturi, Pavel Pudlák |
| 2010 | On the geometry of differential privacy. Moritz Hardt, Kunal Talwar |
| 2010 | On the hardness of the noncommutative determinant. Vikraman Arvind, Srikanth Srinivasan |
| 2010 | On the list-decodability of random linear codes. Venkatesan Guruswami, Johan Håstad, Swastik Kopparty |
| 2010 | On the round complexity of covert computation. Vipul Goyal, Abhishek Jain |
| 2010 | On the searchability of small-world networks with arbitrary underlying structure. Pierre Fraigniaud, George Giakkoupis |
| 2010 | On the structure of cubic and quartic polynomials. Elad Haramaty, Amir Shpilka |
| 2010 | Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Alexander A. Sherstov |
| 2010 | Optimal homologous cycles, total unimodularity, and linear programming. Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy |
| 2010 | Perfect matchings in o( Ashish Goel, Michael Kapralov, Sanjeev Khanna |
| 2010 | Privacy amplification with asymptotically optimal entropy loss. Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin |
| 2010 | Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 Leonard J. Schulman |
| 2010 | Pseudorandom generators for polynomial threshold functions. Raghu Meka, David Zuckerman |
| 2010 | Public-key cryptography from different assumptions. Benny Applebaum, Boaz Barak, Avi Wigderson |
| 2010 | QIP = PSPACE. Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous |
| 2010 | Recognizing well-parenthesized expressions in the streaming model. Frédéric Magniez, Claire Mathieu, Ashwin Nayak |
| 2010 | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Holger Dell, Dieter van Melkebeek |
| 2010 | Saving space by algebraization. Daniel Lokshtanov, Jesper Nederlof |
| 2010 | Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem. Peter Bürgisser, Felipe Cucker |
| 2010 | Sorting under partial information (without the ellipsoid algorithm). Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro |
| 2010 | Spectral methods for matrices and tensors. Ravindran Kannan |
| 2010 | Subgraph sparsification and nearly optimal ultrasparsifiers. Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng |
| 2010 | Tensor-rank and lower bounds for arithmetic formulas. Ran Raz |
| 2010 | The HOM problem is decidable. Guillem Godoy, Omer Giménez, Lander Ramos, Carme Àlvarez |
| 2010 | The limits of buffering: a tight lower bound for dynamic membership in the external memory model. Elad Verbin, Qin Zhang |
| 2010 | The maximum multiflow problems with bounded fractionality. Hiroshi Hirai |
| 2010 | The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith, Jonathan R. Ullman |
| 2010 | Towards polynomial lower bounds for dynamic problems. Mihai Patrascu |
| 2010 | Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Dániel Marx |
| 2010 | Weighted geometric set cover via quasi-uniform sampling. Kasturi R. Varadarajan |
| 2010 | Zero-one frequency laws. Vladimir Braverman, Rafail Ostrovsky |