STOC 2013: 45th ACM Symposium on the Theory of Computing
Palo Alto, CA, June, 1-4, 2013
Conference Program
Saturday, June 1st at The Palo Alto Sheraton
|
Workshops |
|||
|---|---|---|---|
| 8:00-3:30 |
New (Theoretical) Challenges in Machine Learning
Avrim Blum and Phil Long Sequoia/Oak |
Information Complexity and Applications
Mark Braverman Cypress Ballroom: Cypress 1&2 |
Online Matching and Ad Serving: Theory and Practice
Nikhil R. Devanur and Vahab Mirrokni Cypress Ballroom: Juniper |
| 3:30-4:00 | Coffee break | ||
| 4:00-5:00 |
|
||
| 5:00-7:00 | Dinner (Not Provided) | ||
| 7:00-9:00 | Reception (Justines) | ||
| 8:00-9:30 |
|
||
Sunday, June 2nd at The Palo Alto Sheraton
| Sunday, June 2, 2013 | ||
|---|---|---|
| 7:30-8:30 |
|
|
|
Session 1A (Cypress Ballroom) Session chair: Xi Chen |
Session 1B (Sequoia/Oak) Session chair: Mikkel Thorup |
|
| 8:25-8:45 |
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
Daniel Kane and Raghu Meka |
Coevolutionary Opinion Formation Games
Kshipra Bhawalkar, Sreenivas Gollapudi, and Kamesh Munagala |
| 8:50-9:10 |
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan |
Prior-Independent Mechanisms for Scheduling
Shuchi Chawla, Jason D. Hartline, David Malec, and Balasubramanian Sivan |
| 9:15-9:35 |
Natural Proofs Versus Derandomization
Ryan Williams |
Combinatorial Walrasian Equilibrium
Michal Feldman, Nikolai Gravin, and Brendan Lucier |
| 9:40-10:00 |
On the Complexity of Trial and Error
Xiaohui Bei, Ning Chen, and Shengyu Zhang |
Efficient Rounding for the Noncommutative Grothendieck Inequality Assaf Naor, Oded Regev, and Thomas Vidick |
| 10:00-10:30 | Coffee break | |
|
Session 2A (Cypress Ballroom) Session chair: Anna Gilbert |
Session 2B (Sequoia/Oak) Session chair: Aleksander Madry |
|
| 10:30-10:50 |
Low Rank Approximation and Regression in Input Sparsity Time
Ken Clarkson and David P. Woodruff |
Equivalence of Deterministic One-Counter Automata is NL-complete
Stanislav Böhm, Stefan Göller, and Petr Jančar |
| 10:55-11:15 |
Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
Xiangrui Meng and Michael W. Mahoney |
Explicit Lower Bounds via Geometric Complexity Theory
Peter Bürgisser and Christian Ikenmeyer |
| 11:20-11:40 |
Sparsity Lower Bounds for Dimensionality Reducing Maps
Jelani Nelson and Huy L. Nguyên |
From Information to Exact Communication
Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein |
| 11:45-12:05 |
Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data
Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer |
An Information Complexity Approach to Extended Formulations Mark Braverman and Ankur Moitra |
| 12:10-12:30 |
How Robust Are Linear Sketches To Adaptive Inputs?
Moritz Hardt and David P. Woodruff |
Average-Case Lower Bounds for Formula Size Ilan Komargodski and Ran Raz |
| 12:30-1:55 |
Lunch (provided at the conference)
|
Session 3A (Cypress Ballroom) Session chair: Costis Daskalakis |
Session 3B (Sequoia/Oak) Session chair: Yael Tauman Kalai |
| 1:55-2:15 |
The Complexity of Non-Monotone Markets
Xi Chen, Dimitris Paparas, and Mihalis Yannakakis |
Non-Black-Box Simulation in the Fully Concurrent Setting
Vipul Goyal |
| 2:20-2:40 |
Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
Yun Kuen Cheung, Richard Cole, and Nikhil Devanur |
Non-Black-Box Simulation from One-Way FunctionsAnd Applications to Resettable Security
Kai-Min Chung, Rafael Pass, and Karn Seth |
| 2:45-3:05 |
Simultaneous Auctions Are (Almost) Efficient
Michal Feldman, Hu Fu, Nikolai Gravin, and Brendan Lucier |
On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography Nir Bitansky and Omer Paneth |
| 3:10-3:30 |
Composable and Efficient Mechanisms
Vasilis Syrgkanis and Éva Tardos |
Shielding Circuits with Groups Eric Miles and Emanuele Viola |
| 3:30-4:00 | Coffee break | |
|
Session 4A (Cypress Ballroom) Session chair: Valerie King |
Session 4B (Sequoia/Oak) Session chair: Russell Impagliazzo |
|
| 4:00-4:20 |
Quasipolynomial-Time Canonical Form for Steiner Designs László Babai and John Wilmes Multi-Stage Design for Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems Xi Chen, Xiaorui Sun, and Shang-Hua Teng |
Quasi-polynomial Hitting-set for Set-depth-Δ Formulas
Manindra Agrawal, Chandan Saha, and Nitin Saxena |
| 4:25-4:45 |
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results
Anupam Gupta, Kunal Talwar, and David Witmer |
Beyond Worst-Case Analysis in Private Singular Vector Computation
Moritz Hardt and Aaron Roth |
| 4:50-5:10 |
Large-Treewidth Graph Decompositions and Applications
Chandra Chekuri and Julia Chuzhoy |
Differential Privacy for the Analyst via Private Equilibrium Computation
Justin Hsu, Aaron Roth, and Jonathan Ullman |
| 5:15-5:35 |
Fast Hamiltonicity Checking via Bases of Perfect Matchings
Marek Cygan, Stefan Kratsch, and Jesper Nederlof |
The Geometry of Differential Privacy: The Sparse and Approximate Cases
Aleksandar Nikolov, Kunal Talwar, and Li Zhang |
| 5:40-6:00 |
Polynomial-Time Perfect Matchings in Dense Hypergraphs
Peter Keevash, Fiachra Knox, and Richard Mycroft |
Answering n2+o(1) Counting Queries with Differential Privacy is Hard
Jonathan Ullman |
| 6:00-8:00 |
Dinner (Not Provided)
|
|
| 8:00-10:00 |
|
|
Monday, June 3rd at The Palo Alto Sheraton
| Monday, June 3, 2013 | ||
|---|---|---|
| 7:30-8:30 |
|
|
|
Session 5A (Cypress Ballroom) Session chair: Tim Roughgarden |
Session 5B (Sequoia/Oak) Session chair: Virginia Vassilevska Williams |
|
| 8:25-8:45 |
Bottom-k and Priority Sampling, Set Similarity and Subset Sums with Minimal Independence
Mikkel Thorup |
A o(n) Monotonicity Tester for Boolean Functions over the Hypercube
Deeparnab Chakrabarty and C. Seshadhri |
| 8:50-9:10 |
Fast Routing Table Construction Using Small Messages
Christoph Lenzen and Boaz Patt-Shamir |
Optimal Bounds for Monotonicity and Lipschitz Testing over Hypercubes and Hypergrids
Deeparnab Chakrabarty and C. Seshadhri |
| 9:15-9:35 |
Multidimensional Approximate Agreement in Byzantine Asynchronous Systems
Hammurabi Mendes and Maurice Herlihy |
Every Locally Characterized Affine-Invariant Property is Testable
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett |
| 9:40-10:00 |
Byzantine Agreement in Polynomial Expected Time
Valerie King and Jared Saia |
Testing Subdivision-Freeness: Property Testing Meets Structural Graph Theory Ken-ichi Kawarabayashi and Yuichi Yoshida |
| 10:00-10:30 | Coffee break | |
|
Session 6A (Cypress Ballroom) Session chair: Prasad Raghavendra |
Session 6B (Sequoia/Oak) Session chair: Samir Khuller |
|
| 10:30-10:50 |
Approximation Resistance from Pairwise Independent Subgroups
Siu On Chan |
A Node-capacitated Okamura-Seymour Theorem
James R. Lee, Manor Mendel, and Mohammad Moharrami |
| 10:55-11:15 |
Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs
Sangxia Huang |
Structured Recursive Separator Decompositions for Planar Graphs in Linear Time
Philip N. Klein, Shay Mozes, and Christian Sommer |
| 11:20-11:40 |
Witness Encryption and its Applications
Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters |
Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
Liam Roditty and Virginia Vassilevska Williams |
| 11:45-12:05 |
Majority is Stablest : Discrete and SoS
Anindya De, Elchanan Mossel, and Joe Neeman |
The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online Albert Gu, Anupam Gupta, and Amit Kumar |
| 12:10-12:30 |
Strong ETH Holds for Regular Resolution
Chris Beck and Russell Impagliazzo |
Simplex Partitioning via Exponential Clocks and the Multiway Cut Problem Niv Buchbinder, Joseph (Seffi) Naor, and Roy Schwartz |
| 12:30-2:00 |
Lunch (provided at the conference)
|
|
|
Session 7A (Cypress Ballroom) Session chair: Dan Boneh |
Session 7B (Sequoia/Oak) Session chair: Ryan Williams |
|
| 2:00-2:20 |
Attribute-based Encryption for Circuits
Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee |
Extending Continuous Maps: Polynomiality and Undecidability
Martin Cadek, Marek Krcal, Jiri Matousek, Lukas Vokrinek, and Uli Wagner |
| 2:25-2:45 |
Reusable Garbled Circuits and Succinct Functional Encryption
Shafi Goldwasser, Yael Tauman Kalai, Raluca Ada Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich |
Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
Sariel Har-Peled and Benjamin Raichel |
| 2:50-3:10 |
Delegation for Bounded Space
Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum |
Random Lattice Triangulations: Structure and Algorithms
Pietro Caputo, Fabio Martinelli, Alistair Sinclair, and Alexandre Stauffer |
| 3:15-3:35 |
Classical Hardness of Learning with Errors
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehle |
Lee-Yang Theorems and the Complexity of Computing Averages Alistair Sinclair and Piyush Srivastava |
| 3:40-4:00 |
On the Concrete Efficiency of Probabilistically-Checkable Proofs
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer |
A Complete Dichotomy Rises from the Capture of Vanishing Signatures Jin-Yi Cai, Heng Guo, and Tyson Williams |
| 4:00-4:30 | Coffee break | |
| 4:30-6:00 |
Session Chair: David Johnson |
|
| 6:00-8:00 |
Dinner (Not Provided)
|
|
| 8:00-10:00 |
|
|
Tuesday, June 4th at The Palo Alto Sheraton
| Tuesday, June 4, 2013 | ||
|---|---|---|
| 7:30-8:30 |
|
|
|
Session 8A (Cypress Ballroom) Session chair: David Steurer |
Session 8B (Sequoia/Oak) Session chair: Artur Czumaj |
|
| 8:25-8:45 |
Optimal Euclidean Spanners: Really Short, Thin and Lanky
Michael Elkin and Shay Solomon |
Constraint Satisfaction, Packet Routing, and the Lovasz Local Lemma
David G. Harris and Aravind Srinivasan |
| 8:50-9:10 |
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao |
The Complexity of Finite-Valued CSPs
Johan Thapper and Stanislav Zivný |
| 9:15-9:35 |
Low-rank Matrix Completion using Alternating Minimization
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi |
Going After the k-SAT Threshold
Amin Coja-Oghlan and Konstantinos Panagiotou |
| 9:40-10:00 |
The Approximate Rank of a Matrix and its Algorithmic Applications
Noga Alon, Troy Lee, Adi Shraibman, and Santosh Vempala |
Interactive Channel Capacity Gillat Kol and Ran Raz |
| 10:00-10:30 | Coffee break | |
|
Session 9A (Cypress Ballroom) Session chair: Giuseppe F. Italiano |
Session 9B (Sequoia/Oak) Session chair: Moritz Hardt |
|
| 10:30-10:50 |
Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
Aaron Bernstein |
Succinct Sampling from Discrete Distributions
Karl Bringmann and Kasper Green Larsen |
| 10:55-11:15 |
Linear-Time Algorithms for Max Flow and Multiple-Source Shortest Paths in Unit-Weight Planar Graphs
David Eisenstat and Philip N. Klein |
New Independent Source Extractors with Exponential Improvement
Xin Li |
| 11:20-11:40 |
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
Ofer Neiman and Shay Solomon |
Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum, Salil Vadhan, and Avi Wigderson |
| 11:45-12:05 |
A New Approach to Computing Maximum Flows using Electrical Flows
Yin Tat Lee, Satish Rao, and Nikhil Srivastava |
Lower Bounds for RAMs and Quantifier Elimination Miklós Ajtai |
| 12:10-12:30 |
Max Flows in O(nm) Time, or Better
James B. Orlin |
Some Trade-off Results for Polynomial Calculus Chris Beck, Jakob Nordström, and Bangsheng Tang |
| 12:30-1:55 |
Lunch (Not Provided)
|
Session 10A (Cypress Ballroom) Session chair: Lance Fortnow |
Session 10B (Sequoia/Oak) Session chair: Ronald de Wolf |
| 1:55-2:15 |
New Bounds for Matching Vector Families
Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett |
Quantum de Finetti Theorems under Local Measurements with Applications
Fernando G.S.L. Brandão and Aram W. Harrow |
| 2:20-2:40 |
A New Family of Locally Correctable Codes Based on Degree-Lifted Algebraic Geometry Codes
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swatik Kopparty, and Shubangi Saraf |
Product-state Approximations to Quantum Ground States
Fernando G.S.L. Brandão and Aram W. Harrow |
| 2:45-3:05 |
List Decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin Subcodes up to the Singleton Bound
Venkatesan Guruswami and Chaoping Xing |
Inverting Well Conditioned Matrices in Quantum Logspace Amnon Ta-Shma |
| 3:10-3:30 |
On the List Decodability of Random Linear Codes with Large Error Rates
Mary Wootters |
Superlinear Advantage for Exact Quantum Algorithms Andris Ambainis |
| 3:30-4:00 | Coffee break | |
|
Session 11A (Cypress Ballroom) Session chair: Avrim Blum |
Session 11B (Sequoia/Oak) Session chair: Neeraj Kayal |
|
| 4:00-4:20 |
Approximating k-Median via Pseudo-Approximation Shi Li and Ola Svensson |
The Orbit Problem in Higher Dimensions
Ventsislav Chonev, Joël Ouaknine, and James Worrell |
| 4:25-4:45 |
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu |
The Loss of Serving in The Dark
Yossi Azar, Ilan Cohen, and Iftah Gamzu |
| 4:50-5:10 |
Communication Lower Bounds Using Directional Derivatives
Alexander A. Sherstov |
Tight Bounds for Online Vector Bin Packing
Yossi Azar, Ilan Cohen, Seny Kamara, and Bruce Shepherd |
| 5:15-5:35 |
Homomorphic Fingerprints under Misalignments: Sketching Edit and Shift Distances
Alexandr Andoni, Assaf Goldberger, Andrew McGregor, and Ely Porat |
Stochastic Combinatorial Optimization via Poisson Approximation
Jian Li and Wen Yuan |
| 5:35 |
Adjourn
|
|