| 2008 | Stateless distributed gradient descent for positive linear programs. | Baruch Awerbuch, Rohit Khandekar |
| 2008 | Tight rmr lower bounds for mutual exclusion and other problems. | Hagit Attiya, Danny Hendler, Philipp Woelfel |
| 2008 | Unique games on expanding constraint graphs are easy: extended abstract. | Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2008 | Algebrization: a new barrier in complexity theory. | Scott Aaronson, Avi Wigderson |
| 2007 | Towards 3-query locally decodable codes of subexponential length. | Sergey Yekhanin |
| 2007 | Proportional response dynamics leads to market equilibrium. | Fang Wu, Li Zhang |
| 2007 | The condition number of a randomly perturbed matrix. | Van H. Vu, Terence Tao |
| 2007 | All-pairs bottleneck paths for general graphs in truly sub-cubic time. | Virginia Vassilevska, Ryan Williams, Raphael Yuster |
| 2007 | Balanced allocations: the weighted case. | Kunal Talwar, Udi Wieder |
| 2007 | Approximating minimum bounded degree spanning trees to within one of optimal. | Mohit Singh, Lap Chi Lau |
| 2007 | Interpolation of depth-3 arithmetic circuits with two multiplication gates. | Amir Shpilka |
| 2007 | Separating AC | Alexander A. Sherstov |
| 2007 | Low-end uniform hardness vs. randomness tradeoffs for AM. | Ronen Shaltiel, Christopher Umans |
| 2007 | Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. | Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
| 2007 | Circuit lower bounds for Merlin-Arthur classes. | Rahul Santhanam |
| 2007 | Low-degree tests at large distances. | Alex Samorodnitsky |
| 2007 | Property testing in hypergraphs and the removal lemma. | Vojtech Rdl, Mathias Schacht |
| 2007 | Lattices that admit logarithmic worst-case to average-case connection factors. | Chris Peikert, Alon Rosen |
| 2007 | Lower bounds for 2-dimensional range counting. | Mihai Patrascu |
| 2007 | An efficient parallel repetition theorem for Arthur-Merlin games. | Rafael Pass, Muthuramakrishnan Venkitasubramaniam |
| 2007 | Some new results on node-capacitated packing of A-paths. | Gyula Pap |
| 2007 | Linear probing with constant independence. | Anna Pagh, Rasmus Pagh, Milan Ruzic |
| 2007 | Smooth sensitivity and sampling in private data analysis. | Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith |
| 2007 | On the submodularity of influence in social networks. | Elchanan Mossel, Sbastien Roch |
| 2007 | On the impossibility of a quantum sieve algorithm for graph isomorphism. | Cristopher Moore, Alexander Russell, Piotr Sniady |