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