| 2008 | Read-once polynomial identity testing. | Amir Shpilka, Ilya Volkovich |
| 2008 | The pattern matrix method for lower bounds on quantum communication. | Alexander A. Sherstov |
| 2008 | Hardness amplification proofs require majority. | Ronen Shaltiel, Emanuele Viola |
| 2008 | On the constant-depth complexity of k-clique. | Benjamin Rossman |
| 2008 | Rethinking internet routing. | Jennifer Rexford |
| 2008 | Span-program-based quantum algorithm for evaluating formulas. | Ben Reichardt, Robert Spalek |
| 2008 | Elusive functions and lower bounds for arithmetic circuits. | Ran Raz |
| 2008 | Parallel repetition in projection games and a concentration bound. | Anup Rao |
| 2008 | Optimal algorithms and inapproximability results for every CSP? | Prasad Raghavendra |
| 2008 | Optimal hierarchical decompositions for congestion minimization in networks. | Harald Rcke |
| 2008 | Lossy trapdoor functions and their applications. | Chris Peikert, Brent Waters |
| 2008 | On partitioning graphs via single commodity flows. | Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi |
| 2008 | An optimal sdp algorithm for max-cut, and equally optimal long code tests. | Ryan O'Donnell, Yi Wu |
| 2008 | The chow parameters problem. | Ryan O'Donnell, Rocco A. Servedio |
| 2008 | Some topics in analysis of boolean functions. | Ryan O'Donnell |
| 2008 | Towards an optimal separation of space and length in resolution. | Jakob Nordstrm, Johan Hstad |
| 2008 | An effective ergodic theorem and some applications. | Satyadev Nandakumar |
| 2008 | Sketching in adversarial environments. | Ilya Mironov, Moni Naor, Gil Segev |
| 2008 | Combinatorial construction of locally testable codes. | Or Meir |
| 2008 | Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. | Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz |
| 2008 | Inverse conjecture for the gowers norm is false. | Shachar Lovett, Roy Meshulam, Alex Samorodnitsky |
| 2008 | Unconditional pseudorandom generators for low degree polynomials. | Shachar Lovett |
| 2008 | Interdomain routing and games. | Hagay Levin, Michael Schapira, Aviv Zohar |
| 2008 | Additive approximation for bounded degree survivable network design. | Lap Chi Lau, Mohit Singh |
| 2008 | Games for exchanging information. | Gillat Kol, Moni Naor |