| 2009 | Counting Subgraphs via Homomorphisms. | Omid Amini, Fedor V. Fomin, Saket Saurabh |
| 2009 | Bounds on the Size of Small Depth Circuits for Approximating Majority. | Kazuyuki Amano |
| 2009 | Fast FAST. | Noga Alon, Daniel Lokshtanov, Saket Saurabh |
| 2009 | Sorting and Selection with Imprecise Comparisons. | Mikls Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson |
| 2009 | Correlation Clustering Revisited: The "True" Cost of Error Minimization Problems. | Nir Ailon, Edo Liberty |
| 2009 | Graph Sparsification in the Semi-streaming Model. | Kook Jin Ahn, Sudipto Guha |
| 2009 | SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs. | Geir Agnarsson, Magns M. Halldrsson, Elena Losievskaja |
| 2009 | Deciding Safety Properties in Infinite-State Pi-Calculus via Behavioural Types. | Lucia Acciai, Michele Boreale |
| 2008 | Property Testing on k-Vertex-Connectivity of Graphs. | Yuichi Yoshida, Hiro Ito |
| 2008 | Reversible Flowchart Languages and the Structured Reversible Program Theorem. | Tetsuo Yokoyama, Holger Bock Axelsen, Robert Glck |
| 2008 | Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity. | Yitong Yin |
| 2008 | Composable Security in the Bounded-Quantum-Storage Model. | Stephanie Wehner, Jrg Wullschleger |
| 2008 | STORMED Hybrid Systems. | Vladimeros Vladimerou, Pavithra Prabhakar, Mahesh Viswanathan, Geir E. Dullerud |
| 2008 | Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. | Marc Tedder, Derek G. Corneil, Michel Habib, Christophe Paul |
| 2008 | Linear Logical Algorithms. | Robert J. Simmons, Frank Pfenning |
| 2008 | Building a Collision-Resistant Compression Function from Non-compressing Primitives. | Thomas Shrimpton, Martijn Stam |
| 2008 | Delegating Capabilities in Predicate Encryption Systems. | Elaine Shi, Brent Waters |
| 2008 | ATL* Satisfiability Is 2EXPTIME-Complete. | Sven Schewe |
| 2008 | Diagonal Circuit Identity Testing and Lower Bounds. | Nitin Saxena |
| 2008 | Constructing Efficient Dictionaries in Close to Sorting Time. | Milan Ruzic |
| 2008 | All-Pairs Shortest Paths with a Sublinear Additive Error. | Liam Roditty, Asaf Shapira |
| 2008 | Impossibility of a Quantum Speed-Up with a Faulty Oracle. | Oded Regev, Liron Schiff |
| 2008 | Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract). | Igor Razgon, Barry O'Sullivan |
| 2008 | Visibly Pushdown Transducers. | Jean-Franois Raskin, Frdric Servais |
| 2008 | Error-Tolerant Combiners for Oblivious Primitives. | Bartosz Przydatek, Jrg Wullschleger |