Conference Program
Saturday, June 5th at Microsoft Research
The STOC 2010 tutorials are being hosted at Microsoft New England Research and Development Center in Cambridge MA at One Memorial Drive, Cambridge MA. For direction and maps click here.
Tutorial Day
| Saturday, June 5, 2010 | ||
|---|---|---|
|
9:00- 9:30 |
— Registration — (1st floor) | |
|
9:30- 11:30 |
Chair: P. Gopalan Spectral Methods for Matrices and Tensors (Click to view video) Ravindran Kannan (Microsoft Research Lab, India) |
|
|
11:30- 1:00 |
— Lunch — |
|
|
1:00- 3:00 |
Chair: R. Kleinberg Are Many Small Sets Explicitly Small? (Click to view video) Michel Talagrand (Universite Paris VI) |
|
|
3:00-
3:30 |
— Break — | |
|
3:30-
5:30 |
Chair: P. Indyk Message Passing Algorithms: a Success Looking for Theoreticians (Click to view video) Andrea Montanari (Stanford University) |
|
|
5:30- 6:00 |
— Travel to Hyatt — | |
|
6:00- 9:00 |
Opening Reception at Hyatt Regency | |
Sunday, June 6th at Hyatt Regency
| Sunday, June 6 | ||
|---|---|---|
| 7:45-8:45 | — Registration and Continental Breakfast — (Ballroom Foyer) | |
|
Session 1A Chair: K. Clarkson (Ballroom AB) |
Session 1B Chair: O. Regev (Ballroom CD) |
|
| 8:45-9:05 |
Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
Ashish Goel, Michael Kapralov and Sanjeev Khanna |
How to Compress Interactive Communication
Boaz Barak , Mark Braverman, Xi Chen and Anup Rao |
| 9:10-9:30 |
Extensions and Limits to Vertex Sparsification
Tom Leighton and Ankur Moitra |
A Strong Direct Product Theorem for Disjointness
Hartmut Klauck |
| 9:35-9:55 |
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
Alexandra Kolla, Yury Makarychev, Amin Saberi and Shang-Hua Teng |
Hardness Amplification in Proof Complexity Paul Beame, Trinh Huynh and Toniann Pitassi |
| 9:55-10:25 | — Coffee break — | |
|
Session 2A Chair: R. Kleinberg (Ballroom AB) |
Session 2B Chair: A. Russell (Ballroom CD) |
|
| 10:25-10:45 |
Load Balancing and Orientability Thresholds for Random Hypergraphs Pu Gao and Nicholas Wormald |
A Full Characterization of Quantum Advice Scott Aaronson and Andrew Drucker |
| 10:50-11:10 |
Combinatorial Approach to the Interpolation Method and Scaling Limits in Sparse
Random Graphs Mohsen Bayati, David Gamarnik and Prasad Tetali |
BQP and the Polynomial Hierarchy
Scott Aaronson |
| 11:15-11:35 |
The Maximum Multiflow Problems with Bounded Fractionality Hiroshi Hirai |
A Quantum Lovasz Local Lemma
Andris Ambainis, Julia Kempe and Or Sattath |
| 11:40-12:00 |
Faster Approximation Schemes for Fractional Multicommodity Flow Problems via
Dynamic Graph Algorithms Aleksander Madry |
Near-Optimal Extractors against Quantum Storage
Anindya De and Thomas Vidick |
| 12:00-1:30 |
— Lunch —
(Riverside Pavilion) |
|
|
Session 3A Chair: Y. T. Kalai (Ballroom AB) |
Session 3B Chair: P. Indyk (Ballroom CD) |
|
| 1:30-1:50 |
Public-Key Cryptography from Different Assumptions
Benny Applebaum , Boaz Barak and Avi Wigderson |
Detecting High Log-Densities -- an O(n1/4) Approximation for Densest
k-Subgraph
Aditya Bhaskara, Moses Charikar , Eden Chlamtac, Uriel Feige and Aravindan Vijayaraghavan |
| 1:55-2:15 |
Oblivious RAMs without Cryptographic Assumptions
Miklos Ajtai |
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded
Treewidth
MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Dániel Marx |
| 2:20-2:40 |
On the Round Complexity of Covert Computation
Vipul Goyal and Abhishek Jain |
Optimal Homologous Cycles, Total Unimodularity, and Linear Programming
Tamal K. Dey, Anil N. Hirani and Bala Krishnamoorthy |
| 2:40-3:00 |
— Coffee Break —
|
|
|
Session 4A Chair: V. Kabanets (Ballroom AB) |
Session 4B Chair: P. Gopalan (Ballroom CD) |
|
| 3:00-3:20 |
Improving Exhaustive Search Implies Superpolynomial Lower Bounds
Ryan Williams |
Recognizing Well-Parenthesized Expressions in the Streaming Model
Frederic Magniez, Claire Mathieu and Ashwin Nayak |
| 3:25-3:45 |
On the Complexity of Circuit Satisfiability Ramamohan Paturi and Pavel Pudl\'ak |
Measuring Independence of Datasets Vladimir Braverman and Rafail Ostrovsky |
| 3:50-4:10 |
Satisfiability Allows No Nontrivial Sparsification Unless the Polynomial-Time
Hierarchy Collapses
Holger Dell and Dieter van Melkebeek |
Zero-One Frequency Laws Vladimir Braverman and Rafail Ostrovsky |
| 4:10-4:30 | — Coffee break — | |
|
Session 5A Chair: C. Daskalakis (Ballroom AB) |
Session 5B Chair: L. J. Schulman (Ballroom CD) |
|
| 4:30-4:50 |
Budget Constrained Auctions with Heterogeneous Items
Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi and Kamesh Munagala |
Saving Space by Algebraization
Daniel Lokshtanov and Jesper Nederlof |
| 4:55-5:15 |
Bayesian Algorithmic Mechanism Design Jason D. Hartline and Brendan Lucier |
On the Structure of Cubic and Quartic Polynomials Elad Haramaty and Amir Shpilka |
| 5:20-5:40 |
Multi-Parameter Mechanism Design and Sequential Posted Pricing
Shuchi Chawla, Jason Hartline, David Malec and Balasubramanian Sivan |
A Sparse Johnson-Lindenstrauss Transform Anirban Dasgupta, Ravi Kumar and Tamas Sarlos |
| 8:30-10:00 |
— Business Meeting — (Ballroom AB) |
|
Monday, June 7th at Hyatt Regency
| Monday, June 7, 2010 | ||
|---|---|---|
| 7:45-8:45 | — Registration and Continental Breakfast — (Ballroom Foyer) | |
|
Session 6A Chair: P. Indyk (Ballroom AB) |
Session 6B Chair: C. Daskalakis (Ballroom CD) |
|
| 8:45-9:05 |
A Deterministic Single Exponential Time Algorithm for Most Lattice Problems
based on Voronoi Cell Computations
Daniele Micciancio and Panagiotis Voulgaris |
Improved Algorithms for Computing Fisher's Market Clearing Prices
James B. Orlin |
| 9:10-9:30 |
Sorting under Partial Information (without the Ellipsoid Algorithm)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël Jungers and J. Ian Munro |
On the Searchability of Small-World Networks with Arbitrary Underlying Structure
Pierre Fraigniaud and George Giakkoupis |
| 9:35-9:55 |
Matroid Matching: the Power of Local Search
Jon Lee, Maxim Sviridenko and Jan Vondrak |
Almost Tight Bounds for Rumour Spreading with Conductance
Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi |
| 9:55-10:25 | — Coffee break — | |
|
Session 7A Chair: V. Kabanets (Ballroom AB) |
Session 7B Chair: P. Gopalan (Ballroom CD) |
|
| 10:25-10:45 |
On the List-Decodability of Random Linear Codes
Venkatesan Guruswami, Johan Håstad and Swastik Kopparty |
The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the
External Memory Model
Elad Verbin and Qin Zhang |
| 10:50-11:10 |
Local List-Decoding and Testing of Random Linear Codes from High-Error
Swastik Kopparty and Shubhangi Saraf |
Maintaining a Large Matching or a Small Vertex Cover
Krzysztof Onak and Ronitt Rubinfeld |
| 11:15-11:35 |
Pseudorandom Generators for Polynomial Threshold Functions
Raghu Meka and David Zuckerman |
Connectivity Oracles for Failure Prone Graphs
Seth Pettie and Ran Duan |
| 11:40-12:00 |
Efficiency Improvements in Constructing Pseudorandom Generators from One-Way
Functions
Iftach Haitner, Omer Reingold and Salil Vadhan |
Approximate Sparse Recovery: Optimizing Time and Measurements
Anna Gilbert, Yi Li, Ely Porat and Martin Strauss |
| 12:00-1:30 |
— Lunch —
(Riverside Pavilion) |
|
|
Session 8A Chair: K. Clarkson (Ballroom AB) |
Session 8B Chair: O. Regev (Ballroom CD) |
|
| 1:30-1:50 |
The HOM problem is Decidable
Guillem Godoy, Omer Giménez, Lander Ramos and Carme Àlvarez |
Optimal Bounds for Sign-Representing the Intersection of Two Halfspaces by
Polynomials
Alexander A. Sherstov |
| 1:55-2:15 |
Complexity Theory for Operators in Analysis
Akitoshi Kawamura and Stephen Cook |
Bounding the Average Sensitivity and Noise Sensitivity of Polynomial Threshold
Functions
Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio and Li-Yang Tan |
| 2:20-2:40 |
Solving Polynomial Equations in Smoothed Polynomial Time and a Near Solution to
Smale's 17th Problem
Peter Buergisser and Felipe Cucker |
An Invariance Principle For Polytopes
Prahladh Harsha, Adam Klivans and Raghu Meka |
| 2:45-3:05 |
Distributed Computation in Dynamic Networks
Fabian Kuhn, Nancy Lynch and Rotem Oshman |
Efficiently Learning Mixtures of Two Gaussians
Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant |
| 3:05-3:25 |
— Coffee Break —
|
|
|
Session 9 Chair: L. J. Schulman (Ballroom CD) |
||
| 3:25-3:45 |
Augmenting Undirected Node-Connectivity by One
Laszlo A. Vegh |
|
| 3:50-4:10 |
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous |
|
| 4:15-4:35 |
An Improved LP-based Approximation for Steiner Tree
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoss and Laura Sanita |
|
| 4:35-4:55 | — Coffee break — | |
|
Session 10:
Knuth Prize Lecture Chair: M. Yannakakis (Ballroom CD) |
||
| 4:55-5:55 |
Approximation Algorithms in Theory and Practice
David S. Johnson (ATT Labs -- Research) |
|
Tuesday, June 8th at Hyatt
| Tuesday, June 8, 2010 | ||
|---|---|---|
| 7:45-8:45 | — Registration and Continental Breakfast — (Ballroom Foyer) | |
|
Session 11A Chair: P. Indyk (Ballroom AB) |
Session 11B Chair: R. Kleinberg (Ballroom CD) |
|
| 8:45-9:05 |
Changing Base without Losing Space
Yevgeniy Dodis, Mihai Pastrascu and Mikkel Thorup |
Bilipschitz Snowflakes, Metrics of Negative Type, and PSD flows James R. Lee and Mohammad Moharrami |
| 9:10-9:30 |
Towards Polynomial Lower Bounds for Dynamic Problems
Mihai Patrascu |
Approximations for the Isoperimetric and Spectral Profile of Graphs and Related
Parameters
Prasad Raghavendra, David Steurer and Prasad Tetali |
| 9:35-9:55 |
An Optimal Ancestry Scheme and Small Universal Posets Pierre Fraigniaud and Amos Korman |
Weighted Geometric Set Cover via Quasi-Uniform Sampling
Kasturi Varadarajan |
| 9:55-10:25 | — Coffee break — | |
|
Session 12A Chair: V. Kabanets (Ballroom AB) |
Session 12B Chair: Y. T. Kalai (Ballroom CD) |
|
| 10:25-10:45 |
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top
Fan-In Zohar S. Karnin, Partha Mukhopadhyay, Amir Shpilka and Ilya Volkovich |
A Shorter Proof of the Graph Minor Algorithm - The Unique Linkage Theorem Ken-ichi Kawarabayashi and Paul Wollan |
| 10:50-11:10 |
Tensor-Rank and Lower Bounds for Arithmetic Formulas Ran Raz |
Odd Cycle Packing Ken-ichi Kawarabayashi and Bruce Reed |
| 11:15-11:35 |
Non-Commutative Circuits and the Sum-of-Squares Problem Pavel Hrubes, Avi Wigderson and Amir Yehudayoff |
On the Geometry of Differential Privacy Moritz Hardt and Kunal Talwar |
| 11:40-12:00 |
On the Hardness of the Noncommutative Determinant
Vikraman Arvind and Srikanth Srinivasan |
Differential Privacy Under Continual Observation Cynthia Dwork, Moni Naor, Toniann Pitassi and Guy Rothblum |
| 12:00-1:30 |
— Lunch —
(Riverside Pavilion) |
|
|
Session 13A Chair: O. Regev (Ballroom AB) |
Session 13B Chair: K. Clarkson (Ballroom CD) |
|
| 1:30-1:50 |
On the Complexity of #CSP Martin Dyer and David Richerby |
The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries
Aaron Roth and Tim Roughgarden |
| 1:55-2:15 |
Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive
Queries Dániel Marx |
The Price of Privately Releasing Contingency Tables and the Spectra of Random
Matrices with Correlated Rows Shiva Kasiviswanathan, Mark Rudelson, Adam Smith and Jonathan Ullman |
| 2:20-2:40 |
Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
Ola Svensson |
Privacy Amplification with Asymptotically Optimal Entropy Loss Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky and Leonid Reyzin |
| 2:45-3:05 |
Graph Expansion and the Unique Games Conjecture Prasad Raghavendra and David Steurer |
|
| 3:05 PM |
— End of Conference — |
|
