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