| 2009 | Homology flows, cohomology cuts. | Erin W. Chambers, Jeff Erickson, Amir Nayyeri |
| 2009 | Every planar graph is the intersection graph of segments in the plane: extended abstract. | Jrmie Chalopin, Daniel Gonalves |
| 2009 | A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. | Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara |
| 2009 | An efficient algorithm for partial order production. | Jean Cardinal, Samuel Fiorini, Gwenal Joret, Raphal M. Jungers, J. Ian Munro |
| 2009 | Holant problems and counting CSP. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2009 | Testing juntas nearly optimally. | Eric Blais |
| 2009 | A nearly optimal oracle for avoiding failed vertices and edges. | Aaron Bernstein, David R. Karger |
| 2009 | Affine dispersers from subspace polynomials. | Eli Ben-Sasson, Swastik Kopparty |
| 2009 | Twice-ramanujan sparsifiers. | Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava |
| 2009 | MaxMin allocation via degree lower-bounded arborescences. | MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami |
| 2009 | Distributed (delta+1)-coloring in linear (in delta) time. | Leonid Barenboim, Michael Elkin |
| 2009 | Polynomial-time theory of matrix groups. | Lszl Babai, Robert Beals, kos Seress |
| 2009 | Multiple intents re-ranking. | Yossi Azar, Iftah Gamzu, Xiaoxin Yin |
| 2009 | Randomly supported independence and resistance. | Per Austrin, Johan Hstad |
| 2009 | Message passing algorithms and improved LP decoding. | Sanjeev Arora, Constantinos Daskalakis, David Steurer |
| 2009 | Small-size epsilon-nets for axis-parallel rectangles and boxes. | Boris Aronov, Esther Ezra, Micha Sharir |
| 2009 | Approximating edit distance in near-linear time. | Alexandr Andoni, Krzysztof Onak |
| 2009 | Finding sparse cuts locally using evolving sets. | Reid Andersen, Yuval Peres |
| 2009 | The detectability lemma and quantum gap amplification. | Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani |
| 2008 | Optimal approximation for the submodular welfare problem in the value oracle model. | Jan Vondrk |
| 2008 | Testing symmetric properties of distributions. | Paul Valiant |
| 2008 | Fast polynomial factorization and modular composition in small characteristic. | Christopher Umans |
| 2008 | Minimum k-way cuts via deterministic greedy tree packing. | Mikkel Thorup |
| 2008 | Graph sparsification by effective resistances. | Daniel A. Spielman, Nikhil Srivastava |
| 2008 | Inapproximability of pure nash equilibria. | Alexander Skopalik, Berthold Vcking |