STOC 2009

Update! The Business Meeting on Sunday has been delayed (to provide more time for dinner). It will be from 8:30-10:00pm.

Here is a printable version of this program.

Conference Information

All events will take place in the Hyatt Regency Bethesda. The meeting rooms are located on the Ballroom Level of the Hotel (two levels below the main lobby). Coffee breaks and the continental breakfasts will be served in the Ballroom Foyer, on the Ballroom Level. The Cartier/Tiffany rooms will be used as a breakout area.

Registration Desk

The registration desk will be in the Haverford Foyer, two levels below the main lobby. It will be open Saturday from 6:00pm-8:00pm and Sun-Tue from 7:30am-6:00pm.

Internet Access

Wireless internet access will be available in the Cartier/Tiffany room, the Ballroom Foyer, and the Crystal Ballroom (all on the Ballroom Level). Information on accessing the wireless will be available at the registration desk.


Due to space limitations, lunches will be split between two rooms. Attendees may go to either room.

  • Concours Terrace, located one level above the main lobby in the center of the main atrium of the Hotel.
  • Diplomat/Ambassador rooms, located on the Conference Level, one level above the ballroom.

Conference Program

                    Saturday, May 30
9:15am-5:45pm — Les Valiant 60th Birthday Celebration —
(Embassy/Chesapeake Suites)
6:00pm-8:00pm — Registration and Welcome Reception —
(Registration: Haverford Foyer)   (Reception: Concours Terrace)

                    Sunday, May 31
7:30-8:30 — Registration and Continental Breakfast — (Ballroom Foyer)
Chair: Rocco Servedio
Complexity I
Chair: Chris Umans
8:30-8:50 Message Passing Algorithms and Improved LP Decoding
S. Arora, C. Daskalakis and D. Steurer
Exact Learning of Random DNF Formulas Under the Uniform Distribution
Linda Sellie
8:55-9:15 List Decoding Tensor Products and Interleaved codes
P. Gopalan, V. Guruswami and P. Raghavendra
Polynomial-time Theory of Matrix Groups
L. Babai, R. M. Beals and Á. Seress
9:20-9:40 Artin Automorphisms, Cyclotomic Function Fields, and Folded List-decodable Codes
Venkatesan Guruswami
Affine Dispersers from Subspace Polynomials
Eli Ben-Sasson and Swastik Kopparty
9:45-10:05 A Deterministic Reduction for the Gap Minimum Distance Problem
Qi Cheng and Daqing Wan
On Oblivious PTAS for Nash Equilibrium
C. Daskalakis and C. H. Papadimitriou
10:10-10:30 (Empty) The Extended BG-Simulation and the Characterization of t-Resiliency
Eli Gafni
10:30-11:00 — Coffee break —
  Algorithms and Data Structures
Chair: Ravi Kumar
Property Testing
Chair: Anup Rao
11:00-11:20 An Efficient Algorithm for Partial Order Production
J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers and J. Ian Munro
Direct Product Testing: Improved and Derandomized
R. Impagliazzo, V. Kabanets and A. Wigderson
11:25-11:45 A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges
Aaron Bernstein and David Karger
On Proximity Oblivious Testing
Oded Goldreich and Dana Ron
11:50-12:10 Distributed (Δ+1)-Coloring in Linear (in Δ) Time
Leonid Barenboim and Michael Elkin
Testing Juntas Nearly Optimally
Eric Blais
12:15-12:35 Near-Perfect Load Balancing by Randomized Rounding
Tobias Friedrich and Thomas Sauerwald
Green's Conjecture and Testing Linear-Invariant Properties
Asaf Shapira
12:40-2:10 — Lunch —
(Concours Terrace and Diplomat/Ambassador)
2:10-3:20 Athena Lecture
Shafi Goldwasser
Cryptography without (hardly any) Secrets?
Chair: Cynthia Dwork — (Haverford/Baccarat)
3:20-3:50 — Coffee break —
  Crypto I
