| STOC 2011 Schedule | |||
| Sunday, June 5 | |||
| 18:00 | - 19:15 | FCRC Plenary Talk: |
|
| 19:30 | - 21:30 | Welcome Reception | |
| Monday, June 6 | |||
8:00 |
- 8:30 | Continental Breakfast | |
Session 1A. |
Session 1B. | ||
| Chair: David Kempe | Chair: Dieter van Melkebeek | ||
| 8:30 | - 8:50 | The Power of Simple Tabulation Hashing | Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication |
| Mihai Patrascu and Mikkel Thorup | Bo'az Klartag and Oded Regev | ||
| 8:55 | - 9:15 | Tight Bounds for Parallel Randomized Load Balancing | Strong Direct Product Theorems for Quantum Communication and Query Complexity |
| Christoph Lenzen and Roger Wattenhofer | Alexander A. Sherstov | ||
| 9:20 | - 9:40 | Social Networks Spread Rumors in Sublogarithmic Time | An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance |
| Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich | Amit Chakrabarti and Oded Regev | ||
| 9:45 | - 10:05 | Coffee Break | |
| Session 2A. | Session 2B. | ||
| Chair: Lisa Fleischer | Chair: Kobbi Nissim | ||
| 10:05 | - 10:25 | Cover times, blanket times, and majorizing measures | The Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited |
| Jian Ding and James R. Lee and Yuval Peres | Thomas Holenstein and Robin Künzler and Stefano Tessaro | ||
| 10:30 | - 10:50 | A General Framework for Graph Sparsification | Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions |
| Wai Shing Fung and Ramesh Hariharan and Nicholas J. A. Harvey and Debmalya Panigrahi | Craig Gentry and Daniel Wichs | ||
| 10:55 | - 11:15 | Breaking O(n^{1/2})-approximation algorithms for the edge-disjoint paths problem with congestion two |
Limits of Provable Security From Standard Assumptions |
| Ken-ichi Kawarabayashi and Yusuke Kobayashi | Rafael Pass | ||
| 11:30 | - 12:30 | FCRC Plenary Talk: |
|
| 12:30 | - 14:00 | Lunch | |
| Session 3A. | Session 3B. | ||
| Chair: Ittai Abraham | Chair: Amir Shpilka | ||
| 14:00 | - 14:20 | On Optimal Single-Item Auctions |
Towards Coding for Maximum Errors in Interactive Communication |
| Christos Papadimitriou and George Pierrakos | Mark Braverman and Anup Rao | ||
| 14:25 | - 14:45 | Optimal Auctions with Correlated Bidders are Easy | High-rate codes with sublinear-time decoding |
| Shahar Dobzinski and Hu Fu and Robert Kleinberg | Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin | ||
| 14:50 | - 15:10 | An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations | From Affine to Two-Source Extractors via Approximate Duality |
Shahar Dobzinski |
Eli Ben-Sasson, Noga Zewi | ||
| 15:15 | - 15:35 | From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders |
Correlation testing for affine invariant properties on $\F_p^n$ in the high error regime |
Shaddin Dughmi and Tim Roughgarden and Qiqi Yan |
Hamed Hatami and Shachar Lovett | ||
| 15:40 | - 16:05 | Coffee Break | |
| Session 4A. | Session 4B. | ||
| Chair: Eva Tardos | Chair: Dieter van Melkebeek | ||
| 16:05 | - 16:25 | Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm | Moser and Tardos meet Lovász |
| Bharat Adsul and Jugal Garg and Ruta Mehta and Milind Sohoni | Kashyap Kolipaka and Mario Szegedy | ||
| 16:30 | - 16:50 | Exact Algorithms for Solving Stochastic Games |
A Full Derandomization of Schoening's k-SAT Algorithm |
| Kristoffer Arnsfelt Hansen and Michal Koucký and Niels Lauritzen and Peter Bro Miltersen and Elias P. Tsigaridas | Robin A. Moser and Dominik Scheder | ||
| 16:55 | - 17:15 | Dueling algorithms |
Pseudorandom Generators for Combinatorial Shapes |
| Nicole Immorlica and Adam Tauman Kalai and Brendan Lucier and Ankur Moitra and Andrew Postlewaite and Moshe Tennenholtz | Parikshit Gopalan and Raghu Meka and Omer Reingold and David Zuckerman | ||
| 17:20 | - 17:40 | Pareto Optimal Solutions for Smoothed Analysts | Pseudorandom Generators for Group Products |
| Ankur Moitra and Ryan O'Donnell | Michal Koucky and Prajakta Nimbhorkar and Pavel Pudlak | ||
| 20:30 | - 22:30 | Poster Session | |
| Tuesday, June 7 | |||
8:00 |
- 8:30 | Continental Breakfast | |
Session 5. |
|||
| Chair: Salil Vadhan | |||
| 8:30 | - 8:50 | Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs | |
| Paul Christiano and Jonathan A. Kelner and Aleksander Madry and Daniel A. Spielman and Shang-Hua Teng | |||
| 8:55 | - 9:15 | Subexponential lower bounds for randomized pivoting rules for the simplex algorithm |
|
| Oliver Friedmann and Thomas Dueholm Hansen and Uri Zwick | |||
| 9:20 | - 9:40 | Analyzing Network Coding Gossip Made Easy | |
| Bernhard Haeupler | |||
| 9:45 | - 10:05 | Coffee Break | |
| Session 6A. | Session 6B. | ||
| Chair: Seth Pettie | Chair: Frederic Magniez | ||
| 10:05 | - 10:25 | An Algorithm for the Graph Crossing Number Problem |
The Computational Complexity of Linear Optics |
| Julia Chuzhoy | Scott Aaronson and Alex Arkhipov | ||
| 10:30 | - 10:50 | Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs |
A quasipolynomial-time algorithm for the quantum separability problem |
| Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen | Fernando Brandao and Matthias Christandl and Jon Yard | ||
| 10:55 | - 11:15 | Directed Spanners via Flow-Based Linear Programs |
Parallel Repetition of Entangled Games |
| Michael Dinitz and Robert Krauthgamer | Julia Kempe and Thomas Vidick | ||
| 11:30 | - 12:30 | FCRC Plenary Talk: |
|
| 12:30 | - 14:00 | Lunch | |
| Session 7A. | Session 7B. | ||
| Chair: Ittai Abraham | Chair: Amir Shpilka | ||
| 14:00 | - 14:20 | Distributed Verification and Hardness of Distributed Approximation | An LLL-Reduction Algorithm with Quasi-linear Time Complexity |
| Atish Das Sarma and Stephan Holzer and Liah Kor and Amos Korman and Danupon Nanongkai and Gopal Pandurangan and David Peleg and Roger Wattenhofer | Andrew Novocin and Damien Stehlé and Gilles Villard | ||
| 14:25 | - 14:45 | Linearizable Implementations Do Not Suffice for Randomized Distributed Computation | NP-Hardness of Approximately Solving Linear Equations Over Reals |
Wojciech Golab and Lisa Higham and Philipp Woelfel |
Subhash Khot and Dana Moshkovitz | ||
| 14:50 | - 15:10 | The Topology of Wireless Communication |
Black-Box Identity Testing of Depth-4 Multilinear Circuits |
| Erez Kantor and Zvi Lotker and Merav Parter and David Peleg | Shubhangi Saraf and Ilya Volkovich | ||
| 15:15 | - 15:35 | Optimal Path Search in Small Worlds: Dimension Matters | Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter |
| George Giakkoupis and Nicolas Schabanel | Nitin Saxena and C. Seshadhri | ||
| 15:40 | - 16:05 | Coffee Break | |
| Session 8A. | Session 8B. | ||
| Chair: Seth Pettie | Chair: Venkatesan Guruswami | ||
| 16:05 | - 16:25 | Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications |
On the Complexity of Powering in Finite Fields |
| Erik Demaine and Mohammad Hajiaghayi and Ken-ichi Kawarabayashi | Swastik Kopparty | ||
| 16:30 | - 16:50 | A simpler algorithm and shorter proof for the graph minor decomposition |
Almost Settling the Hardness of Noncommutative Determinant |
| Ken-ichi Kawarabayashi and Paul Wollan | Steve Chien and Prahladh Harsha and Alistair Sinclair and Srikanth Srinivasan | ||
| 16:55 | - 17:15 | Multicut is FPT / Fixed-parameter tractability of multicut parameterized by the size of the cutset |
Geometric Complexity Theory and Tensor Rank |
Nicolas Bousquet and Jean Daligault and Stéphan Thomassé / Dániel Marx and Igor Razgon |
Peter Buergisser and Christian Ikenmeyer | ||
| 17:20 | - 17:40 | Finding topological subgraphs is fixed-parameter tractable | Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes |
| Martin Grohe and Ken-ichi Kawarabayashi and Dániel Marx and Paul Wollan | Boaz Barak and Zeev Dvir and Avi Wigderson and Amir Yehudayoff | ||
| 21:00 | - 23:00 | Business Meeting | |
| Wednesday, June 8 | |||
8:00 |
- 8:30 | Continental Breakfast | |
| Session 9A. | Session 9B. | ||
| Chair: Allan Borodin | Chair: Kasturi Varadarajan | ||
| 8:30 | - 8:50 | Mechanisms for (Mis)allocating Scientific Credit |
Don't Rush into a Union: Take Time to Find Your Roots |
| Jon Kleinberg and Sigal Oren | Mihai Patrascu and Mikkel Thorup | ||
| 8:55 | - 9:15 | Inner Product Spaces for MinSum Coordination Mechanisms |
A Unified Framework for Approximating and Clustering Data |
Richard Cole and Jose R. Correa and Vasilis Gkatzelis and Vahab Mirrokni and Neil Olver |
Dan Feldman and Michael Langberg | ||
| 9:20 | - 9:40 | Mechanism design with uncertain inputs (to err is human, to forgive divine) |
Approximate Polytope Membership Queries |
| Uriel Feige and Moshe Tennenholtz | Sunil Arya and Guilherme D. da Fonseca and David M. Mount | ||
| 9:45 | - 10:05 | Coffee Break | |
| Session 10A. | Session 10B. | ||
| Chair: Avrim Blum | Chair: Venkatesan Guruswami | ||
| 10:05 | - 10:25 | Online Bipartite Matching with Unknown Distributions / Online Bipartite Matching with Random Arrivals: An Approach Based on Strongly Factor-Revealing LPs |
K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance |
Chinmay Karande and Aranyak Mehta and Pushkar Tripathi / |
Piotr Indyk and Eric Price | ||
| 10:30 | - 10:50 | Almost Tight Bounds for Reordering Buffer Management |
Breaking the $k^2$ barrier for explicit RIP matrices |
| Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald Raecke | Jean Bourgain, S. J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova | ||
| 10:55 | - 11:15 | Santa Claus Schedules Jobs on Unrelated Machines |
Deterministic Construction of a High Dimensional l_p Section in l_1^n for any p<2 |
| Ola Svensson | Zohar S. Karnin | ||
| 11:30 | - 12:30 | FCRC Plenary Talk: |
|
| 12:30 | - 14:00 | Lunch | |
| Session 11A. | Session 11B. | ||
| Chair: Ryan Williams | Chair: Moni Naor | ||
| 14:00 | - 14:20 | Schaefer's Theorem for Graphs | Constant Round Non-Malleable Protocols using One Way Functions / Constant-Round Non-Malleable Commitments from Any One-Way Function |
| Manuel Bodirsky and Michael Pinsker | Vipul Goyal / |
||
| 14:25 | - 14:45 | Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP | Secure Computation with Information Leaking to an Adversary |
| Yuichi Yoshida | Miklos Ajtai | ||
| 14:50 | - 15:10 | Every Property of Hyperfinite Graphs is Testable |
How to Leak on Key Updates |
| Ilan Newman and Christian Sohler | Allison Lewko and Mark Lewko and Brent Waters | ||
| 15:15 | - 15:35 | Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs |
Near-Optimal Private Approximation Protocols via a Black-Box Transformation |
| Gregory Valiant and Paul Valiant | David P. Woodruff | ||
| 15:40 | - 16:05 | Coffee Break | |
| Session 12A. | Session 12B. | ||
| Chair: Alexandr Andoni | Chair: Kobbi Nissim | ||
| 16:05 | - 16:25 | Fast Moment Estimation in Data Streams in Optimal Space | Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes |
| Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff | Chandra Chekuri and Jan Vondrák and Rico Zenklusen | ||
| 16:30 | - 16:50 | Subspace Embeddings for the L_1-norm with Applications |
Learning Submodular Functions |
| Christian Sohler and David Woodruff | Maria Florina Balcan and Nicholas J. A. Harvey | ||
| 16:55 | - 17:15 | Near-optimal distortion bounds for embedding doubling spaces into L_1 | Privately Releasing Conjunctions and the Statistical Query Barrier |
| James R. Lee and Anastasios Sidiropoulos | Anupam Gupta and Moritz Hardt and Aaron Roth and Jonathan Ullman | ||
| 17:20 | - 17:40 | From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking | Privacy-preserving Statistical Estimation with Optimal Convergence Rates |
| Omar Fawzi and Patrick Hayden and Pranab Sen | Adam Smith | ||