STOC 2016
48th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2016)
Powered by
Conference Publishing Consulting
48th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2016), June 19–21, 2016, Cambridge, MA, USA

STOC 2016 – Proceedings

 Contents - Abstracts - Authors

Frontmatter

Title Page


Article: stoc16foreword-fm000-p doi:
Foreword


Article: stoc16foreword-fm001-p doi:
Conference Organization


Article: stoc16foreword-fm002-p doi:
Sponsors and Supporters


Article: stoc16foreword-fm003-p doi:

Session 1A

Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions
Boris Aronov and Micha Sharir
(New York University, USA; Tel Aviv University, Israel)


 Article: stoc16main-main171-p doi:
Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford
(Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Microsoft Research, USA)


 Article: stoc16main-main436-p doi:
Separating Subadditive Euclidean Functionals
Alan Frieze and Wesley Pegden
(Carnegie Mellon University, USA)


 Article: stoc16main-main301-p doi:
Bounded Degree Cosystolic Expanders of Every Dimension
Shai Evra and Tali Kaufman
(Hebrew University of Jerusalem, Israel; Bar-Ilan University, Israel)


 Article: stoc16main-main190-p doi:

Session 1B

Constant-Round Interactive Proofs for Delegating Computation
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum
(Samsung Research, USA; Massachusetts Institute of Technology, USA)


 Article: stoc16main-main449-p doi:
Candidate Hard Unique Game
Subhash Khot and Dana Moshkovitz
(New York University, USA; Massachusetts Institute of Technology, USA)


 Article: stoc16main-main140-p doi:
On the Effect of Randomness on Planted 3-Coloring Models
Roee David and Uriel Feige
(Weizmann Institute of Science, Israel)


 Article: stoc16main-main250-p doi:
Matrix Rigidity of Random Toeplitz Matrices
Oded Goldreich and Avishay Tal
(Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA)


 Article: stoc16main-main359-p doi:

Session 2A

Complexity Theoretic Limitations on Learning Halfspaces
Amit Daniely
(Google, USA)


 Article: stoc16main-main108-p doi:
A Cost Function for Similarity-Based Hierarchical Clustering
Sanjoy Dasgupta
(University of California at San Diego, USA)


 Article: stoc16main-main131-p doi:
The Computational Power of Optimization in Online Learning
Elad Hazan and Tomer Koren
(Princeton University, USA; Technion, Israel)


 Article: stoc16main-main167-p doi:
Instance Optimal Learning of Discrete Distributions
Gregory Valiant and Paul Valiant
(Stanford University, USA; Brown University, USA)


 Article: stoc16main-main391-p doi:

Session 2B

Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan, and Ola Svensson
(Eindhoven University of Technology, Netherlands; University of Maryland, USA; EPFL, Switzerland)


 Article: stoc16main-main307-p doi:
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies
Elaine Levey and Thomas Rothvoss
(University of Washington, USA)


 Article: stoc16main-main145-p doi:
Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer
(Cornell University, USA; University of California at Berkeley, USA)


 Article: stoc16main-main137-p doi:
Maximizing Determinants under Partition Constraints
Aleksandar Nikolov and Mohit Singh
(University of Toronto, Canada; Microsoft Research, USA)


 Article: stoc16main-main440-p doi:

Session 3A

High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf
(Rutgers University, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA)


 Article: stoc16main-main122-p doi:
Repairing Reed-Solomon Codes
Venkatesan Guruswami and Mary Wootters
(Carnegie Mellon University, USA)


 Article: stoc16main-main125-p doi:
Efficiently Decoding Reed-Muller Codes from Random Errors
Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk
(Tel Aviv University, Israel)


 Article: stoc16main-main128-p doi:

Session 3B

Optimal Principal Component Analysis in Distributed and Streaming Models
Christos Boutsidis, David P. Woodruff, and Peilin Zhong
(Goldman Sachs, USA; IBM Research, USA; Tsinghua University, China)


 Article: stoc16main-main431-p doi:
Weighted Low Rank Approximations with Provable Guarantees
Ilya Razenshteyn, Zhao Song, and David P. Woodruff
(Massachusetts Institute of Technology, USA; University of Texas at Austin, USA; IBM Research, USA)


 Article: stoc16main-main387-p doi:
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
Michael Kapralov
(EPFL, Switzerland)


 Article: stoc16main-main442-p doi:

Session 4A

Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs
Gil Cohen
(Weizmann Institute of Science, Israel)


 Article: stoc16main-main138-p doi:
Non-malleable Extractors and Codes, with Their Many Tampered Extensions
Eshan Chattopadhyay, Vipul Goyal, and Xin Li
(University of Texas at Austin, USA; Microsoft Research, India; Johns Hopkins University, USA)


 Article: stoc16main-main207-p doi:
Extractors for Sumset Sources
Eshan Chattopadhyay and Xin Li
(University of Texas at Austin, USA; Johns Hopkins University, USA)


 Article: stoc16main-main422-p doi:

Session 4B

Parallel Exhaustive Search without Coordination
Pierre Fraigniaud, Amos Korman, and Yoav Rodeh
(CNRS, France; University of Paris Diderot, France; Weizmann Institute of Science, Israel)


 Article: stoc16main-main182-p doi:
Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints
Aviad Rubinstein
(University of California at Berkeley, USA)


 Article: stoc16main-main176-p doi:
Online Matching: Haste Makes Waste!
Yuval Emek, Shay Kutten, and Roger Wattenhofer
(Technion, Israel; ETH Zurich, Switzerland)


 Article: stoc16main-main239-p doi:

Session 5

A Tight Space Bound for Consensus
Leqi Zhu
(University of Toronto, Canada)


 Article: stoc16main-main266-p doi:
The 4/3 Additive Spanner Exponent Is Tight
Amir Abboud and Greg Bodwin
(Stanford University, USA)


 Article: stoc16main-main234-p doi:

Session 6A

Cell-Probe Lower Bounds for Dynamic Problems via a New Communication Model
Huacheng Yu
(Stanford University, USA)


 Article: stoc16main-main235-p doi:
Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams
(Stanford University, USA; Aarhus University, Denmark)


 Article: stoc16main-main451-p doi:
Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound
Aaron Bernstein and Shiri Chechik
(Columbia University, USA; Tel Aviv University, Israel)


 Article: stoc16main-main112-p doi:
New Deterministic Approximation Algorithms for Fully Dynamic Matching
Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai
(Institute of Mathematical Sciences at Chennai, India; University of Vienna, Austria; KTH, Sweden)


 Article: stoc16main-main293-p doi:

Session 6B

Algorithmic Bayesian Persuasion
Shaddin Dughmi and Haifeng Xu
(University of Southern California, USA)


 Article: stoc16main-main346-p doi:
The Sample Complexity of Auctions with Side Information
Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas
(Microsoft Research, USA; University of Hong Kong, China; University of California at Berkeley, USA)


 Article: stoc16main-main219-p doi:
Do Prices Coordinate Markets?
Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra
(University of Pennsylvania, USA)


 Article: stoc16main-main246-p doi:
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Four Agents
Haris Aziz and Simon Mackenzie
(Data61, Australia; UNSW, Australia)


 Article: stoc16main-main121-p doi:

Session 7A

Distributed (Δ+1)-Coloring in Sublogarithmic Rounds
David G. Harris, Johannes Schneider, and Hsin-Hao Su
(University of Maryland, USA; ABB Corporate Research, USA; Massachusetts Institute of Technology, USA)


 Article: stoc16main-main152-p doi:
A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto
(ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland)


 Article: stoc16main-main300-p doi:
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
(University of Vienna, Austria; Max Planck Institute for Informatics, Germany; KTH, Sweden)


 Article: stoc16main-main382-p doi:
Contention Resolution with Log-Logstar Channel Accesses
Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young
(Stony Brook University, USA; University of Michigan, USA; Mississippi State University, USA)


 Article: stoc16main-main456-p doi:

Session 7B

Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal
Surender Baswana, Keerti Choudhary, and Liam Roditty
(IIT Kanpur, India; Bar-Ilan University, Israel)


 Article: stoc16main-main437-p doi:
Deterministic and Probabilistic Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal
(University of Southern California, USA)


 Article: stoc16main-main462-p doi:
Ramanujan Coverings of Graphs
Chris Hall, Doron Puder, and William F. Sawin
(University of Wyoming, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)


 Article: stoc16main-main313-p doi:
Enumerating Parametric Global Minimum Cuts by Random Interleaving
David R. Karger
(Massachusetts Institute of Technology, USA)


 Article: stoc16main-main335-p doi:

Session 8A

Improved Approximation for Node-Disjoint Paths in Planar Graphs
Julia Chuzhoy, David H. K. Kim, and Shi Li
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA; State University of New York at Buffalo, USA)


 Article: stoc16main-main169-p doi:
A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting
MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx
(Google, USA; Massachusetts Institute of Technology, USA; University of Maryland at College Park, USA; Hungarian Academy of Sciences, Hungary)


 Article: stoc16main-main213-p doi:
Approximating Connectivity Domination in Weighted Bounded-Genus Graphs
Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld
(ENS, France; CNRS, France; Brown University, USA)


 Article: stoc16main-main369-p doi:
Routing under Balance
Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford
(University of Warwick, UK; Carnegie Mellon University, USA; Microsoft Research, USA)


 Article: stoc16main-main454-p doi:

Session 8B

Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity
Xi Chen, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan
(Columbia University, USA; Charles University in Prague, Czechia; Toyota Technological Institute at Chicago, USA)


 Article: stoc16main-main158-p doi:
On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree
Neeraj Kayal, Chandan Saha, and Sébastien Tavenas
(Microsoft Research, India; Indian Institute of Science, India)


 Article: stoc16main-main214-p doi:
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. Kane and Ryan Williams
(University of California at San Diego, USA; Stanford University, USA)


 Article: stoc16main-main370-p doi:
Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma
Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan
(University of Toronto, Canada; National Institute of Informatics, Japan; Columbia University, USA; Toyota Technological Institute at Chicago, USA)


 Article: stoc16main-main380-p doi:

Session 9

Reed-Muller Codes Achieve Capacity on Erasure Channels
Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke
(Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA)


 Article: stoc16main-main347-p doi:
Explicit Two-Source Extractors and Resilient Functions
Eshan Chattopadhyay and David Zuckerman
(University of Texas at Austin, USA)


 Article: stoc16main-main134-p doi:
Graph Isomorphism in Quasipolynomial Time [Extended Abstract]
László Babai
(University of Chicago, USA)


 Article: stoc16main-main187-p doi:

Session 10A

Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
Sepehr Assadi, Sanjeev Khanna, and Yang Li
(University of Pennsylvania, USA)


 Article: stoc16main-main319-p doi:
Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime
Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký
(IIT Kanpur, India; Charles University in Prague, Czechia)


 Article: stoc16main-main330-p doi:
On Approximating Functions of the Singular Values in a Stream
Yi Li and David P. Woodruff
(Facebook, USA; IBM Research, USA)


 Article: stoc16main-main341-p doi:
Beating CountSketch for Heavy Hitters in Insertion Streams
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff
(Johns Hopkins University, USA; ETH Zurich, Switzerland; IBM Research, USA)


 Article: stoc16main-main240-p doi:

Session 10B

Bipartite Perfect Matching Is in Quasi-NC
Stephen Fenner, Rohit Gurjar, and Thomas Thierauf
(University of South Carolina, USA; Aalen University, Germany)


 Article: stoc16main-main260-p doi:
Exact Algorithms via Monotone Local Search
Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh
(University of Bergen, Norway; UNSW, Australia; Data61, Australia; Institute of Mathematical Sciences at Chennai, India)


 Article: stoc16main-main216-p doi:
Basis Collapse for Holographic Algorithms over All Domain Sizes
Sitan Chen
(Harvard University, USA)


 Article: stoc16main-main206-p doi:
Base Collapse of Holographic Algorithms
Mingji Xia
(Institute of Software at Chinese Academy of Sciences, China)


 Article: stoc16main-main249-p doi:
Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs
(University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France)


 Article: stoc16main-main123-p doi:

Session 11A

Semidefinite Programs on Sparse Random Graphs and Their Application to Community Detection
Andrea Montanari and Subhabrata Sen
(Stanford University, USA)


 Article: stoc16main-main209-p doi:
How Robust Are Reconstruction Thresholds for Community Detection?
Ankur Moitra, William Perry, and Alexander S. Wein
(Massachusetts Institute of Technology, USA)


 Article: stoc16main-main311-p doi:
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman
(Yale University, USA; Massachusetts Institute of Technology, USA; Georgia Tech, USA)


 Article: stoc16main-main390-p doi:
