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