| 2008 | Hardness-randomness tradeoffs for bounded depth arithmetic circuits. | Zeev Dvir, Amir Shpilka, Amir Yehudayoff |
| 2008 | Decodability of group homomorphisms beyond the johnson bound. | Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan |
| 2008 | Fast integer multiplication using modular arithmetic. | Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi |
| 2008 | Algorithms for subset selection in linear regression. | Abhimanyu Das, David Kempe |
| 2008 | Random projection trees and low dimensional manifolds. | Sanjoy Dasgupta, Yoav Freund |
| 2008 | Faster approximate lossy generalized flow via interior point algorithms. | Samuel I. Daitch, Daniel A. Spielman |
| 2008 | Randomized k-server on hierarchical binary trees. | Aaron Cote, Adam Meyerson, Laura J. Poplawski |
| 2008 | Fast-converging tatonnement algorithms for one-time and ongoing market problems. | Richard Cole, Lisa Fleischer |
| 2008 | Optimal query complexity bounds for finding graphs. | Sung-Soon Choi, Jeong Han Kim |
| 2008 | A fixed-parameter algorithm for the directed feedback vertex set problem. | Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon |
| 2008 | Pricing combinatorial markets for tournaments. | Yiling Chen, Sharad Goel, David M. Pennock |
| 2008 | Network design for vertex connectivity. | Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna |
| 2008 | Robust lower bounds for communication and stream computation. | Amit Chakrabarti, Graham Cormode, Andrew McGregor |
| 2008 | A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. | Jin-yi Cai, Xi Chen, Dong Li |
| 2008 | The myth of the folk theorem. | Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou |
| 2008 | The complexity of temporal constraint satisfaction problems. | Manuel Bodirsky, Jan Kra |
| 2008 | A learning theory approach to non-interactive database privacy. | Avrim Blum, Katrina Ligett, Aaron Roth |
| 2008 | Regret minimization and the price of total anarchy. | Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, Aaron Roth |
| 2008 | Every minor-closed property of sparse graphs is testable. | Itai Benjamini, Oded Schramm, Asaf Shapira |
| 2008 | A combinatorial construction of almost-ramanujan graphs using the zig-zag product. | Avraham Ben-Aroya, Amnon Ta-Shma |
| 2008 | Graphs, polymorphisms and the complexity of homomorphism problems. | Libor Barto, Marcin Kozik, Todd Niven |
| 2008 | Communication in the presence of replication. | Omer Barkol, Yuval Ishai, Enav Weinreb |
| 2008 | Additive guarantees for degree bounded directed network design. | Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan |
| 2008 | Randomized competitive algorithms for generalized caching. | Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2008 | A discriminative framework for clustering via similarity functions. | Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |