STOC 2015: 47th Annual Symposium on the Theory of Computing

Conference Program

Sunday June 14, 2015

Workshop and Tutorials
9:00-5:30 9:00-5:00
Location: E141-142
Algorithmic Frontiers of Modern Massively Parallel Computation
Organizers: Ashish Goel, Sergei Vassilvistskii, Grigory Yaroslavtsev
11:20-5:30
Location: E143-144
Tutorial: Hardness and Equivalences in P
Organizers: Amir Abboud, Arturs Backurs, Piotr Indyk, Virginia V. Williams
2:00-5:30
Location: D133-D134
Tutorial: Sampling and Volume Computation in High Dimension
Organizer: Santosh Vempala
Note: Sunday meals are not part of STOC registration
6:00-7:15 Turing Award Lecture: Michael Stonebraker (Hall A)
7:30-9:30 Welcome Reception (Portland 251)

Monday June 15, 2015

Continental Breakfast in lobby outside Portland 252-3
Session 1A
Chair: Udi Wieder
Location: Portland 252
Session 1B
Chair: Chris Umans
Location: Portland 253
8:35-9:00 Approximate Distance Oracles with Improved Bounds
Shiri Chechik (Tel-Aviv University)
Proof of the Satisfiability Conjecture for Large k
Jian Ding (University of Chicago), Allan Sly (UC Berkeley and Australian National University), Nike Sun (Microsoft Research and MIT)
9:00-9:25 The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
Jakub Lacki (University of Warsaw), Jakub Ocwieja (University of Warsaw), Marcin Pilipczuk (University of Warwick and Unviersity of Warsaw), Piotr Sankowski (Univerisity of Warsaw), Anna Zych (University of Warsaw)
Consistency Thresholds for the Planted Bisection Model
Elchanan Mossel (U.C. Berkeley and University of Pennsylvania) , Joe Neeman (U.T. Austin), Allan Sly (U.C. Berkeley and Australian National University)
9:25-9:50 Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Monika Henzinger (University of Vienna, Austria), Sebastian Krinninger (University of Vienna, Austria), Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (KTH Royal Institute of Technology)
On the Complexity of Random Satisfiability Problems with Planted Solutions
Vitaly Feldman (IBM Research - Almaden), Will Perkins (University of Birmingham), Santosh Vempala (Georgia Tech)
9:50-10:15 Clustered Integer 3SUM via Additive Combinatorics
Timothy M. Chan (University of Waterloo), Moshe Lewenstein (Bar-Ilan University)
Sum-of-squares Lower Bounds for Planted Clique
Raghu Meka (UCLA), Aaron Potechin (MIT), Avi Wigderson (IAS)
10:15-10:40 Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Amir Abboud (Stanford), Virginia Vassilevska Williams (Stanford), Huacheng Yu (Stanford)
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak (Microsoft Research), Pravesh Kothari (University of Texas at Austin), Siu On Chan (Microsoft Research)
10:40-11:00 Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Arturs Backurs (MIT) and Piotr Indyk (MIT)
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Gábor Braun (Georgia Tech), Sebastian Pokutta (Georgia Tech), Daniel Zink (Georgia Tech)
11:00-11:20 Coffee Break
11:20-12:30 FCRC Keynote Session: Andrew Yao (Hall A)
12:30-1:55 Lunch
Session 2A
Chair: Ilias Diakonikolas
Location: Portland 252
Session 2B
Chair: Krzysztof Onak
Location: Portland 253
1:55-2:20 Preserving Statistical Validity in Adaptive Data Analysis
Cynthia Dwork (Microsoft Research), Vitaly Feldman (IBM Research - Almaden), Moritz Hardt (IBM Research - Almaden), Toniann Pitassi (University of Toronto), Omer Reingold, Aaron Roth (University of Pennsylvania)
Randomized Composable Core-sets for Distributed Submodular Maximization
Vahab Mirrokni (Google Research New York), Morteza Zadimoghaddam (Google Research New York)
2:20-2:45 Local, Private, Efficient Protocols for Succinct Histograms
Raef Bassily (The Pennsylvania State University), Adam Smith (The Pennsylvania State University)
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Michael B. Cohen (MIT), Sam Elder (MIT), Cameron Musco (MIT), Christopher Musco (MIT), Madalina Persu (MIT)
2:45-3:10 Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions
Shachar Lovett (University of California, San Diego), Jiapeng Zhang (University of California, San Diego)
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Sayan Bhattacharya (The Institute of Mathematical Sciences, Chennai, India), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology), Charalampos E. Tsourakakis (Harvard University)
3:10-3:30 Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Boaz Barak (Microsoft Research), Jonathan Kelner (MIT), David Steurer (Cornell University)
Lp Row Sampling by Lewis Weights
Michael B. Cohen (MIT) and Richard Peng (MIT)
3:30-4:00 Coffee Break
Session 3A
Chair: Sanjeev Khanna
Location: Portland 252
Session 3B
Chair: Michael Forbes
Location: Portland 253
4:00-4:25 On the Lovász Theta function for Independent Sets in Sparse Graphs
Nikhil Bansal (TU Eindhoven), Anupam Gupta (CMU), Guru Guruganesh (CMU)
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract
Pravesh K. Kothari (The University of Texas at Austin), Raghu Meka (University of California Los Angeles)
4:25-4:50 The Complexity of the Simplex Method
John Fearnley (University of Liverpool), Rahul Savani (University of Liverpool)
Rectangles Are Nonnegative Juntas
Mika Gö,ös (University of Toronto), Shachar Lovett (University of California, San Diego), Raghu Meka (University of California, Los Angeles), Thomas Watson (University of Toronto), David Zuckerman (University of Texas at Austin)
4:50-5:15 An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Thomas Dueholm Hansen (Stanford University), Uri Zwick (Tel Aviv University)
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Irit Dinur (Weizman Institute), Prahladh Harsha (TIFR), Guy Kindler (Hebrew University)
5:15-5:40 Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Shuchi Chawla (University of Wisconsin-Madison), Konstantin Makarychev (Microsoft Research), Tselil Schramm (UC Berkeley), Grigory Yaroslavtsev (University of Pennsylvania)
The List Decoding Radius of Reed-Muller Codes over Small Fields
Abhishek Bhowmick (University of Texas at Austin) and Shachar Lovett (University of California, San Diego)
5:40-6:05 Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
Zeyuan Allen-Zhu (MIT), Lorenzo Orecchia (Boston University)
A Characterization of the Capacity of Online (Causal) Binary Channels
Zitan Chen (The Chinese University of Hong Kong), Sidharth Jaggi (The Chinese University of Hong Kong), Michael Langberg (SUNY at Buffalo)
6:05-6:25 Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan Allen-Zhu (MIT), Zhenyu Liao (Boston University), Lorenzo Orecchia (Boston University)
Reed-Muller Codes for Random Erasures and Errors
Emmanuel Abbe (Princeton University), Amir Shpilka (Tel-Aviv University), Avi Wigderson (IAS, Princeton).
9:00pm Business Meeting (Location: Portland 252)

