FOCS 2010 Proceedings  
Compressed Zip File
Foreword
Organizing Committee
Program-Committee
Reviewers
Table of Contents
Saturday, October 23  
11:00 -12:30 Tutorial 1: Ketan Mulmuley. Geometric Complexity Theory (GCT).
12:30 - 1:45 Lunch (On your own)
1:45 - 3:15 Tutorial 2: Mihai Pătraşcu. How to Grow Your Lower Bounds.
3:30 - 5:00 Tutorial 3: Tim Roughgarden. How To Think About Mechanism Design.
6:00 - 9:00 Welcoming Reception
Sunday, October 24  
8:00 - 8:45 Continental Breakfast
    Session 1A Session 1B
8:45 - 9:05 Constructive Algorithms for Discrepancy Minimization Boosting and Differential Privacy
    Nikhil Bansal Cynthia Dwork and Guy Rothblum and Salil Vadhan
9:10 - 9:30 Bounded Independence Fools Degree-2 Threshold Functions A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis
    Ilias Diakonikolas and Daniel M. Kane and Jelani Nelson Moritz Hardt and Guy Rothblum
9:35 - 9:55 From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits Impossibility of Differentially Private Universally Optimal Mechanisms
    Nitin Saxena and C. Seshadhri Hai Brenner and Kobbi Nissim
10:00 - 10:20 The Coin Problem, and Pseudorandomness for Branching Programs / Pseudorandom Generators for Regular Branching Programs The Limits of Two-Party Differential Privacy
    Joshua Brody and Elad Verbin /
Mark Braverman and Anup Rao and Ran Raz and Amir Yehudayoff
Andrew McGregor and Ilya Mironov and Toniann Pitassi and Omer Reingold and Kunal Talwar and Salil Vadhan
10:20 -10:50 Coffee Break
    Session 2A Session 2B
10:50 - 11:10 Settling the Polynomial Learnability of Mixtures of Gaussians Deciding first-order properties for sparse graphs
    Ankur Moitra and Gregory Valiant Zdenek Dvorak and Daniel Kral and Robin Thomas
11:15 - 11:35 Polynomial Learning of Distribution Families Logspace Versions of the Theorems of Bodlaender and Courcelle
    Mikhail Belkin and Kaushik Sinha Michael Elberfeld and Andreas Jakoby and Till Tantau
11:40 - 12:00 Agnostically learning under permutation invariant distributions A separator theorem in minor-closed classes
    Karl Wimmer Ken-ichi Kawarabayashi and Bruce Reed
12:05 - 12:25 Learning Convex Concepts from Gaussian Distributions with PCA Optimal stochastic planarization
    Santosh Vempala Anastasios Sidiropoulos
12:30 - 1:45 Lunch
    Session 3A Session 3B
2:00 - 2:20 Determinant Sums for Undirected Hamiltonicity Solving linear systems through nested dissection
    Andreas Björklund Noga Alon and Raphael Yuster
2:25 - 2:45 Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability Approaching optimality for solving SDD linear systems
    Rahul Santhanam Iannis Koutis and Gary L. Miller and Richard Peng
2:50 - 3:10 The Monotone Complexity of k-CLIQUE on Random Graphs Fast approximation algorithms for cut-based graph problems
    Benjamin Rossman Aleksander Madry
3:15 - 3:35 The Complexity of Distributions Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
    Emanuele Viola Konstantin Makarychev and Yury Makarychev
3:40 - 4:00 Hardness of Finding Independent Sets in Almost 3-Colorable Graphs Vertex Sparsifiers and Abstract Rounding Algorithms
    Irit Dinur and Subhash Khot and Will Perkins and Muli Safra Moses Charikar and Tom Leighton and Shi Li and Ankur Moitra
4:00 - 4:30 Coffee Break
    Session 4
4:30 - 4:50 Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
    Matthew Andrews  
4:55 - 5:15 Computational Transition at the Uniqueness Threshold
    Allan Sly  
5:20 - 6:20 Avner Magen Memorial Talk
    Toni Pitassi  
9:00 - Business Meeting
Monday, October 25  
8:00 - 8:45 Continental Breakfast
    Session 5A Session 5B
8:45 - 9:05 Clustering with Spectral Norm and the k-means Algorithm A non-linear lower bound for planar epsilon-nets
    Amit Kumar and Ravindran Kannan Noga Alon
9:10 - 9:30 Stability yields a PTAS for k-Median and k-Means Clustering The sub-exponential upper bound for on-line chain partitioning
    Pranjal Awasthi and Avrim Blum and Or Sheffet Bartłomiej Bosek and Tomasz Krawczyk
9:35 - 9:55 The Geometry of Manipulation -- a Quantitative Proof of the Gibbard-Satterthwaite Theorem Improved Bounds for Geometric Permutations
    Marcus Isaksson and Guy Kindler and Elchanan Mossel Natan Rubin and Haim Kaplan and Micha Sharir
10:00 - 10:20 Efficient volume sampling for row/column subset selection On the Queue Number of Planar Graphs
    Amit Deshpande and Luis Rademacher Giuseppe Di Battista and Fabrizio Frati and János Pach
10:20 -10:50 Coffee Break
    Session 6A Session 6B
10:50 - 11:10 Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
    Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak David Doty and Matthew J. Patitz and Dustin Reishus and Robert T. Schweller and Scott M. Summers
