Below is the list of papers accepted for FOCS 2008 (in order of submission).

Ran Raz.
A Counterexample to Strong Parallel Repetition

Esther Ezra.
On the Union of Cylinders in Three Dimensions

Ehud Friedgut, Gil Kalai and Noam Nisan.
Elections Can be Manipulated Often

Deeparnab Chakrabarty and Gagan Goel.
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

Julia Kempe, Oded Regev and Ben Toner.
Unique Games with Entangled Provers are Easy

Noga Alon and Asaf Nussboim.
k-wise independent random graphs

Punyashloka Biswal, James Lee and Satish Rao.
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows

Amit Chakrabarti, Alexander Jaffe, James Lee and Justin Vincent.
Embeddings, cuts, and flows in topological graphs: Lossy invariants, linearization, and 2-sums

Zeev Dvir and Avi Wigderson.
Kakeya sets, new mergers and old extractors

Ran Raz and Amir Yehudayoff.
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner and Thomas Vidick.
Entangled games are hard to approximate

Tom Leighton and Ankur Moitra.
Some Results on Greedy Embeddings in Metric Spaces

Timothy M. Chan, Mihai Patrascu and Liam Roditty.
Dynamic Connectivity: Connecting to Networks and Geometry

Jiri Matousek and Anastasios Sidiropoulos.
Inapproximability for metric embeddings into R^d

Christos Papadimitriou, Michael Schapira and Yaron Singer.
On the Hardness of Being Truthful

Jin-Yi Cai, Pinyan Lu and Mingji Xia.
Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness

Raphael Yuster.
Matrix sparsification for rank and determinant computations via nested dissection

Timothy Chow.
Almost-natural proofs

Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein and Avinatan Hasidim.
Broadcasting with side information

Tali Kaufman and Shachar Lovett.
Worst Case to Average Case Reductions for Polynomials

Monaldo Mastrolilli and Ola Svensson.
(Acyclic) Job Shops are Hard to Approximate

Stefan Dziembowski and Krzysztof Pietrzak.
Leakage-Resilient Cryptography in the Standard Model

Nikhil Devanur and Ravindran Kannan.
Polynomial time Algorithms for Computing Market Equilibria under general utility functions

Kiran Kedlaya and Christopher Umans.
Fast modular composition in any characteristic

Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau and Chun Kong Yung.
Degree Bounded Network Design with Metric Costs

Kunal Talwar, Rina Panigrahy and Udi Wieder.
A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match

Venkatesan Guruswami, Rajsekar Manokaran and Prasad Raghavendra.
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph

Manindra Agrawal and V Vinay.
Arithmetic Circuits: A Chasm at Depth Four

Shankar Bhamidi, Guy Bresler and Allan Sly.
Mixing time of exponential random graphs

Paul Beame and Dang-Trinh Huynh-Ngoc.
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi and Tim Roughgarden.
Truthful Approximation Schemes for Single-Parameter Agents

Andreas Bjorklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto.
Computing the Tutte polynomial in vertex-exponential time

Chaitanya Swamy and Maurice Cheung.
Approximation Algorithms for Single-minded Envy-free Profit-Maximization Problems with Limited Supply

Elazar Goldenberg and Irit Dinur.
Locally Testing Direct Products in the High Error Range

Constantinos Daskalakis and Christos Papadimitriou.
Discretized Multinomial Distributions, Covers, and Nash Equilibria in Anonymous Games

Christoph Lenzen, Thomas Locher and Roger Wattenhofer.
Clock Synchronization with Bounded Global and Local Skew

Shahar Dobzinski, Ron Lavi and Noam Nisan.
Multi-unit Auctions with Budget Limits

Rishi Saket and Subhash Khot.
Hardness of Minimizing and Learning DNF Expressions

Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski and Mohit Singh.
Set Covering with Our Eyes Closed

Dan Boneh, Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis and Brent Waters.
On The Impossibility of Basing Identity Based Encryption on Trapdoor Permutations

Mihai Patrascu.
(Data) Structures

