|
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.
Lunches
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) |
| |
Codes
Chair: Rocco Servedio
(Haverford/Baccarat) |
Complexity I
Chair: Chris Umans
(Waterford/Lalique) |
| 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
(Haverford/Baccarat) |
Property Testing
Chair: Anup Rao
(Waterford/Lalique) |
| 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
(Haverford/Baccarat) |
Approximation Algorithms I
Chair: Nikhil Bansal
(Waterford/Lalique) |
| 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 —
(Haverford/Baccarat) |
|
Monday, June 1 |
| 7:30-8:45 |
— Registration and Continental Breakfast — (Ballroom Foyer) |
| |
Graph Cuts and Flows
Chair: Chris Umans
(Haverford/Baccarat) |
Optimization
Chair: Rocco Servedio
(Waterford/Lalique) |
| 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
(Haverford/Baccarat) |
| 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) |
| |
Privacy
Chair: Ravi Kumar
(Haverford/Baccarat) |
Quantum
Chair: Anup Rao
(Waterford/Lalique) |
| 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 — |
| |
Graphs
Chair: Rasmus Pagh
(Haverford/Baccarat) |
Complexity II
Chair: Jonathan Katz
(Waterford/Lalique) |
| 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) |
| |
Economics
Chair: Nicole Immorlica
(Haverford/Baccarat) |
Markov Chains
Chair: Michael Mitzenmacher
(Waterford/Lalique) |
| 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
(Haverford/Baccarat) |
Geometry
Chair: Rasmus Pagh
(Waterford/Lalique) |
| 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
(Haverford/Baccarat) |
Complexity III
Chair: Jonathan Kelner
(Waterford/Lalique) |
| 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 — |
|
