List of accepted papers for 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 Verdière, 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

Comments