11:15 - 11:35 Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
    Amit Chakrabarti and Graham Cormode and Ranganath Kondapally and Andrew McGregor Jin-Yi Cai and Pinyan Lu and Mingji Xia
11:40 - 12:00 New Constructive Aspects of the Lovasz Local Lemma A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
    Bernhard Haeupler and Barna Saha and Aravind Srinivasan Jin-Yi Cai and Xi Chen
12:05 - 12:25 The Geometry of Scheduling  
    Nikhil Bansal and Kirk Pruhs  
12:30 - 1:45 Lunch
    Session 7A Session 7B
2:00 - 2:20 Sublinear Time Optimization for Machine Learning Overcoming the Hole In The Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage
    Kenneth L. Clarkson and Elad Hazan and David P. Woodruff Zvika Brakerski and Yael Tauman Kalai and Jonathan Katz and Vinod Vaikuntanathan
2:25 - 2:45 Estimating the longest increasing sequence in sublinear time Cryptography Against Continuous Memory Attacks
    Michael Saks and C. Seshadhri Yevgeniy Dodis and Kristiyan Haralambiev and Adriana Lopez-Alt and Daniel Wichs
2:50 - 3:10 Testing Properties of Sparse Images On the Insecurity of Parallel Repetition for Leakage Resilience
    Dana Ron and Gilad Tsur Allison Lewko and Brent Waters
3:15 - 3:35 A Unified Framework for Testing Linear-Invariant Properties Black-Box, Round-Efficient Secure Computation via Non-Malleability Assumption
    Arnab Bhattacharyya and Elena Grigorescu and Asaf Shapira Hoeteck Wee
3:40 - 4:00 Optimal Testing of Reed-Muller Codes Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions
    Arnab Bhattacharyya and Swastik Kopparty and Grant Schoenebeck and Madhu Sudan and David Zuckerman Ran Canetti and Huijia Lin and Rafael Pass
4:00 - 4:30 Coffee Break
    Session 8
4:30 - 4:50 Bounds on Monotone Switching Networks for Directed Connectivity
    Aaron Potechin  
4:55 - 5:15 Subexponential Algorithms for Unique Games and Related problems
    Sanjeev Arora and Boaz Barak and David Steurer  
5:20 - 6:20 Nevanlinna Prize Talk. Laplacian Gems
    Dan Spielman  
Tuesday, October 26  
8:00 - 8:45 Continental Breakfast
    Session 9A Session 9B
8:45 - 9:05 Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures On the Computational Complexity of Coin Flipping
    Chandra Chekuri and Jan Vondrak and Rico Zenklusen Hemanta K. Maji and Manoj Prabhakaran and Amit Sahai and Dan Schreiber
9:10 - 9:30 Minimum-Cost Network Design with (Dis)economies of Scale Sequential Rationality in Cryptographic Protocols
    Matthew Andrews and Spyridon Antonakopoulos and Lisa Zhang Ronen Gradwohl and Noam Livne and Alon Rosen
9:35 - 9:55 One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk An efficient test for product states, with applications to quantum Merlin-Arthur games
    Ashish Goel and Ian Post Aram W. Harrow and Ashley Montanaro
10:00 - 10:20 Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time  
    Glencora Borradaile and Piotr Sankowski and Christian Wulff-Nilsen  
10:20 -10:50 Coffee Break
    Session 10A Session 10B
10:50 - 11:10 Subcubic Equivalences Between Path, Matrix, and Triangle Problems A Fourier-analytic approach to Reed-Muller decoding
    Virginia Vassilevska Williams and Ryan Williams Parikshit Gopalan
11:15 - 11:35 Replacement Paths via Fast Matrix Multiplication Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
    Oren Weimann and Raphael Yuster Shachar Lovett and Partha Mukhopadhyay and Amir Shpilka
11:40 - 12:00 All-Pairs Shortest Paths in O(n2) Time With High Probability Matching Vector Codes /
Local list decoding with a constant number of queries
    Yuval Peres and Dmitry Sotnikov and Benny Sudakov ad Uri Zwick Zeev Dvir and Parikshit Gopalan and Sergey Yekhanin /
Avraham Ben-Aroya and Klim Efremenko and Amnon Ta-Shma
12:05 - 12:25 Approximating Maximum Weight Matching in Near-linear Time Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
    Ran Duan and Seth Pettie Venkatesan Guruswami and Adam Smith
12:30 - 1:45 Lunch
    Session 11A Session 11B
2:00 - 2:20 Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
    Renato Paes Leme and Eva Tardos Yuriy Arbitman and Moni Naor and Gil Segev
2:25 - 2:45 Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts / Frugal Mechanism Design via Spectral Techniques A lower bound for dynamic approximate membership data structures
    David Kempe and Mahyar Salek and Cristopher Moore /
Ning Chen and Edith Elkind and Nick Gravin and Fedor Petrov
Shachar Lovett and Ely Porat
2:50 - 3:10 Budget Feasible Mechanisms Lower Bounds for Near Neighbor Search via Metric Expansion
    Yaron Singer Rina Panigrahy and Kunal Talwar and Udi Wieder
3:15 - 3:35 Black-Box Randomized Reductions in Algorithmic Mechanism Design Distance Oracles Beyond the Thorup–Zwick Bound
    Shaddin Dughmi and Tim Roughgarden Mihai Pătraşcu and Liam Roditty
Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces