List of accepted papers for FOCS 2008:


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 

Robert Kleinberg, Georgios Piliouras and Eva Tardos.
Multiplicative updates outperform generic no-regret learning in congestion games 

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