Chair: Shafi Goldwasser
Approximation Algorithms I
Chair: Nikhil Bansal
3:50-4:10 Fully Homomorphic Encryption Using Ideal Lattices
Craig Gentry
Approximating Edit Distance in Near-Linear Time
Alexandr Andoni and Krzysztof Onak
4:15-4:35 A Unified Framework for Concurrent Security: Universal Composability from Stand-alone Non-malleability
H. Lin, R. Pass and M. Venkitasubramaniam
Numerical Linear Algebra in the Streaming Model
Kenneth L. Clarkson and David P. Woodruff
4:40-5:00 Non-Malleability Amplification
Huijia Lin and Rafael Pass
A Fast and Efficient Algorithm for Low-rank Approximation of a Matrix
Nam H. Nguyen, Thong T. Do and Trac D. Tran
5:05-5:25 3-Query Locally Decodable Codes of Subexponential Length
Klim Efremenko
An Improved Constant-Time Approximation Algorithm for Maximum Matchings
Yuichi Yoshida, Masaki Yamamoto and Hiro Ito
8:30-10:00 — Business Meeting —

                    Monday, June 1
7:30-8:45 — Registration and Continental Breakfast — (Ballroom Foyer)
  Graph Cuts and Flows
Chair: Chris Umans
Chair: Rocco Servedio
8:45-9:05 Finding Sparse Cuts Locally Using Evolving Sets
Reid Andersen and Yuval Peres
Integrality Gaps for Sherali-Adams Relaxations
M. Charikar, K. Makarychev and Y. Makarychev
9:10-9:30 On the Geometry of Graphs with a Forbidden Minor
James R. Lee and Anastasios Sidiropoulos
Sherali-Adams Relaxations of the Matching Polytope
Claire Mathieu and Alistair Sinclair
9:35-9:55 Twice-Ramanujan Sparsifiers
J. D. Batson, D. A. Spielman and N. Srivastava
CSP Gaps and Reductions in the Lasserre Hierarchy
Madhur Tulsiani
10:00-10:20 Max Cut and the Smallest Eigenvalue
Luca Trevisan
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems
Marek Karpinski and Warren Schudy
10:25-10:45 Homology Flows, Cohomology Cuts
Erin W. Chambers, Jeff Erickson and Amir Nayyeri
Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
J. Lee, V. S. Mirrokni, V. Nagarajan and M. Sviridenkos
10:45-11:15 — Coffee break —
  Award Papers — Chair: Michael Mitzenmacher
11:15-11:40 Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
Chris Peikert
11:40-12:05 A Constructive Proof of the Lovász Local Lemma
Robin A. Moser
12:05-1:30 — Lunch —
(Concours Terrace and Diplomat/Ambassador)
Chair: Ravi Kumar
Chair: Anup Rao
1:30-1:50 Universally Utility-Maximizing Privacy Mechanisms
A. Ghosh, T. Roughgarden and M. Sundararajan
Quantum Algorithms Using the Curvelet Transform
Yi-Kai Liu
1:55-2:15 Private Coresets
Dan Feldman, Amos Fiat, Haim Kaplan and Kobbi Nissim
Short Seed Extractors against Quantum Storage
Amnon Ta-Shma
2:20-2:40 Differential Privacy and Robust Statistics
Cynthia Dwork and Jing Lei
Efficient Discrete-time Simulations of Continuous-time Quantum Query Algorithms
R. Cleve, D. Gottesman, M. Mosca, R. Somma and D. Yonge-Mallo
2:45-3:05 On the Complexity of Differentially Private Data Release
C. Dwork, M. Naor, O. Reingold, G. Rothblum and S. Vadhan
The Detectability Lemma and Quantum Gap Amplification
D. Aharonov, I. Arad, Z. Landau and U. Vazirani
3:05-3:35 — Coffee break —
Chair: Rasmus Pagh
Complexity II
Chair: Jonathan Katz
3:35-3:55 Affiliation Networks
Silvio Lattanzi and D. Sivakumar
On the Complexity of Communication Complexity
Eyal Kushilevitz and Enav Weinreb
4:00-4:20 Fault-Tolerant Spanners for General Graphs
S. Chechik, M. Langberg, D. Peleg and L. Roditty
Bit-Probe Lower Bounds for Succinct Data Structures
Emanuele Viola
4:25-4:45 Hadwiger's Conjecture is Decidable
Ken-ichi Kawarabayashi and Bruce Reed
Randomly Supported Independence and Resistance
Per Austrin and Johan Håstad
4:50-5:10 Finding, Minimizing, and Counting Weighted Subgraphs
Virginia Vassilevska and Ryan Williams
Conditional Hardness for Satisfiable-3CSPs
Ryan O'Donnell and Yi Wu

                    Tuesday, June 2
