STOC 2011 Schedule  
Sunday, June 5  
18:00 - 19:15

FCRC Plenary Talk:
2010 ACM Turing Award Lecture
Leslie G. Valiant, Harvard University

19:30 - 21:30 Welcome Reception
Monday, June 6  


- 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:
IBM's Watson/DeepQA
David A. Ferruci, IBM

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: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 Sankowskiand 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:
2011 Knuth Prize Lecture
Algorithms: Recent Highlights and Challenges
Ravi Kannan, Microsoft Research

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: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 /
Mohammad Mahdian and Qiqi Yan

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:
Warehouse-Scale Computing: Entering the Teenage Decade
Luiz Andre Barroso, Google

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 /
Huijia Lin and Rafael Pass

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