| 2006 | Independent Zero-Knowledge Sets. | Rosario Gennaro, Silvio Micali |
| 2006 | Constructing Exponential-Size Deterministic Zielonka Automata. | Blaise Genest, Anca Muscholl |
| 2006 | Better Algorithms for Minimizing Average Flow-Time on Related Machines. | Naveen Garg, Amit Kumar |
| 2006 | Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions. | Martin Gairing, Burkhard Monien, Karsten Tiemann |
| 2006 | An Efficient Compiler from | Jun Furukawa, Kaoru Kurosawa, Hideki Imai |
| 2006 | How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover. | Toshihiro Fujito |
| 2006 | Dynamic Matrix Rank. | Gudmund Skovbjerg Frandsen, Peter Frands Frandsen |
| 2006 | Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie-Hellman Schemes. | Pierre-Alain Fouque, David Pointcheval, Jacques Stern, Sbastien Zimmer |
| 2006 | Atomic Congestion Games Among Coalitions. | Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis |
| 2006 | Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
| 2006 | Optimal Resilient Sorting and Searching in the Presence of Memory Faults. | Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano |
| 2006 | On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations. | Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo |
| 2006 | The Myriad Virtues of Wavelet Trees. | Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini |
| 2006 | Recursive Concurrent Stochastic Games. | Kousha Etessami, Mihalis Yannakakis |
| 2006 | A Robust APTAS for the Classical Bin Packing Problem. | Leah Epstein, Asaf Levin |
| 2006 | On Counting Homomorphisms to Directed Acyclic Graphs. | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson |
| 2006 | Differential Privacy. | Cynthia Dwork |
| 2006 | An Efficient Provable Distinguisher for HFE. | Vivien Dubois, Louis Granboulan, Jacques Stern |
| 2006 | Finite-State Dimension and Real Arithmetic. | David Doty, Jack H. Lutz, Satyadev Nandakumar |
| 2006 | On the Impossibility of Extracting Classical Randomness Using a Quantum Computer. | Yevgeniy Dodis, Renato Renner |
| 2006 | Planar Crossing Numbers of Genus | Hristo N. Djidjev, Imrich Vrto |
| 2006 | Symbolic Protocol Analysis in Presence of a Homomorphism Operator and | Stphanie Delaune, Pascal Lafourcade, Denis Lugiez, Ralf Treinen |
| 2006 | The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. | Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou |
| 2006 | The One Way to Quantum Computation. | Vincent Danos, Elham Kashefi, Prakash Panangaden |
| 2006 | A Probabilistic Hoare-style Logic for Game-Based Cryptographic Proofs. | Ricardo Corin, Jerry den Hartog |