| 2008 | (Acyclic) JobShops are Hard to Approximate. Monaldo Mastrolilli, Ola Svensson |
| 2008 | (Data) STRUCTURES. Mihai Patrascu |
| 2008 | 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, October 25-28, 2008 |
| 2008 | A Counterexample to Strong Parallel Repetition. Ran Raz |
| 2008 | A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems. Siu On Chan, Michael Molloy |
| 2008 | A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match. Rina Panigrahy, Kunal Talwar, Udi Wieder |
| 2008 | A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. Avraham Ben-Aroya, Oded Regev, Ronald de Wolf |
| 2008 | A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. Glencora Borradaile, Philip N. Klein, Claire Mathieu |
| 2008 | A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed |
| 2008 | Algorithmic Barriers from Phase Transitions. Dimitris Achlioptas, Amin Coja-Oghlan |
| 2008 | Algorithms for Single-Source Vertex Connectivity. Julia Chuzhoy, Sanjeev Khanna |
| 2008 | Almost-Natural Proofs. Timothy Y. Chow |
| 2008 | Approximate Kernel Clustering. Subhash Khot, Assaf Naor |
| 2008 | Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply. Maurice Cheung, Chaitanya Swamy |
| 2008 | Arithmetic Circuits: A Chasm at Depth Four. Manindra Agrawal, V. Vinay |
| 2008 | Average-case Complexity. Luca Trevisan |
| 2008 | Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra |
| 2008 | Broadcasting with Side Information. Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, Avinatan Hassidim |
| 2008 | Clock Synchronization with Bounded Global and Local Skew. Christoph Lenzen, Thomas Locher, Roger Wattenhofer |
| 2008 | Computing the Tutte Polynomial in Vertex-Exponential Time. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |
| 2008 | Constant-Time Approximation Algorithms via Local Improvements. Huy N. Nguyen, Krzysztof Onak |
| 2008 | Degree Bounded Network Design with Metric Costs. Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung |
| 2008 | Dense Subsets of Pseudorandom Sets. Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
| 2008 | Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. Constantinos Daskalakis, Christos H. Papadimitriou |
| 2008 | Dynamic Connectivity: Connecting to Networks and Geometry. Timothy M. Chan, Mihai Patrascu, Liam Roditty |
| 2008 | Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. Punyashloka Biswal, James R. Lee, Satish Rao |
| 2008 | Elections Can be Manipulated Often. Ehud Friedgut, Gil Kalai, Noam Nisan |
| 2008 | Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent |
| 2008 | Entangled Games are Hard to Approximate. Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick |
| 2008 | Fast Modular Composition in any Characteristic. Kiran S. Kedlaya, Christopher Umans |
| 2008 | Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. Elchanan Mossel |
| 2008 | Hardness of Minimizing and Learning DNF Expressions. Subhash Khot, Rishi Saket |
| 2008 | Hardness of Nearest Neighbor under L-infinity. Alexandr Andoni, Dorian Croitoru, Mihai Patrascu |
| 2008 | Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. Jin-Yi Cai, Pinyan Lu, Mingji Xia |
| 2008 | Inapproximability for Metric Embeddings into R^d. Jirí Matousek, Anastasios Sidiropoulos |
| 2008 | Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. László Babai, Paolo Codenotti |
| 2008 | Isotropic PCA and Affine-Invariant Clustering. S. Charles Brubaker, Santosh S. Vempala |
| 2008 | Kakeya Sets, New Mergers and Old Extractors. Zeev Dvir, Avi Wigderson |
| 2008 | Leakage-Resilient Cryptography. Stefan Dziembowski, Krzysztof Pietrzak |
| 2008 | Learning Geometric Concepts via Gaussian Surface Area. Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio |
| 2008 | Linear Level Lasserre Lower Bounds for Certain k-CSPs. Grant Schoenebeck |
| 2008 | Locally Testing Direct Product in the Low Error Range. Irit Dinur, Elazar Goldenberg |
| 2008 | Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. Chinmoy Dutta, Jaikumar Radhakrishnan |
| 2008 | Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. Nikhil R. Devanur, Ravi Kannan |
| 2008 | Matrix Sparsification for Rank and Determinant Computations via Nested Dissection. Raphael Yuster |
| 2008 | Minimizing Movement in Mobile Facility Location Problems. Zachary Friggstad, Mohammad R. Salavatipour |
| 2008 | Mixing Time of Exponential Random Graphs. Shankar Bhamidi, Guy Bresler, Allan Sly |
| 2008 | Multi-unit Auctions with Budget Limits. Shahar Dobzinski, Ron Lavi, Noam Nisan |
| 2008 | Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. Ran Raz, Amir Yehudayoff |
| 2008 | Near-Optimal Sparse Recovery in the L1 Norm. Piotr Indyk, Milan Ruzic |
| 2008 | Nearly Tight Low Stretch Spanning Trees. Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2008 | Network Extractor Protocols. Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman |
| 2008 | Noise Tolerance of Expanders and Sublinear Expander Reconstruction. Satyen Kale, Yuval Peres, C. Seshadhri |
| 2008 | On Basing Lower-Bounds for Learning on Worst-Case Assumptions. Benny Applebaum, Boaz Barak, David Xiao |
| 2008 | On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. Deeparnab Chakrabarty, Gagan Goel |
| 2008 | On the Hardness of Being Truthful. Christos H. Papadimitriou, Michael Schapira, Yaron Singer |
| 2008 | On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters |
| 2008 | On the Union of Cylinders in Three Dimensions. Esther Ezra |
| 2008 | On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. Paul Beame, Dang-Trinh Huynh-Ngoc |
| 2008 | Quantum Multi Prover Interactive Proofs with Communicating Provers. Michael Ben-Or, Avinatan Hassidim, Haran Pilpel |
| 2008 | Rounding Parallel Repetitions of Unique Games. Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer |
| 2008 | Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier. Sébastien Roch |
| 2008 | Set Covering with our Eyes Closed. Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, Mohit Singh |
| 2008 | Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. Yefim Dinitz, Michael Elkin, Shay Solomon |
| 2008 | Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. Eli Ben-Sasson, Jakob Nordström |
| 2008 | Size Bounds and Query Plans for Relational Joins. Albert Atserias, Martin Grohe, Dániel Marx |
| 2008 | Sketching and Streaming Entropy via Approximation Theory. Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak |
| 2008 | Some Results on Greedy Embeddings in Metric Spaces. Ankur Moitra, Tom Leighton |
| 2008 | Spherical Cubes and Rounding in High Dimensions. Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson |
| 2008 | Submodular Approximation: Sampling-based Algorithms and Lower Bounds. Zoya Svitkina, Lisa Fleischer |
| 2008 | Succincter. Mihai Patrascu |
| 2008 | The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). Michael Ben-Or, Avinatan Hassidim |
| 2008 | The Polynomial Method in Quantum and Classical Computing. Scott Aaronson |
| 2008 | The Power of Reordering for Online Minimum Makespan Scheduling. Matthias Englert, Deniz Özmen, Matthias Westermann |
| 2008 | The Sign-Rank of AC^O. Alexander A. Razborov, Alexander A. Sherstov |
| 2008 | The Unbounded-Error Communication Complexity of Symmetric Functions. Alexander A. Sherstov |
| 2008 | Theory of Sponsored Search Auctions. Gagan Aggarwal, S. Muthukrishnan |
| 2008 | Truthful Approximation Schemes for Single-Parameter Agents. Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden |
| 2008 | Two Query PCP with Sub-Constant Error. Dana Moshkovitz, Ran Raz |
| 2008 | Unique Games with Entangled Provers are Easy. Julia Kempe, Oded Regev, Ben Toner |
| 2008 | What Can We Learn Privately? Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith |
| 2008 | Worst Case to Average Case Reductions for Polynomials. Tali Kaufman, Shachar Lovett |
| 2008 | k-Wise Independent Random Graphs. Noga Alon, Asaf Nussboim |