| 2008 | Approximating List-Coloring on a Fixed Surface. | Ken-ichi Kawarabayashi |
| 2008 | Improving the Round Complexity of VSS in Point-to-Point Networks. | Jonathan Katz, Chiu-Yuen Koo, Ranjit Kumaresan |
| 2008 | Attribute Grammars and Categorical Semantics. | Shin-ya Katsumata |
| 2008 | Randomized Self-assembly for Approximate Shapes. | Ming-Yang Kao, Robert T. Schweller |
| 2008 | An Expansion Tester for Bounded Degree Graphs. | Satyen Kale, C. Seshadhri |
| 2008 | Interactive PCP. | Yael Tauman Kalai, Ran Raz |
| 2008 | Complementation, Disambiguation, and Determinization of Bchi Automata Unified. | Detlef Khler, Thomas Wilke |
| 2008 | Leftist Grammars Are Non-primitive Recursive. | Tomasz Jurdzinski |
| 2008 | Extended pi-Calculi. | Magnus Johansson, Joachim Parrow, Bjrn Victor, Jesper Bengtson |
| 2008 | On the Computational Completeness of Equations over Sets of Natural Numbers. | Artur Jez, Alexander Okhotin |
| 2008 | Affiliation-Hiding Envelope and Authentication Schemes with Efficient Support for Multiple Credentials. | Stanislaw Jarecki, Xiaomin Liu |
| 2008 | Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2. | Klaus Jansen, Ralf Thle |
| 2008 | Polynomial-Time Construction of Linear Network Coding. | Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita |
| 2008 | On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak. | Jonathan J. Hoch, Adi Shamir |
| 2008 | Asynchronous Multi-Party Computation with Quadratic Communication. | Martin Hirt, Jesper Buus Nielsen, Bartosz Przydatek |
| 2008 | Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks. | Sean Hallgren, Alexandra Kolla, Pranab Sen, Shengyu Zhang |
| 2008 | Superpolynomial Speedups Based on Almost Any Quantum Circuit. | Sean Hallgren, Aram W. Harrow |
| 2008 | Faster Algorithms for Incremental Topological Ordering. | Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan |
| 2008 | Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination. | Sudipto Guha, Andrew McGregor |
| 2008 | Finite Automata, Digraph Connectivity, and Regular Expression Size. | Hermann Gruber, Markus Holzer |
| 2008 | Open Implication. | Karin Greimel, Roderick Bloem, Barbara Jobstmann, Moshe Y. Vardi |
| 2008 | Tree Projections: Hypergraph Games and Minimality. | Gianluigi Greco, Francesco Scarcello |
| 2008 | Bounded Ciphertext Policy Attribute Based Encryption. | Vipul Goyal, Abhishek Jain, Omkant Pandey, Amit Sahai |
| 2008 | When Does Partial Commutative Closure Preserve Regularity? | Antonio Cano Gmez, Giovanna Guaiana, Jean-Eric Pin |
| 2008 | How to Encrypt with the LPN Problem. | Henri Gilbert, Matthew J. B. Robshaw, Yannick Seurin |