| 2008 | Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. | Nikhil R. Devanur, Ravi Kannan |
| 2008 | Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2008 | Algorithms for Single-Source Vertex Connectivity. | Julia Chuzhoy, Sanjeev Khanna |
| 2008 | Almost-Natural Proofs. | Timothy Y. Chow |
| 2008 | Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply. | Maurice Cheung, Chaitanya Swamy |
| 2008 | Dynamic Connectivity: Connecting to Networks and Geometry. | Timothy M. Chan, Mihai Patrascu, Liam Roditty |
| 2008 | A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems. | Siu On Chan, Michael Molloy |
| 2008 | Degree Bounded Network Design with Metric Costs. | Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung |
| 2008 | On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. | Deeparnab Chakrabarty, Gagan Goel |
| 2008 | Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. | Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent |
| 2008 | Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2008 | Isotropic PCA and Affine-Invariant Clustering. | S. Charles Brubaker, Santosh S. Vempala |
| 2008 | A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. | Glencora Borradaile, Philip N. Klein, Claire Mathieu |
| 2008 | On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. | Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters |
| 2008 | Computing the Tutte Polynomial in Vertex-Exponential Time. | Andreas Bjrklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |
| 2008 | Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. | Punyashloka Biswal, James R. Lee, Satish Rao |
| 2008 | Mixing Time of Exponential Random Graphs. | Shankar Bhamidi, Guy Bresler, Allan Sly |
| 2008 | Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. | Eli Ben-Sasson, Jakob Nordstrm |
| 2008 | Quantum Multi Prover Interactive Proofs with Communicating Provers. | Michael Ben-Or, Avinatan Hassidim, Haran Pilpel |
| 2008 | The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). | Michael Ben-Or, Avinatan Hassidim |
| 2008 | A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. | Avraham Ben-Aroya, Oded Regev, Ronald de Wolf |
| 2008 | On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. | Paul Beame, Dang-Trinh Huynh-Ngoc |
| 2008 | Rounding Parallel Repetitions of Unique Games. | Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer |
| 2008 | Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. | Lszl Babai, Paolo Codenotti |
| 2008 | Size Bounds and Query Plans for Relational Joins. | Albert Atserias, Martin Grohe, Dniel Marx |