Avraham Ben-Aroya, Oded Regev and Ronald de Wolf.
A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

Ittai Abraham, Yair Bartal and Ofer Neiman.
Nearly Tight Low Stretch Spanning Trees

Nicholas J.A. Harvey, Jelani Nelson and Krzysztof Onak.
Sketching and Streaming Entropy via Approximation Theory

Avinatan Hassidim and Michael Ben-Or.
The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)

Albert Atserias, Martin Grohe and Daniel Marx.
Size bounds and query plans for relational joins

Eli Ben-Sasson and Jakob Nordstr�m.
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

Yefim Dinitz, Michael Elkin and Shay Solomon.
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners

Subhash Khot and Assaf Naor.
Approximate kernel clustering

Laszlo Babai and Paolo Codenotti.
Isomorphism of 3-hypergraphs in moderately exponential time

Dana Moshkovitz and Ran Raz.
Two Query PCP with Sub-Constant Error

Satyen Kale, Yuval Peres and C. Seshadhri.
Noise Tolerance of Expanders and Sublinear Expander Reconstruction

Avinatan Hassidim, Haran Pilpel and Michael Ben-Or.
Quantum Multi Prover Interactive Proofs with Communicating Provers

Dimitris Achlioptas and Amin Coja-Oghlan.
Algorithmic Barriers from Phase Transitions

Adam Klivans, Ryan O'Donnell and Rocco Servedio.
Learning Geometric Concepts via Gaussian Surface Area

Guy Kindler, Ryan O'Donnell, Anup Rao and Avi Wigderson.
Rounding Schemes and Cubical Tilings with Sphere-Like Surface Area

Zachary Friggstad and Mohammad Salavatipour.
Minimizing Movement in Mobile Facility Location Problems

Piotr Indyk and Milan Ruzic.
Near-Optimal Sparse Recovery in the L_1 norm

Elchanan Mossel.
Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes

Alexander Sherstov.
The Unbounded-Error Communication Complexity of Symmetric Functions

Chinmoy Dutta and Jaikumar Radhakrishnan.
Lower Bounds For Noisy Wireless Networks using Sampling Algorithms

Zoya Svitkina and Lisa Fleischer.
Submodular Approximation: Sampling-based Algorithms and Lower Bounds

Benny Applebaum, Boaz Barak and David Xiao.
On Basing Lower-Bounds for Learning on Worst-Case Assumptions

Alexandr Andoni, Dorian Croitoru and Mihai Patrascu.
Hardness of Nearest Neighbor under L-infinity

Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam Smith.
What Can We Learn Privately?

Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev and David Steurer.
Rounding Parallel Repetitions of Unique Games

Alexander Razborov and Alexander Sherstov.
The Sign-Rank of AC^0

Ken-ichi Kawarabayashi, Bojan Mohar and Bruce Reed.
A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width

Julia Chuzhoy and Sanjeev Khanna.
Algorithms for Single-Source Vertex-Connectivity

Grant Schoenebeck.
Linear Level Lasserre Lower Bounds for Certain $k$-CSPs

Sebastien Roch.
Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier

Yael Kalai, Xin Li, Anup Rao and David Zuckerman.
Network Extractor Protocols

Huy Nguyen and Krzysztof Onak.
Constant-Time Approximation Algorithms via Local Improvements

Matthias Englert, Deniz �zmen and Matthias Westermann.
The Power of Reordering for Online Minimum Makespan Scheduling

Siuon Chan and Michael Molloy.
The Resolution Complexity of General Random Constraint Satisfaction Problems

Glencora Borradaile, Philip Klein and Claire Mathieu.
A polynomial-time approximation scheme for Euclidean Steiner forest

S. Charles Brubaker and Santosh Vempala.
Isotropic PCA and Affine-Invariant Clustering

Mihai Patrascu.
Succincter

Luca Trevisan, Salil Vadhan, Omer Reingold and Madhur Tulsiani.
Dense Subsets of Pseudorandom Sets

IEEE CS | ACM | SIGACT | SODA '08 | STOC '08 | SODA '07 | STOC '07 | FOCS '07