Conference Program

Saturday, June 1st at The Palo Alto Sheraton

8:00-3:30 New (Theoretical) Challenges in Machine Learning
Avrim Blum and Phil Long

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
Invited Talk by Prabhakar Raghavan (Sequoia/Oak)
5:00-7:00 Dinner (Not Provided)
7:00-9:00 Reception (Justines)
Grant Writing Panel (Cypress Ballroom)

Sunday, June 2nd at The Palo Alto Sheraton

Sunday, June 2, 2013
Bagels and Coffee (Cypress and Sequoia/Oak)
  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)
Poster Session (Justins)      [hors d'oeuvres provided]

Monday, June 3rd at The Palo Alto Sheraton

Monday, June 3, 2013
Bagels and Coffee (Cypress and Sequoia/Oak)
  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
Knuth-Prize Lecture: Gary Miller (Cypress Ballroom)
Session Chair: David Johnson
6:00-8:00 Dinner (Not Provided)
SIGACT Business Meeting (Cypress Ballroom)

Tuesday, June 4th at The Palo Alto Sheraton

Tuesday, June 4, 2013
Bagels and Coffee (Cypress and Sequoia/Oak)
  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