| 2008 | A (de)constructive approach to program checking. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum |
| 2008 | A combinatorial construction of almost-ramanujan graphs using the zig-zag product. Avraham Ben-Aroya, Amnon Ta-Shma |
| 2008 | A discriminative framework for clustering via similarity functions. Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala |
| 2008 | A fixed-parameter algorithm for the directed feedback vertex set problem. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon |
| 2008 | A learning theory approach to non-interactive database privacy. Avrim Blum, Katrina Ligett, Aaron Roth |
| 2008 | A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. Jin-Yi Cai, Xi Chen, Dong Li |
| 2008 | Additive approximation for bounded degree survivable network design. Lap Chi Lau, Mohit Singh |
| 2008 | Additive guarantees for degree bounded directed network design. Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan |
| 2008 | Agnostically learning decision trees. Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans |
| 2008 | Algebraic property testing: the role of invariance. Tali Kaufman, Madhu Sudan |
| 2008 | Algebrization: a new barrier in complexity theory. Scott Aaronson, Avi Wigderson |
| 2008 | Algorithms for subset selection in linear regression. Abhimanyu Das, David Kempe |
| 2008 | An effective ergodic theorem and some applications. Satyadev Nandakumar |
| 2008 | An o(log Jittat Fakcharoenphol, Bundit Laekhanukit |
| 2008 | An optimal sdp algorithm for max-cut, and equally optimal long code tests. Ryan O'Donnell, Yi Wu |
| 2008 | Balanced outcomes in social exchange networks. Jon M. Kleinberg, Éva Tardos |
| 2008 | Classical interaction cannot replace a quantum message. Dmitry Gavinsky |
| 2008 | Combinatorial construction of locally testable codes. Or Meir |
| 2008 | Communication in the presence of replication. Omer Barkol, Yuval Ishai, Enav Weinreb |
| 2008 | Complete fairness in secure two-party computation. S. Dov Gordon, Carmit Hazay, Jonathan Katz, Yehuda Lindell |
| 2008 | Computing how we became human. David Haussler |
| 2008 | Cryptography with constant computational overhead. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2008 | Decodability of group homomorphisms beyond the johnson bound. Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan |
| 2008 | Delegating computation: interactive proofs for muggles. Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum |
| 2008 | Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. Rahul Jain, Hartmut Klauck, Ashwin Nayak |
| 2008 | Elusive functions and lower bounds for arithmetic circuits. Ran Raz |
| 2008 | Every minor-closed property of sparse graphs is testable. Itai Benjamini, Oded Schramm, Asaf Shapira |
| 2008 | Evolvability from learning algorithms. Vitaly Feldman |
| 2008 | Fast integer multiplication using modular arithmetic. Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi |
| 2008 | Fast polynomial factorization and modular composition in small characteristic. Christopher Umans |
| 2008 | Fast-converging tatonnement algorithms for one-time and ongoing market problems. Richard Cole, Lisa Fleischer |
| 2008 | Faster approximate lossy generalized flow via interior point algorithms. Samuel I. Daitch, Daniel A. Spielman |
| 2008 | Finding short lattice vectors within mordell's inequality. Nicolas Gama, Phong Q. Nguyen |
| 2008 | Games for exchanging information. Gillat Kol, Moni Naor |
| 2008 | Graph and map isomorphism and all polyhedral embeddings in linear time. Ken-ichi Kawarabayashi, Bojan Mohar |
| 2008 | Graph sparsification by effective resistances. Daniel A. Spielman, Nikhil Srivastava |
| 2008 | Graphs, polymorphisms and the complexity of homomorphism problems. Libor Barto, Marcin Kozik, Todd Niven |
| 2008 | Hardness amplification proofs require majority. Ronen Shaltiel, Emanuele Viola |
| 2008 | Hardness-randomness tradeoffs for bounded depth arithmetic circuits. Zeev Dvir, Amir Shpilka, Amir Yehudayoff |
| 2008 | Inapproximability of pure nash equilibria. Alexander Skopalik, Berthold Vöcking |
| 2008 | Infeasibility of instance compression and succinct PCPs for NP. Lance Fortnow, Rahul Santhanam |
| 2008 | Interdomain routing and games. Hagay Levin, Michael Schapira, Aviv Zohar |
| 2008 | Inverse conjecture for the gowers norm is false. Shachar Lovett, Roy Meshulam, Alex Samorodnitsky |
| 2008 | List-decoding reed-muller codes over small fields. Parikshit Gopalan, Adam R. Klivans, David Zuckerman |
| 2008 | Logconcave random graphs. Alan M. Frieze, Santosh S. Vempala, Juan Vera |
| 2008 | Lossy trapdoor functions and their applications. Chris Peikert, Brent Waters |
| 2008 | Minimum k-way cuts via deterministic greedy tree packing. Mikkel Thorup |
| 2008 | Multi-armed bandits in metric spaces. Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal |
| 2008 | Network design for vertex connectivity. Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna |
| 2008 | On agnostic boosting and parity learning. Adam Tauman Kalai, Yishay Mansour, Elad Verbin |
| 2008 | On hardness of learning intersection of two halfspaces. Subhash Khot, Rishi Saket |
| 2008 | On partitioning graphs via single commodity flows. Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi |
| 2008 | On the constant-depth complexity of k-clique. Benjamin Rossman |
| 2008 | Optimal algorithms and inapproximability results for every CSP? Prasad Raghavendra |
| 2008 | Optimal approximation for the submodular welfare problem in the value oracle model. Jan Vondrák |
| 2008 | Optimal hierarchical decompositions for congestion minimization in networks. Harald Räcke |
| 2008 | Optimal mechanism design and money burning. Jason D. Hartline, Tim Roughgarden |
| 2008 | Optimal query complexity bounds for finding graphs. Sung-Soon Choi, Jeong Han Kim |
| 2008 | Parallel repetition in projection games and a concentration bound. Anup Rao |
| 2008 | Pricing combinatorial markets for tournaments. Yiling Chen, Sharad Goel, David M. Pennock |
| 2008 | Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008 Cynthia Dwork |
| 2008 | Random projection trees and low dimensional manifolds. Sanjoy Dasgupta, Yoav Freund |
| 2008 | Randomized competitive algorithms for generalized caching. Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2008 | Randomized k-server on hierarchical binary trees. Aaron Cote, Adam Meyerson, Laura J. Poplawski |
| 2008 | Read-once polynomial identity testing. Amir Shpilka, Ilya Volkovich |
| 2008 | Regret minimization and the price of total anarchy. Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, Aaron Roth |
| 2008 | Rethinking internet routing. Jennifer Rexford |
| 2008 | Robust lower bounds for communication and stream computation. Amit Chakrabarti, Graham Cormode, Andrew McGregor |
| 2008 | Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz |
| 2008 | Sketching in adversarial environments. Ilya Mironov, Moni Naor, Gil Segev |
| 2008 | Some topics in analysis of boolean functions. Ryan O'Donnell |
| 2008 | Span-program-based quantum algorithm for evaluating formulas. Ben Reichardt, Robert Spalek |
| 2008 | Stateless distributed gradient descent for positive linear programs. Baruch Awerbuch, Rohit Khandekar |
| 2008 | Testing symmetric properties of distributions. Paul Valiant |
| 2008 | The chow parameters problem. Ryan O'Donnell, Rocco A. Servedio |
| 2008 | The complexity of temporal constraint satisfaction problems. Manuel Bodirsky, Jan Kára |
| 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 pattern matrix method for lower bounds on quantum communication. Alexander A. Sherstov |
| 2008 | The vpn conjecture is true. Navin Goyal, Neil Olver, F. Bruce Shepherd |
| 2008 | Tight rmr lower bounds for mutual exclusion and other problems. Hagit Attiya, Danny Hendler, Philipp Woelfel |
| 2008 | Towards an optimal separation of space and length in resolution. Jakob Nordström, Johan Håstad |
| 2008 | Trapdoors for hard lattices and new cryptographic constructions. Craig Gentry, Chris Peikert, Vinod Vaikuntanathan |
| 2008 | Unconditional pseudorandom generators for low degree polynomials. Shachar Lovett |
| 2008 | Uniform direct product theorems: simplified, optimized, and derandomized. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson |
| 2008 | Unique games on expanding constraint graphs are easy: extended abstract. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2008 | Universal semantic communication I. Brendan Juba, Madhu Sudan |