Parallel Algorithms for Select and Partition with Noisy Comparisons
Mark Braverman, Jieming Mao, and S. Matthew Weinberg
(Princeton University, USA)


 Article: stoc16main-main419-p doi:

Session 11B

Separations in Query Complexity using Cheat Sheets
Scott Aaronson, Shalev Ben-David, and Robin Kothari
(Massachusetts Institute of Technology, USA)


 Article: stoc16main-main423-p doi:
Entangled Simultaneity versus Classical Interactivity in Communication Complexity
Dmitry Gavinsky
(Czech Academy of Sciences, Czechia)


 Article: stoc16main-main203-p doi:
Classical Verification of Quantum Proofs
Zhengfeng Ji
(University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China)


 Article: stoc16main-main364-p doi:
Efficient Quantum Tomography
Ryan O'Donnell and John Wright
(Carnegie Mellon University, USA)


 Article: stoc16main-main191-p doi:
Sample-Optimal Tomography of Quantum States
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu
(Massachusetts Institute of Technology, USA; University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China; University of Oregon, USA; University of Guelph, Canada)


 Article: stoc16main-main351-p doi:

Session 12A

A Duality Based Unified Approach to Bayesian Mechanism Design
Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg
(McGill University, Canada; Microsoft Research, USA; Princeton University, USA)


 Article: stoc16main-main430-p doi:
Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
Shahar Dobzinski
(Weizmann Institute of Science, Israel)


 Article: stoc16main-main296-p doi:
Watch and Learn: Optimizing from Revealed Preferences Feedback
Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu
(University of Pennsylvania, USA; Northeastern University, USA)


 Article: stoc16main-main336-p doi:
The Price of Anarchy in Large Games
Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis
(Tel Aviv University, Israel; Microsoft Research, USA; Stanford University, USA)


 Article: stoc16main-main340-p doi:

Session 12B

Exponential Separation of Communication and External Information
Anat Ganor, Gillat Kol, and Ran Raz
(Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA)


 Article: stoc16main-main164-p doi:
Interactive Compression for Product Distributions
Gillat Kol
(Institute for Advanced Study at Princeton, USA)


 Article: stoc16main-main168-p doi:
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible
Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler
(Princeton University, USA; Tel Aviv University, Israel; Carnegie Mellon University, USA)


 Article: stoc16main-main257-p doi:
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff
(Princeton University, USA; Toyota Technological Institute at Chicago, USA; IBM Research, USA)


 Article: stoc16main-main342-p doi:

Session 13A

A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs and Eric Blais
(CWI, Netherlands; University of Waterloo, Canada)


 Article: stoc16main-main280-p doi:
Relating Two Property Testing Models for Bounded Degree Directed Graphs
Artur Czumaj, Pan Peng, and Christian Sohler
(University of Warwick, UK; TU Dortmund, Germany; Institute of Software at Chinese Academy of Sciences, China)


 Article: stoc16main-main314-p doi:
Algorithmic Stability for Adaptive Data Analysis
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman
(University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA)


 Article: stoc16main-main278-p doi:
The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)


 Article: stoc16main-main218-p doi:
A Size-Free CLT for Poisson Multinomials and Its Applications
Constantinos Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos
(Massachusetts Institute of Technology, USA; Northwestern University, USA)


 Article: stoc16main-main104-p doi:

Session 13B

Algebraic Attacks against Random Local Functions and Their Countermeasures
Benny Applebaum and Shachar Lovett
(Tel Aviv University, Israel; University of California at San Diego, USA)


 Article: stoc16main-main230-p doi:
Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations
Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf
(IBM Research, USA; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)


 Article: stoc16main-main256-p doi:
Watermarking Cryptographic Capabilities
Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs
(Massachusetts Institute of Technology, USA; NTT, Japan; Northeastern University, USA)


 Article: stoc16main-main448-p doi:
Textbook Non-malleable Commitments
Vipul Goyal, Omkant Pandey, and Silas Richelson
(Microsoft Research, India; Drexel University, USA; Massachusetts Institute of Technology, USA)


 Article: stoc16main-main464-p doi:

proc time: 0.2