| 2006 | Half-Positional Determinacy of Infinite Games. | Eryk Kopczynski |
| 2006 | Lower Bounds of Static Lovsz-Schrijver Calculus Proofs for Tseitin Tautologies. | Arist Kojevnikov, Dmitry Itsykson |
| 2006 | Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. | Subhash Khot, Ashok Kumar Ponnuswami |
| 2006 | Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding. | Akinori Kawachi, Tomoyuki Yamakami |
| 2006 | On Intersection Problems for Polynomially Generated Sets. | Karianto Wong, Aloys Krieg, Wolfgang Thomas |
| 2006 | Communication of Two Stacks and Rewriting. | Juhani Karhumki, Michal Kunc, Alexander Okhotin |
| 2006 | Small Sweeping 2NFAs Are Not Closed Under Complement. | Christos A. Kapoutsis |
| 2006 | Dynamic Interpolation Search Revisited. | Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios K. Tsakalidis, Kostas Tsichlas, Christos D. Zaroliagis |
| 2006 | A Dolev-Yao-Based Definition of Abuse-Free Protocols. | Detlef Khler, Ralf Ksters, Thomas Wilke |
| 2006 | On Complexity of Grammars Related to the Safety Problem. | Tomasz Jurdzinski |
| 2006 | Untitled record | Radha Jagadeesan, Alan Jeffrey, Corin Pitcher, James Riely |
| 2006 | Descriptive and Relative Completeness of Logics for Higher-Order Functions. | Kohei Honda, Martin Berger, Nobuko Yoshida |
| 2006 | On the Bipartite Unique Perfect Matching Problem. | Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf |
| 2006 | Comparing Reductions to NP-Complete Sets. | John M. Hitchcock, Aduri Pavan |
| 2006 | Nearly Optimal Visibility Representations of Plane Graphs. | Xin He, Huaming Zhang |
| 2006 | Approximating the Orthogonal Knapsack Problem for Hypercubes. | Rolf Harren |
| 2006 | On Everlasting Security in the | Danny Harnik, Moni Naor |
| 2006 | A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs. | Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn |
| 2006 | Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions. | Iftach Haitner, Danny Harnik, Omer Reingold |
| 2006 | Typed GoI for Exponentials. | Esfandiar Haghverdi |
| 2006 | Commutative Locative Quantifiers for Multiplicative Linear Logic. | Stefano Guerrini, Patrizia Marzuoli |
| 2006 | Testing Graph Isomorphism in Parallel by Playing a Game. | Martin Grohe, Oleg Verbitsky |
| 2006 | The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. | Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou |
| 2006 | Optimal Lower Bounds for Rank and Select Indexes. | Alexander Golynski |
| 2006 | Deterministic Priority Mean-Payoff Games as Limits of Discounted Games. | Hugo Gimbert, Wieslaw Zielonka |