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


Ran Raz, Amir Shpilka and Amir Yehudayoff.
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

Louay Bazzi.
Polylogarithmic independence can fool  DNF formulas

Daniel Marx.
On the optimality of planar and geometric approximation schemes

Daniel Marx.
Can you beat treewidth?

Subhash Khot and Assaf Naor.
Linear equations modulo $2$ and the $L_1$ diameter of convex bodies

Madhu Sudan and Tali Kaufman.
Sparse Random Linear Codes are Locally Decodable and Testable

Noga Alon and Michael Capalbo.
Finding disjoint paths in expanders deterministically and online

Daniel Stefankovic, Santosh Vempala and Eric Vigoda.
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and
Counting

Esther Ezra and Micha Sharir.
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions

Zeev Dvir, Ariel Gabizon and Avi Wigderson.
Extractors and Rank Extractors for Polynomial Sources

Per Austrin.
Towards Sharp Inapproximability For Any 2-CSP

Sudipto Guha and Kamesh Munagala.
Approximation Algorithms for Partial-information based Stochastic Control
with Markovian Rewards

Xi Chen and Shang-Hua Teng.
Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point
Computation

Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd and Lisa Zhang.
Buy-at-Bulk Network Design with Protection

Nikhil Bansal, Niv Buchbinder and Seffi Naor.
A Primal-Dual Randomized Algorithm for Weighted Paging

Christoph Ambuehl, Monaldo Mastrolilli and Ola Svensson.
Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and
Precedence Constrained Scheduling

Parikshit Gopalan, Subhash Khot and Rishi Saket.
Hardness of Reconstructing Multivariate Polynomials over Finite Fields

Konstantinos Georgiou, Avner Magen, Toniann Pitassi and Iannis Tourlakis.
Integrality gaps of 2-o(1) for Vertex Cover SDPs in the Lovasz-Schrijver
hierarchy

Vladimir Braverman and Rafail Ostrovsky.
Smooth Histograms for Sliding Windows

Antoine Gerschenfeld and Andrea Montanari.
Reconstruction for models on random graphs

Uriel Feige.
Refuting smoothed 3CNF formulas

Oded Regev and Ben Toner.
Simulating Quantum Correlations with Finite Communication

Andrej Bogdanov and Muli Safra.
Hardness amplification for errorless heuristics

Uriel Feige, Vahab Mirrokni and Jan Vondrak.
Maximizing non-monotone submodular functions

Frank McSherry and Kunal Talwar.
Mechanism Design via Differential Privacy

Andrej Bogdanov and Emanuele Viola.
Pseudorandom bits for polynomials via the Gowers norm

Andrew M. Childs, Leonard J. Schulman and Umesh V. Vazirani.
Quantum algorithms for hidden nonlinear structures

Constantinos Daskalakis and Christos Papadimitriou.
Computing Equilibria in Anonymous Games

Iftach Haitner, Jonathan J. Hoch, Omer Reingold and Gil Segev.
Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the
Round Complexity of Statistically-Hiding Commitments

Stefan Dziembowski and Krzysztof Pietrzak.
Intrusion-Resilient Secret Sharing

Philipp Hertel and Toniann Pitassi.
Exponential Time/Space Speedups for Resolution and the PSPACE-completeness
of Black-White Pebbling

Stefan Dantchev, Barnaby Martin and Stefan Szeider.
Parameterized Proof Complexity

Emanuele Viola and Avi Wigderson.
One-way multi-party communication lower bound for pointer jumping with
applications

Arie Matsliah, Eldar Fischer and Asaf Shapira.
Approximate Hypergraph Partitioning and Applications

Mihai Patrascu and Mikkel Thorup.
Planning for Fast Connectivity Updates

Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer and
Dmitriy Morozov.
Inferring Local Homology from Sampled Stratified Spaces

Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber
and Clifford Stein.
Non-Preemptive Min-Sum Scheduling with Resource Augmentation

Dorit Aharonov, Daniel Gottesman, Sandy Irani and Julia Kempe.
The power of quantum systems on a line

Ran Canetti, Rafael Pass and Abhi Shelat.
Cryptography from Sunspots

Jeong Han Kim, Ravi Montenegro and Prasad Tetali.
A Near Optimal Bound for Pollard's Rho to Solve Discrete Log

Naveen Garg and Amit Kumar.
Minimizing Average Flow-time : Upper and Lower Bounds

Artur Czumaj and Christian Sohler.
Testing Expansion in Bounded-Degree Graphs

Alexandr Andoni and Robi Krauthgamer.
The Computational Hardness of Estimating Edit Distance

Yun Long, Asaf Nachmias and Yuval Peres.
Mixing time power laws at criticality

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt
Rubinfeld, Rocco A. Servedio and Andrew Wan.
Testing for Concise Representations

Qi Cheng.
Derandomization of Sparse Cyclotomic Integer Zero Testing

Andris Ambainis, Andrew Childs, Ben Reichardt, Robert Spalek and Shengyu
Zhang.
Any AND-OR formula of size N can be evaluated in time N^{1/2+o(1)} on a
quantum computer

Moses Charikar, Konstantin Makarychev and Yury Makarychev.
Tradeoffs between Local and Global Distortions of Metric Spaces

Moses Charikar, Konstantin Makarychev and Yury Makarychev.
On the Advantage over Random for Maximum Acyclic Subgraph

Anna Gal and Parikshit Gopalan.
Lower Bounds on Streaming Algorithms for Approximating the Length of the
Longest Increasing Subsequence

Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky and Amit Sahai.
Covert Multi-party Computation

Eyal Lubetzky and Uri Stav.
Non-linear index coding outperforming the linear optimum

Boaz Barak and Mohammad Mahmoody-Ghidary.
Lower Bounds on Signatures From Symmetric Primitives

Kousha Etessami and Mihalis Yannakakis.
On the Complexity of Nash Equilibria and Other Fixed Points

Guy Blelloch and Daniel Golovin.
Strongly History-Independent Hashing with Applications

Eden Chlamtac.
Approximation Algorithms Using Hierarchies of Semidefinite Programming
Relaxations

Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo and Rafail Ostrovsky.
Round Complexity of Authenticated Broadcast with a Dishonest Majority

Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Kunal Talwar.
Balloon Popping With Applications to Ascending Auctions

Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith.
Strong Lower Bounds for Approximating Distribution Support Size and the
Distinct Elements Problem

Arkadev Chattopadhyay.
Discrepancy and the Power of Bottom Fan-In in Depth-Three Circuits

Jonathan Kelner and Evdokia Nikolova.
On the Hardness and Smoothed Complexity of Quasi-concave Minimization

Dan Boneh, Craig Gentry and Mike Hamburg.
Identity Based Encryption Without Pairings

Christos Koufogiannakis and Neal Young.
A fast approximation algorithm for large packing and covering linear
programs