7:30-8:45 — Registration and Continental Breakfast — (Ballroom Foyer)
Chair: Nicole Immorlica
Markov Chains
Chair: Michael Mitzenmacher
8:45-9:05 A New Approach to Auctions and Resilient Mechanism Design
Jing Chen and Silvio Micali
How Long Does it Take to Catch a Wild Kangaroo?
Ravi Montenegro and Prasad Tetali
9:10-9:30 Intrinsic Robustness of the Price of Anarchy
Tim Roughgarden
Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming
Ravi Kannan and Hariharan Narayanan
9:35-9:55 On the Convergence of Regret Minimization Dynamics in Concave Games
Eyal Even-Dar, Yishay Mansour and Uri Nadav
Mixing Time for the Solid-on-Solid Model
Fabio Martinelli and Alistair Sinclair
10:00-10:20 Multiplicative Updates Outperform Generic No-regret Learning in Congestion Games
Robert Kleinberg, Georgios Piliouras and Eva Tardos
Reconstruction for the Potts Model
Allan Sly
10:25-10:45 MaxMin Allocation via Degree Lower-bounded Arborescences
M. Bateni, M. Charikar and V. Guruswami
Tight Lower Bounds for Greedy Routing in Uniform Small World Rings
Martin Dietzfelbinger and Philipp Woelfel
10:45-11:15 — Coffee break —
  Crypto II
Chair: Jonathan Katz
Chair: Rasmus Pagh
11:15-11:35 Non-Malleable Extractors and Symmetric Key Cryptography from Weak Secrets
Yevgeniy Dodis and Daniel Wichs
Every Planar Graph is the Intersection Graph of Segments in the Plane
Jeremie Chalopin and Daniel Goncalves
11:40-12:00 Inaccessible Entropy
I. Haitner, O. Reingold, S. Vadhan and H. Wee
Small-size ε-nets for Axis-Parallel Rectangles and Boxes
Boris Aronov, Esther Ezra and Micha Sharir
12:05-12:25 On Cryptography with Auxiliary Input
Yevgeniy Dodis, Yael Tauman Kalai and Shachar Lovett
Explicit Construction of a Small ε-net for Linear Threshold Functions
Yuval Rabani and Amir Shpilka
12:30-2:00 — Lunch —
(Concours Terrace and Diplomat/Ambassador)
  Approximation Algorithms II
Chair: Michael Mitzenmacher
Complexity III
Chair: Jonathan Kelner
2:00-2:20 A Constant-Factor Approximation for Stochastic Steiner Forest
Anupam Gupta and Amit Kumar
An Axiomatic Approach to Algebrization
R. Impagliazzo, V. Kabanets and A. Kolokolova
2:25-2:45 Multiple Intents Re-Ranking
Yossi Azar, Iftah Gamzu and Xiaoxin Yin
Random Graphs and the Parity Quantifier
Phokion Kolaitis, Swastik Kopparty
2:50-3:10 A Competitive Algorithm for Minimizing Weighted Flow Time on Unrelated Machines with Speed Augmentation
J. S. Chadha, N. Garg, A. Kumar and V. N. Muralidhara
Holant Problems and Counting CSP
Jin-Yi Cai, Pinyan Lu and Mingji Xia
3:15-3:35 Online and Stochastic Survivable Network Design
Anupam Gupta, Ravishankar Krishnaswamy and R. Ravi
A New Line of Attack on the Dichotomy Conjecture
Gabor Kun and Mario Szegedy
3:35 — Conference Ends —

-   STOC 2009 Home   -