STOC2010

(CC) "Calm by the river today" by Pear Biter/flickr

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 —