STOC 2017- Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

Full Citation in the ACM Digital Library

SESSION: Invited Talks

Recent trends in decentralized cryptocurrencies (invited talk)

Why prices need algorithms (invited talk)

Optimizing tree pattern queries: why cutting is not enough (invited talk)

Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk)

Fast convergence of learning in games (invited talk)

Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk)

The next 700 network programming languages (invited talk)

Practical post-quantum key agreement from generic lattices (invited talk)

SESSION: Session 1A

Twenty (simple) questions

Kolmogorov complexity version of Slepian-Wolf coding

Synchronization strings: codes for insertions and deletions approaching the Singleton bound

SESSION: Session 1B

Learning from untrusted data

Beating 1-1/e for ordered prophets

Kernel-based methods for bandit convex optimization

SESSION: Session 1C

New hardness results for routing on disjoint paths

A simpler and faster strongly polynomial algorithm for generalized flow maximization

Finding even cycles faster via capped k-walks

SESSION: Session 2A

Strongly refuting random CSPs below the spectral threshold

Sum of squares lower bounds for refuting any CSP

Information-theoretic thresholds from the cavity method

SESSION: Session 2B

Bernoulli factories and black-box reductions in mechanism design

Simple mechanisms for subadditive buyers via duality

Stability of service under time-of-use pricing

SESSION: Session 2C

Faster space-efficient algorithms for subset sum and k-sum

Homomorphisms are a good basis for counting small subgraphs

Lossy kernelization

SESSION: Session 3: STOC Best Papers

Explicit, almost optimal, epsilon-balanced codes

Deciding parity games in quasipolynomial time

A weighted linear matroid parity algorithm

SESSION: Session 4A

Exponential separation of quantum communication and classical information

Compression of quantum multi-prover interactive proofs

Hardness amplification for entangled games via anchoring

The computational complexity of ball permutations

The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation

SESSION: Session 4B

Uniform sampling through the Lovasz local lemma

Approximate counting, the Lovasz local lemma, and inference in graphical models

Real stable polynomials and matroids: optimization and counting

A generalization of permanent inequalities and applications in counting and optimization

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling

SESSION: Session 4C

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

Local max-cut in smoothed polynomial time

Algorithms for stable and perturbation-resilient problems

Area-convexity, l&infty; regularization, and undirected multicommodity flow

SESSION: Session 5A

Pseudorandomness of ring-LWE for any ring and modulus

Non-interactive delegation and batch NP verification from standard computational assumptions

Average-case fine-grained hardness

Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model

SESSION: Session 5B

Removal lemmas with polynomial bounds

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

Online and dynamic algorithms for set cover

Online service with delay

SESSION: Session 5C

The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

On independent sets, 2-to-2 games, and Grassmann graphs

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

How well do local algorithms solve semidefinite programs?

SESSION: Session 6A

A polynomial restriction lemma with applications

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

Probabilistic rank and matrix rigidity

Succinct hitting sets and barriers to proving algebraic circuits lower bounds

Pseudodeterministic constructions in subexponential time

SESSION: Session 6B

An SDP-based algorithm for linear-sized spectral sparsification

Low rank approximation with entrywise l1-norm error

An adaptive sublinear-time block sparse fourier transform

Streaming symmetric norms via measure concentration

Sampling random spanning trees faster than matrix multiplication

SESSION: Session 6C

A time- and message-optimal distributed algorithm for minimum spanning trees

Distributed exact shortest paths in sublinear time

Exponential separations in the energy complexity of leader election

On the complexity of local distributed graph problems

Efficient massively parallel methods for dynamic programming

SESSION: Session 7A

Complexity of short Presburger arithmetic

Linear matroid intersection is in quasi-NC

Randomized polynomial time identity testing for noncommutative circuits

Holographic algorithm with matchgates is universal for planar #CSP over boolean domain

SESSION: Session 7B

Efficient empirical revenue maximization in single-parameter auction environments

The menu-size complexity of revenue approximation

Communication complexity of approximate Nash equilibria

Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria

SESSION: Session 7C

Approximate near neighbors for general symmetric norms

Algorithmic discrepancy beyond partial coloring

Geodesic walks in polytopes

A reverse Minkowski theorem

SESSION: Session 8: Danny Lewin Prize STOC Best Student Paper

Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

SESSION: Session 9A

Efficient quantum tomography II

Quantum entanglement, sum of squares, and the log rank conjecture

Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

A quantum linearity test for robustly verifying entanglement

SESSION: Session 9B

The limitations of optimization from samples

Approximate modularity revisited

Trace reconstruction with exp(O(n1/3)) samples

Optimal mean-based algorithms for trace reconstruction

Provable learning of noisy-OR networks

Time-space hardness of learning sparse parities

SESSION: Session 9C

DecreaseKeys are expensive for external memory priority queues

Set similarity search beyond MinHash

Decremental single-source reachability in planar digraphs

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time

Fully-dynamic minimum spanning forest with improved worst-case update time

SESSION: Session 10A

Improved non-malleable extractors, non-malleable codes and independent source extractors

Towards optimal two-source extractors and Ramsey graphs

Non-malleable codes and extractors for small-depth circuits, and affine functions

An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy

SESSION: Session 10B

Finding approximate local minima faster than gradient descent

Katyusha: the first direct acceleration of stochastic gradient methods

A strongly polynomial algorithm for bimodular integer linear programming

Subquadratic submodular function minimization

SESSION: Session 10C

Addition is exponentially harder than counting for shallow monotone circuits

Strongly exponential lower bounds for monotone computation

Formula lower bounds via the quantum method