Tuesday June 16, 2015

Session 4A
Chair: Ben Reichardt
Location: Portland 252
Session 4B
Chair: Yaron Singer
Location: Portland 253
8:35-9:00 Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson (MIT) and Andris Ambainis (University of Latvia)
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Siddharth Barma (California Institute of Technology)
9:00-9:25 Quantum Information Complexity
Dave Touchette (Université de Montréal)
Approximating the Nash Social Welfare with Indivisible Items
Richard Cole (New York University) and Vasilis Gkatzelis (Stanford University)
9:25-9:50 Sparse Quantum Codes from Quantum Circuits
Dave Bacon (University of Washington and Google), Steven T. Flammia (U Sydney), Aram W. Harrow (MIT), Jonathan Shi (Cornell)
On the Complexity of Nash Equilibria in Anonymous Games
Xi Chen (Columbia University), David Durfee (Georgia Institute of Technology), Anthi Orfanou (Columbia University)
9:50-10:15 Small Value Parallel Repetition for General Games
Mark Braverman (Princeton University), Ankit Garg (Princeton University).
Hardness of Graph Pricing Through Generalized Max-Dicut
Euiwoong Lee (Carnegie Mellon)
10:15-10:40 An Interactive Information Odometer and Applications
Mark Braverman (Princeton University) and Omri Weinstein (Princeton University)
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Amit Daniely (Hebrew University), Michael Schapira (Hebrew University), Gal Shahaf (Hebrew University)
10:40-11:00 The Communication Complexity of Interleaved Group Products
W. T. Gowers (University of Cambridge), Emanuele Viola (Northeastern & Harvard)
Inapproximability of Nash Equilibrium
Aviad Rubinstein (UC Berkeley)
11:00-11:20 Coffee Break
11:20-12:30 FCRC Keynote Session: Olivier Temam (Hall A)
12:30-1:55 Lunch
Session 5A
Chair: Yael Kalai
Location: Portland 252
Session 5B
Chair: Mary Wootters
Location: Portland 253
1:55-2:20 Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Venkata Koppula (University of Texas at Austin), Allison B. Lewko (Columbia University), Brent Waters (University of Texas at Austin)
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
Ran Canetti (Tel-Aviv University and Boston University), Justin Holmgren (MIT), Abhishek Jain (Johns Hopkins), Vinod Vaikuntanathan (MIT)
Succinct Randomized Encodings and their Applications
Nir Bitansky (MIT), Sanjam Garg (University of California, Berkeley), Huijia Lin (University of California, Santa Barbara), Rafael Pass (Cornell University), Sidharth Telang (Cornell University)
Sketching and Embedding are Equivalent for Norms
Alexandr Andoni (Simons Institute), Robert Krauthgamer (Weizmann Institute of Science), Ilya Razenshteyn (MIT)
2:20-2:45 Garbled RAM From One-Way Functions
Sanjam Garg (UC Berkeley), Steve Lu (UCLA), Rafail Ostrovsky (UCLA), Alessandra Scafuro (Boston University and Northeastern University)
Prioritized Metric Structures and Embedding
Michael Elkin (Ben-Gurion University of the Negev), Arnold Filtser (Ben-Gurion University of the Negev), Neiman Ofer (Ben-Gurion University of the Negev)
2:45-3:10 Non-malleable Reductions and Applications
Divesh Aggarwal (EPFL), Yevgeniy Dodis (NYU), Tomasz Kazana (University of Warsaw), Maciej Obremski (University of Warsaw)
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space
Jean Bourgain (IAS), Sjoerd Dirksen (RWTH Aachen University), Jelani Nelson (Harvard)
3:10-3:30 Leveled Fully Homomorphic Signatures from Standard Lattices
Sergey Gorbunov (MIT), Vinod Vaikuntanathan (MIT), Daniel Wichs (Northeastern)
A Directed Isoperimetric Inequality with Application to Bregman Near Neighbor Lower Bounds
Amirali Abdullah (University of Utah), Suresh Venkatasubramanian (University of Utah)
3:30-3:55 Coffee Break
Session 6A
Chair: Elena Grigorescu
Location: Portland 252
Session 6B
Chair: Costis Daskalakis
Location: Portland 253
3:55-4:20 Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries
Xi Chen (Columbia University), Anindya De (IAS/DIMACS), Rocco A. Servedio (Columbia University), Li-Yang Tan (Columbia University/Simons Institute)
Bypassing KLS: Gaussian Cooling and an O*(n3) Volume Algorithm
Ben Cousins (Georgia Tech), Santosh Vempala (Georgia Tech)
4:20-4:40 Quantum Spectrum Testing
Ryan O'Donnell (Carnegie Mellon University), John Wright (Carnegie Mellon University)
FPTAS for #BIS with Degree Bounds on One Side Jingcheng Liu (UC Berkeley), Pinyan Lu (Microsoft Research)
4:40-5:00 Break
5:00-6:15 Session 7
Chair: Ronitt Rubinfeld
Location: Portland 251/257/258
5:00pm-5:25pm Exponential Separation of Information and Communication for Boolean Functions
Anat Ganor (Weizmann Institute), Gillat Kol (IAS), Ran Raz (Weizmann Institute & IAS)
5:25pm-5:50pm Lower Bounds on the Size of Semidefinite Programming Relaxations
James R. Lee (University of Washington), Prasad Raghavendra (UC Berkeley), David Steurer (Cornell)
5:50pm-6:15pm 2-Server PIR with Sub-Polynomial Communication
Zeev Dvir (Princeton University) and Sivakanth Gopi (Princeton University)
6:15-7:30 Knuth Prize Lecture: László Babai (Portland 251/7/8)

