| 2008 | Hardness of Minimizing and Learning DNF Expressions. | Subhash Khot, Rishi Saket |
| 2008 | Approximate Kernel Clustering. | Subhash Khot, Assaf Naor |
| 2008 | Unique Games with Entangled Provers are Easy. | Julia Kempe, Oded Regev, Ben Toner |
| 2008 | Entangled Games are Hard to Approximate. | Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick |
| 2008 | Fast Modular Composition in any Characteristic. | Kiran S. Kedlaya, Christopher Umans |
| 2008 | A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. | Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed |
| 2008 | Worst Case to Average Case Reductions for Polynomials. | Tali Kaufman, Shachar Lovett |
| 2008 | What Can We Learn Privately? | Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith |
| 2008 | Noise Tolerance of Expanders and Sublinear Expander Reconstruction. | Satyen Kale, Yuval Peres, C. Seshadhri |
| 2008 | Network Extractor Protocols. | Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman |
| 2008 | Near-Optimal Sparse Recovery in the L1 Norm. | Piotr Indyk, Milan Ruzic |
| 2008 | Sketching and Streaming Entropy via Approximation Theory. | Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak |
| 2008 | Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. | Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra |
| 2008 | Set Covering with our Eyes Closed. | Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, Mohit Singh |
| 2008 | Minimizing Movement in Mobile Facility Location Problems. | Zachary Friggstad, Mohammad R. Salavatipour |
| 2008 | Elections Can be Manipulated Often. | Ehud Friedgut, Gil Kalai, Noam Nisan |
| 2008 | On the Union of Cylinders in Three Dimensions. | Esther Ezra |
| 2008 | The Power of Reordering for Online Minimum Makespan Scheduling. | Matthias Englert, Deniz zmen, Matthias Westermann |
| 2008 | Leakage-Resilient Cryptography. | Stefan Dziembowski, Krzysztof Pietrzak |
| 2008 | Kakeya Sets, New Mergers and Old Extractors. | Zeev Dvir, Avi Wigderson |
| 2008 | Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. | Chinmoy Dutta, Jaikumar Radhakrishnan |
| 2008 | Multi-unit Auctions with Budget Limits. | Shahar Dobzinski, Ron Lavi, Noam Nisan |
| 2008 | Locally Testing Direct Product in the Low Error Range. | Irit Dinur, Elazar Goldenberg |
| 2008 | Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. | Yefim Dinitz, Michael Elkin, Shay Solomon |
| 2008 | Truthful Approximation Schemes for Single-Parameter Agents. | Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden |