List of Accepted Papers to STOC 2016


       On Approximating Functions of the Singular Values in a Stream

Yi Li, and David Woodruff


       The Price of Anarchy in Large Games

Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis


       Watch and Learn: Optimizing from Revealed Preferences Feedback

Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu


       Simpler Analysis and Enumeration of Parametric Minimum Cuts

David Karger


       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


       Algorithmic Bayesian Persuasion

Shaddin Dughmi, and Haifeng Xu


       Classical Verification of Quantum Proofs

Zhengfeng Ji


       Matrix Rigidity of Random Toeplitz Matrices

Oded Goldreich, and Avishay Tal


       Sample-optimal tomography of quantum states

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu


       Reed-Muller Codes Achieve Capacity on Erasure Channels

Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, and Rudiger Urbanke


       Streaming algorithms for embedding and computing edit distance in the low distance regime

Diptarka Chakraborty, Elazar Goldenberg, and Michal Kouck


       Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem

Sepehr Assadi, Sanjeev Khanna, and Yang Li


       Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders

Shahar Dobzinski


       New Deterministic Approximation Algorithms for Fully Dynamic Matching

Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai


       A Polynomial Lower Bound for Testing Monotonicity

Aleksandrs Belovs, and Eric Blais


       Algorithmic Stability for Adaptive Data Analysis

Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman


       A Lower Bound for the Distributed Lovsz Local Lemma

Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiinen, Joel Rybicki, Jukka Suomela, and Jara Uitto


       Separating subadditive Euclidean functionals

Alan Frieze, and Wesley Pegden


       Relating Two Property Testing Models for Bounded Degree Directed Graphs

Artur Czumaj, Pan Peng, and Christian Sohler


       Ramanujan Coverings of Graphs

Chris Hall, Doron Puder, and William F. Sawin


       How Robust are Reconstruction Thresholds for Community Detection?

Ankur Moitra, William Perry, and Alexander S. Wein


       Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines

Nikhil Bansal, Aravind Srinivasan, and Ola Svensson


       Approximating connectivity domination in weighted bounded-genus graphs

Vincent Cohen-Addad, ric Colin de Verdire, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld


       Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

Daniel M. Kane, and Ryan Williams


       Watermarking Cryptographic Capabilities

Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs


       Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time

Michael Kapralov


       Maximizing Determinants under Partition Constraints

Aleksandar Nikolov, and Mohit Singh


       Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal

Baswana Surender, Choudhary Keerti, and Roditty Liam


       Constant-Round Interactive Proofs for Delegating Computation

Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum


       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


       Textbook Non-Malleable Commitments

Vipul Goyal, Omkant Pandey, and Silas Richelson


       Deterministic and Probabilistic Binary Search in Graphs

Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal


       Contention Resolution with Log-Logstar Channel Accesses

Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young


       Routing under Balance

Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford


       Geometric Median in Nearly Linear Time

Michael Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford


       Optimal Principal Component Analysis in Distributed and Streaming Models

Christos Boutsidis, David P. Woodruff, and Peilin Zhong


       Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman


       Weighted Low Rank Approximations with Provable Guarantees

Ilya Razenshteyn, Zhao Song, and David P. Woodruff


       A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai


       Poly-logarithmic Frege depth lower bounds via an expander switching lemma

Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan


       Instance Optimal Learning of Discrete Distributions

Gregory Valiant, and Paul Valiant


       Parallel Algorithms for Select and Partition with Noisy Comparisons

Mark Braverman, Jieming Mao, and S. Matthew Weinberg


       A Duality Based Unified Approach to Bayesian Mechanism Design

Yang Cai, Nikhil Devanur, and S. Matthew Weinberg


       Separations in query complexity using cheat sheets

Scott Aaronson, Shalev Ben-David, and Robin Kothari


       Extractors for Sumset Sources

Eshan Chattopadhyay, and Xin Li


       A Tight Space Bound for Consensus

Leqi Zhu


       Bipartite Perfect Matching is in quasi-NC

Stephen Fenner, Rohit Gurjar, and Thomas Thierauf


       Near-optimal small-depth lower bounds for small distance connectivity

Xi Chen, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan


       Distributed (\Delta+1)-Coloring in Sublogarithmic Rounds

David G. Harris, Johannes Schneider, and Hsin-Hao Su


       A Lasserre-based (1+epsilon)-approximation for Pm | p_j=1, prec | C_max

Elaine Levey, and Thomas Rothvoss


       Candidate Hard Unique Game

Subhash Khot, and Dana Moshkovitz


       Exponential Separation of Communication and External Information

Anat Ganor, Gillat Kol, and Ran Raz


       The Computational Power of Optimization in Online Learning

Elad Hazan, and Tomer Koren


       Beyond matroids: secretary problem and prophet inequality with general constraints.

Aviad Rubinstein


       Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions

Boris Aronov, and Micha Sharir


       Improved Approximation for Node-Disjoint Paths in Planar Graphs

Julia Chuzhoy, David H. K. Kim, and Shi Li


       Interactive Compression for Product Distributions

Gillat Kol


       Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

Gil Cohen


       Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer


       High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf


       A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents

Haris Aziz, and Simon Mackenzie


       Deterministic Decremental Single Source Shortest Paths: Beyond the $O(mn)$ Bound

Aaron Bernstein, and Shiri Chechik


       Complexity theoretic limitations on learning halfspaces

Amit Daniely


       Separations in Query Complexity Based on Pointer Functions

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs


       Repairing Reed-Solomon Codes

Venkatesan Guruswami, and Mary Wootters


       Explicit Two-Source Extractors and Resilient Functions

Eshan Chattopadhyay, and David Zuckerman


       A cost function for similarity-based hierarchical clustering

Sanjoy Dasgupta


       Efficiently decoding Reed-Muller codes from random errors

Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk


       Parallel Exhaustive Search without Coordination

Pierre Fraigniaud, Amos Korman, and Yoav Rodeh


       Graph Isomorphism in Quasipolynomial Time

Laszlo Babai


       Online Matching: Haste makes Waste!

Yuval Emek, Shay Kutten, and Roger Wattenhofer


       Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model

Huacheng Yu


       The 4/3 Additive Spanner Exponent is Tight

Amir Abboud, and Greg Bodwin


       Algebraic Attacks against Random Local Functions and Their Countermeasures

Benny Applebaum, and Shachar Lovett


       Beating CountSketch for Heavy Hitters in Insertion Streams

Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff


       Do Prices Coordinate Markets?

Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Ricky Vohra


       Constant-rate coding for multiparty interactive communication is impossible

Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler


       Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations

Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf


       On the effect of randomness on planted 3-coloring models

Roee David, and Uriel Feige


       Base collapse of holographic algorithms

Mingji Xia


       The Sample Complexity of Auctions with Side Information

Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas


       The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

Ilias Diakonikolas, Daniel Kane, and Alistair Stewart


       Basis Collapse for Holographic Algorithms Over All Domain Sizes

Sitan Chen


       Entangled simultaneity versus classical interactivity in communication complexity

Dmitry Gavinsky


       Efficient quantum tomography

Ryan O'Donnell, and John Wright


       Bounded Degree Cosystolic Expanders of Every Dimension

Shai Evra, and Tali Kaufman


       Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Eshan Chattopadhyay, Vipul Goyal, and Xin Li


       Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection

Andrea Montanari, and Subhabrata Sen


       Exact Algorithms via Monotone Local Search

Fedor Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh


       On the size of homogeneous and of depth four formulas with low individual degree

Neeraj Kayal, Chandan Saha, and Sebastien Tavenas


       A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting

MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Daniel Marx


       A Size-Free CLT for Poisson Multinomials and its Applications

Costis Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos