| 2010 | On the structure of cubic and quartic polynomials. | Elad Haramaty, Amir Shpilka |
| 2010 | Efficiency improvements in constructing pseudorandom generators from one-way functions. | Iftach Haitner, Omer Reingold, Salil P. Vadhan |
| 2010 | On the list-decodability of random linear codes. | Venkatesan Guruswami, Johan Hstad, Swastik Kopparty |
| 2010 | On the round complexity of covert computation. | Vipul Goyal, Abhishek Jain |
| 2010 | Perfect matchings in o( | Ashish Goel, Michael Kapralov, Sanjeev Khanna |
| 2010 | The HOM problem is decidable. | Guillem Godoy, Omer Gimnez, Lander Ramos, Carme lvarez |
| 2010 | Approximate sparse recovery: optimizing time and measurements. | Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss |
| 2010 | Load balancing and orientability thresholds for random hypergraphs. | Pu Gao, Nicholas C. Wormald |
| 2010 | An optimal ancestry scheme and small universal posets. | Pierre Fraigniaud, Amos Korman |
| 2010 | On the searchability of small-world networks with arbitrary underlying structure. | Pierre Fraigniaud, George Giakkoupis |
| 2010 | On the complexity of #CSP. | Martin E. Dyer, David Richerby |
| 2010 | Differential privacy under continual observation. | Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum |
| 2010 | Connectivity oracles for failure prone graphs. | Ran Duan, Seth Pettie |
| 2010 | Changing base without losing space. | Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup |
| 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 | Optimal homologous cycles, total unimodularity, and linear programming. | Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy |
| 2010 | Near-optimal extractors against quantum storage. | Anindya De, Thomas Vidick |
| 2010 | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. | Holger Dell, Dieter van Melkebeek |
| 2010 | A sparse Johnson: Lindenstrauss transform. | Anirban Dasgupta, Ravi Kumar, Tams Sarls |
| 2010 | Almost tight bounds for rumour spreading with conductance. | Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi |
| 2010 | Multi-parameter mechanism design and sequential posted pricing. | Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan |
| 2010 | Privacy amplification with asymptotically optimal entropy loss. | Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin |
| 2010 | Sorting under partial information (without the ellipsoid algorithm). | Jean Cardinal, Samuel Fiorini, Gwenal Joret, Raphal M. Jungers, J. Ian Munro |
| 2010 | An improved LP-based approximation for steiner tree. | Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvo, Laura Sanit |
| 2010 | Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem. | Peter Brgisser, Felipe Cucker |