| 2008 | Balanced outcomes in social exchange networks. | Jon M. Kleinberg, va Tardos |
| 2008 | Multi-armed bandits in metric spaces. | Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal |
| 2008 | On hardness of learning intersection of two halfspaces. | Subhash Khot, Rishi Saket |
| 2008 | Graph and map isomorphism and all polyhedral embeddings in linear time. | Ken-ichi Kawarabayashi, Bojan Mohar |
| 2008 | Algebraic property testing: the role of invariance. | Tali Kaufman, Madhu Sudan |
| 2008 | On agnostic boosting and parity learning. | Adam Tauman Kalai, Yishay Mansour, Elad Verbin |
| 2008 | Universal semantic communication I. | Brendan Juba, Madhu Sudan |
| 2008 | Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. | Rahul Jain, Hartmut Klauck, Ashwin Nayak |
| 2008 | Cryptography with constant computational overhead. | Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2008 | Uniform direct product theorems: simplified, optimized, and derandomized. | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson |
| 2008 | Computing how we became human. | David Haussler |
| 2008 | Optimal mechanism design and money burning. | Jason D. Hartline, Tim Roughgarden |
| 2008 | The vpn conjecture is true. | Navin Goyal, Neil Olver, F. Bruce Shepherd |
| 2008 | Complete fairness in secure two-party computation. | S. Dov Gordon, Carmit Hazay, Jonathan Katz, Yehuda Lindell |
| 2008 | List-decoding reed-muller codes over small fields. | Parikshit Gopalan, Adam R. Klivans, David Zuckerman |
| 2008 | Agnostically learning decision trees. | Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans |
| 2008 | Delegating computation: interactive proofs for muggles. | Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum |
| 2008 | A (de)constructive approach to program checking. | Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum |
| 2008 | Trapdoors for hard lattices and new cryptographic constructions. | Craig Gentry, Chris Peikert, Vinod Vaikuntanathan |
| 2008 | Classical interaction cannot replace a quantum message. | Dmitry Gavinsky |
| 2008 | Finding short lattice vectors within mordell's inequality. | Nicolas Gama, Phong Q. Nguyen |
| 2008 | Logconcave random graphs. | Alan M. Frieze, Santosh S. Vempala, Juan Vera |
| 2008 | Infeasibility of instance compression and succinct PCPs for NP. | Lance Fortnow, Rahul Santhanam |
| 2008 | Evolvability from learning algorithms. | Vitaly Feldman |
| 2008 | An o(log | Jittat Fakcharoenphol, Bundit Laekhanukit |