Wednesday June 17, 2015

Session 8A
Chair: Udi Wieder
Location: Portland 252
Session 8B
Chair: Sanjeev Khanna
Location: Portland 253
8:35-9:00 Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method
Andris Ambainis (University of Latvia), Yuval Filmus (Institute for Advanced Study), François Le Gall (University of Tokyo)
Excluded Grid Theorem: Improved and Simplified
Julia Chuzhoy (Toyota Technological Institute at Chicago)
9:00-9:25 High Parallel Complexity Graphs and Memory-Hard Functions
Joël Alwen (IST Austria), Vladimir Serbinenko (Google Zürich)
The Directed Grid Theorem
Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO) and Stephan Kreutzer (Technical University Berlin)
9:25-9:50 Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Ittai Abraham (VMware Research), Danny Dolev (Hebrew University)
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo, Japan) and Mikkel Thorup (University of Copenhagen, Denmark)
9:50-10:15 Test-and-Set in Optimal Space
George Giakkoupis (INRIA Rennes), Maryam Helmi (University of Calgary), Lisa Higham (University of Calgary), Philipp Woelfel (University of Calgary)
Beyond the Euler Characteristic: Approximating the Genus of General Graphs
Ken-ichi Kawarabayashi (National Institute of Informatics, Japan), Anastasios Sidiropoulos (The Ohio State University)
10:15-10:40 Adjacency Labeling Schemes and Induced-Universal Graphs
Stephen Alstrup (University of Copenhagen), Haim Kaplan (Tel Aviv University), Mikkel Thorup (University of Copenhagen), Uri Zwick (Tel-Aviv University)
Computing with Tangles
Martin Grohe (RWTH Aachen University) and Pascal Schweitzer (RWTH Aachen University)
10:40-11:00 How Well Can Graphs Represent Wireless Interference?
Magnus M. Halldorsson (Reykjavik University) and Tigran Tonoyan (Reykjavik University)
Faster Canonical Forms for Primitive Coherent Configurations
John Wilmes (University of Chicago) and Xiaorui Sun (Columbia University)
11:00-11:20 Coffee Break
11:20-12:30 FCRC Keynote Session: Don Syme (Hall A)
12:30-1:55 Lunch
Session 9A
Chair: Elena Grigorescu
Location: Portland 252
Session 9B
Chair: Ilias Diakonikolas
Location: Portland 253
1:55-2:20 Random Permutations using Switching Networks
Artur Czumaj (University of Warwick)
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Jian Li (Tsinghua University), Yuval Rabani (The Hebrew University), Leonard J. Schulman (California Institute of Technology), Chaitanya Swamy (University of Waterloo)
2:20-2:45 Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Anand Louis (Princeton University)
Tight Bounds for Learning a Mixture of Two Gaussians
Moritz Hardt (IBM Research Almaden), Eric Price (The University of Texas at Austin)
2:45-3:10 Testing Cluster Structure of Graphs
Artur Czumaj (University of Warwick), Pan Peng (TU Dortmund and Chinese Academy of Sciences), Christian Sohler (TU Dortmund)
Learning Mixtures of Gaussians in High Dimensions
Rong Ge (Microsoft Research New England), Qingqing Huang (MIT), Sham M. Kakade (Microsoft Research New England)
3:10-3:30 Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling
Divesh Aggarwal (École polytechnique fédérale de Lausanne), Daniel Dadush (Centrum Wiskunde & Informatica), Oded Regev (New York University), Noah Stephens-Davidowitz (New York University)
Efficiently Learning Ising Models on Arbitrary Graphs
Guy Bresler (MIT)
3:30-4:00 Coffee Break
Session 10A
Chair: Mary Wootters
Location: Portland 252
Session 10B
Chair: Shaddin Dughmi
Location: Portland 253
4:00-4:25 Approximate k-flat Nearest Neighbor Search
Wolfgang Mulzer (FU Berlin), Huy L. Nguyen (Simons Institute), Paul Seiferth (FU Berlin), Yannik Stein (FU Berlin)
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox (Duke University), Philip N. Klein (Brown University), Shay Mozes (Interdisciplinary Center, Herzliya, Israel)
4:25-4:50 Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni (Simons Institute) and Ilya Razenshteyn (MIT)
Minimizing Flow-Time on Unrelated Machines
Nikhil Bansal (Eindhoven University of Technology, Netherlands), Janardhan Kulkarni (Duke University)
4:50-5:15 Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Kasper Green Larsen (Aarhus University), Jelani Nelson (Harvard University), Huy Le Nguyen (Simons Institute)
Randomized Rounding for the Largest Simplex Problem
Aleksandar Nikolov (Microsoft Research)
5:15-5:40 From Independence to Expansion and Back Again
Tobias Christiani (IT University of Copenhagen), Rasmus Pagh (IT University of Copenhagen), Mikkel Thorup (University of Copenhagen)
Greedy Algorithms for Steiner Forest
Anupam Gupta (Carnegie Mellon University) and Amit Kumar (IIT Delhi)
5:40-6:05 Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Ankur Moitra (MIT)
Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim (Max-Planck-Institut fur Informatik), Robert Kleinberg (Cornell University and Microsoft Research), Rad Niazadeh (Cornell University)
6:05-6:25 Analysis of a Classical Matrix Preconditioning Algorithm
Leonard J. Schulman (Caltech), Alistair Sinclair (UC Berkeley)
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Nitish Korula (Google Research), Vahab Mirrokni (Google Research), Morteza Zadimoghaddam (Google Research)