STOC 2016- Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing

Full Citation in the ACM Digital Library

SESSION: Session 1A

Almost tight bounds for eliminating depth cycles in three dimensions

Geometric median in nearly linear time

Separating subadditive euclidean functionals

Bounded degree cosystolic expanders of every dimension

SESSION: Session 1B

Constant-round interactive proofs for delegating computation

Candidate hard unique game

On the effect of randomness on planted 3-coloring models

Matrix rigidity of random toeplitz matrices

SESSION: Session 2A

Complexity theoretic limitations on learning halfspaces

A cost function for similarity-based hierarchical clustering

The computational power of optimization in online learning

Instance optimal learning of discrete distributions

SESSION: Session 2B

Lift-and-round to improve weighted completion time on unrelated machines

A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies

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

Maximizing determinants under partition constraints

SESSION: Session 3A

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

Repairing Reed-solomon codes

Efficiently decoding Reed-Muller codes from random errors

SESSION: Session 3B

Optimal principal component analysis in distributed and streaming models

Weighted low rank approximations with provable guarantees

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time

SESSION: Session 4A

Two-source dispersers for polylogarithmic entropy and improved ramsey graphs

Non-malleable extractors and codes, with their many tampered extensions

Extractors for sumset sources

SESSION: Session 4B

Parallel exhaustive search without coordination

Beyond matroids: secretary problem and prophet inequality with general constraints

Online matching: haste makes waste!

SESSION: Session 5

A tight space bound for consensus

The 4/3 additive spanner exponent is tight

SESSION: Session 6A

Cell-probe lower bounds for dynamic problems via a new communication model

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

Deterministic decremental single source shortest paths: beyond the o(mn) bound

New deterministic approximation algorithms for fully dynamic matching

SESSION: Session 6B

Algorithmic Bayesian persuasion

The sample complexity of auctions with side information

Do prices coordinate markets?

A discrete and bounded envy-free cake cutting protocol for four agents

SESSION: Session 7A

Distributed (Delta+1)-coloring in sublogarithmic rounds

A lower bound for the distributed Lovász local lemma

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Contention resolution with log-logstar channel accesses

SESSION: Session 7B

Fault tolerant subgraph for single source reachability: generic and optimal

Deterministic and probabilistic binary search in graphs

Ramanujan coverings of graphs

Enumerating parametric global minimum cuts by random interleaving

SESSION: Session 8A

Improved approximation for node-disjoint paths in planar graphs

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting

Approximating connectivity domination in weighted bounded-genus graphs

Routing under balance

SESSION: Session 8B

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

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

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

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

SESSION: Session 9

Reed-Muller codes achieve capacity on erasure channels

Explicit two-source extractors and resilient functions

Graph isomorphism in quasipolynomial time [extended abstract]

SESSION: Session 10A

Tight bounds for single-pass streaming complexity of the set cover problem

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

On approximating functions of the singular values in a stream

Beating CountSketch for heavy hitters in insertion streams

SESSION: Session 10B

Bipartite perfect matching is in quasi-NC

Exact algorithms via monotone local search

Basis collapse for holographic algorithms over all domain sizes

Base collapse of holographic algorithms

Separations in query complexity based on pointer functions

SESSION: Session 11A

Semidefinite programs on sparse random graphs and their application to community detection

How robust are reconstruction thresholds for community detection?

Sparsified Cholesky and multigrid solvers for connection laplacians

Parallel algorithms for select and partition with noisy comparisons

SESSION: Session 11B

Separations in query complexity using cheat sheets

Entangled simultaneity versus classical interactivity in communication complexity

Classical verification of quantum proofs

Efficient quantum tomography

Sample-optimal tomography of quantum states

SESSION: Session 12A

A duality based unified approach to Bayesian mechanism design

Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders

Watch and learn: optimizing from revealed preferences feedback

The price of anarchy in large games

SESSION: Session 12B

Exponential separation of communication and external information

Interactive compression for product distributions

Constant-rate coding for multiparty interactive communication is impossible

Communication lower bounds for statistical estimation problems via a distributed data processing inequality

SESSION: Session 13A

A polynomial lower bound for testing monotonicity

Relating two property testing models for bounded degree directed graphs

Algorithmic stability for adaptive data analysis

The fourier transform of poisson multinomial distributions and its algorithmic applications

A size-free CLT for poisson multinomials and its applications

SESSION: Session 13B

Algebraic attacks against random local functions and their countermeasures

Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations

Watermarking cryptographic capabilities

Textbook non-malleable commitments