| FOCS 2010 Schedule | |||
| Saturday, October 23 | |||
| 11:00 | -12:30 | Tutorial 1: Ketan Mulmuley. Geometric Complexity Theory (GCT). Ballrooms 1 and 2. | |
| 12:30 | - 1:45 | Lunch (On your own) | |
| 1:45 | - 3:15 | Tutorial 2: Mihai Pătraşcu. How to Grow Your Lower Bounds. Ballrooms 1 and 2. | |
| 3:30 | - 5:00 | Tutorial 3: Tim Roughgarden. How To Think About Mechanism Design. Ballrooms 1 and 2. | |
| 6:00 | - 9:00 | Welcoming Reception. Ballroom 4. | |
| Sunday, October 24 | |||
| 8:00 | - 8:45 | Continental Breakfast. Foyer. | |
| Session 1A. Ballrooms 1 and 2. | Session 1B. Ballroom 3. | ||
| 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 Interactive 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. Foyer. | |
| Session 2A. Ballrooms 1 and 2. | Session 2B. Ballroom 3. | ||
| 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. Ballrooms 4 and 5. | |
| Session 3A. Ballrooms 1 and 2. | Session 3B. Ballroom 3. | ||
| 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. Foyer. | |
| Session 4. Ballrooms 1 and 2. | |||
| 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. Ballrooms 1 and 2. | |
| Monday, October 25 | |||
| 8:00 | - 8:45 | Continental Breakfast. Foyer. | |
| Session 5A. Ballrooms 1 and 2. | Session 5B. Ballroom 3. | ||
| 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. Foyer. | |
| Session 6A. Ballrooms 1 and 2. | Session 6B. Ballroom 3. | ||
| 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. Ballrooms 4 and 5. | |
| Session 7A. Ballrooms 1 and 2. | Session 7B. Ballroom 3. | ||
| 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 | From Standard to Adaptive Hardness And Composable Security With No Set-Up |
| 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. Foyer. | |
| Session 8. Ballrooms 1 and 2. | |||
| 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. Foyer. | |
| Session 9A. Ballrooms 1 and 2. | Session 9B. Ballroom 3.. | ||
| 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. Foyer. | |
| Session 10A. Ballrooms 1 and 2. | Session 10B. Ballroom 3.. | ||
| 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. Ballrooms 4 and 5. | |
| Session 11A. Ballrooms 1 and 2. | Session 11B. Ballroom 3.. | ||
| 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 | ||