STOC 2019 Accepted Papers

Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective

Vishesh Jain (MIT), Frederic Koehler (MIT), Andrej Risteski (MIT)

Algebraic approach to promise constraint satisfaction

Jakub Bulín (Charles University), Andrei Krokhin (University of Durham), Jakub Opršal (University of Durham)

Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications)

Ilias Diakonikolas (USC), Daniel Kane (UCSD)

Testing Graphs in Vertex-Distribution-Free Models

Oded Goldreich (Weizmann Institute of Science)

Solving Linear Programs in the Current Matrix Multiplication Time

Michael Cohen (MIT), Yin Tat Lee (University of Washington), Zhao Song (University of Washington & UT-Austin)

An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model

Eric Balkanski (Harvard University), Aviad Rubinstein (Stanford University), Yaron Singer (Harvard University)

Algorithmic Pirogov-Sinai Theory

Tyler Helmuth (University of Bristol), Will Perkins (University of Illinois at Chicago), Guus Regts (University of Amsterdam)

Quantum Weak Coin Flipping

Atul Singh Arora (Université libre de Bruxelles), Jérémie Roland (Université libre de Bruxelles), Stephan Weis (Universidade de Coimbra)

Optimal terminal dimensionality reduction in Euclidean space

Shyam Narayanan (Harvard University), Jelani Nelson (Harvard University)

Which Properties are Testable in the Vertex-Distribution-Free Model

Lior Gishboliner (Tel Aviv University), Asaf Shapira (Tel Aviv University)

Non-Gaussian Component Analysis using Entropy Methods

Navin Goyal (Microsoft Research India), Abhishek Shetty (Microsoft Research India)

A quantum-inspired classical algorithm for recommendation systems

Ewin Tang (University of Texas at Austin)

Separating Monotone VP and VNP

Amir Yehudayoff (Technion-IIT)

Private PAC learning implies finite Littlestone Dimension

Noga Alon (Princeton University), Roi Livni (Tel Aviv University), Maryanthe Malliaris (Chicago University), Shay Moran (Princeton University)

On a generalization of iterated and randomized rounding

Nikhil Bansal (CWI and TU Eindhoven)

Competitively Chasing Convex Bodies

Sebastien Bubeck (Microsoft Research), Yin Tat Lee (University of Washington), Yuanzhi Li (Stanford University), Mark Sellke (Stanford University)

Oracle Separation of BQP and PH

Ran Raz (Princeton University), Avishay Tal (Stanford University)

Almost Optimal Distance Oracles for Planar Graphs

Panagiotis Charalampopoulos (Department of Informatics), Paweł Gawrychowski (Institute of Computer Science), Shay Mozes (Efi Arazi School of Computer Science), Oren Weimann (Department of Computer Science), Shay Mozes (IDC Herzliya)

Local Decodability of the Burrows-Wheeler Transform

Sandip Sinha (Columbia University), Omri Weinstein (Columbia University)

Oblivious Dimension Reduction for k-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma

Luca Becchetti (Sapienza), Marc Bury (Zalando SE), Vincent Cohen-Addad (CNRS), Fabrizio Grandoni (IDSIA), Chris Schwiegelshohn (Sapienza)

Pseudorandom Generators for Width-3 Branching Programs

Raghu Meka (UCLA), Omer Reingold (Stanford University), Avishay Tal (Stanford University)

A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems

Julia Chuzhoy (Toyota Technological Institute at Chicago), Sanjeev Khanna (University of Pennsylvania)

Fooling Polytopes

Ryan O'Donnell (Carnegie Mellon University), Rocco A. Servedio (Columbia University), Li-Yang Tan (Stanford University)

Approximation Algorithms for Minimum Norm and Ordered Optimization Problems

Deeparnab Chakrabarty (Dartmouth College), Chaitanya Swamy (University of Waterloo)

DNF sparsification beyond sunflowers

Shachar Lovett (UC San Diego), Jiapeng Zhang (UC San Diego)

Planar Graphs of Bounded Degree have Constant Queue Number

Michael Bekos (University of Tübingen), Henry Förster (University of Tübingen), Martin Gronemann (University of Cologne), Tamara Mchedlidze (Karlsruhe Institute of Technology), Fabrizio Montecchiani (University of Perugia), Chrysanthi Raftopoulou (National Technical University of Athens), Torsten Ueckerdt (Karlsruhe Institute of Technology)

Settling the Sample Complexity of Single-parameter Revenue Maximization

Chenghao Guo (IIIS), Zhiyi Huang (University of Hong Kong), Xinzhi Zhang (IIIS)

Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time

Aaron Bernstein (Rutgers University), Danupon Nanongkai (KTH Royal Institute of Technology)

Unconstrained Submodular Maximization with Constant Adaptive Complexity

Lin Chen (Yale University), Moran Feldman (Open University of Israel), Amin Karbasi (Yale University)

Planar point sets determine many pairwise crossing segments

János Pach (EPFL), Natan Rubin (Ben-Gurion University), Gábor Tardos (Renyi Institute)

Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles

Mina Dalirrooyfard (MIT), Thuy Duong Vuong (MIT), Virginia Vassilevska Williams (MIT)

Random walks and forbidden minors II: a $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs

Akash Kumar (Purdue University), C. Seshadhri (University of California), Andrew Stolman (University of California)

Tight Approximation Ratio of Anonymous Pricing

Yaonan Jin (Department of IEDA), Pinyan Lu (ITCS), Qi Qi (Department of IEDA), Zhihao Gavin Tang (Department of Computer Science), Tao Xiao (Department of Computer Science)

Communication Complexity of Estimating Correlations

Uri Hadar (Tel Aviv University), Jingbo Liu (MIT), Yury Polyanskiy (MIT), Ofer Shayevitz (Tel Aviv University)

Bootstrapping Results for Threshold Circuits Just Beyond Known Lower Bounds

Lijie Chen (MIT), Roei Tell (Weizmann Institute of Science)

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches

Aris Filos-Ratsikas (Ecole Polytechnique Federale de Lausanne), Paul W. Goldberg (University of Oxford)

Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time

Aaron Bernstein (Department of Computer Science), Maximilian Probst (Department of Computer Science), Christian Wulff-Nilsen (Department of Computer Science)

The Structure of Optimal Private Tests for Simple Hypotheses

Clement Canonne (Stanford University), Gautam Kamath (Simons Institute for the Theory of Computing), Audra McMillan (Boston University and Northeastern University), Adam Smith (Boston University), Jonathan Ullman (Northeastern University)

Lower Bounds for External Memory Sorting via Network Coding

Alireza Farhadi (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland), Kasper Green Larsen (Aarhus University), Elaine Shi (Cornell University)

A unifying method for the design of algorithms canonizing combinatorial objects

Pascal Schweitzer (TU Kaiserslautern), Daniel Wiebking (RWTH Aachen University)

A Fixed-Depth Size-Hierarchy Theorem for $AC^0[\oplus]$ via the Coin Problem

Nutan Limaye (IIT Bombay), Karteek Sreenivasaiah (IIT Hyderabad), Srikanth Srinivasan (IIT Bombay), Utkarsh Tripathi (IIT Bombay), S. Venkitesh (IIT Bombay)

A Strongly Polynomial Algorithm for Linear Exchange Markets

Jugal Garg (University of Illinois at Urbana-Champaign), László A. Végh (London School of Economics and Political Science)

Sylvester-Gallai type theorems for quadratic polynomials

Amir Shpilka (Tel-Aviv University)

Achieving Optimal Backlog in Mullti-Processor Cup Games

Michael A. Bender (Stony Brook University), Martin Farach-Colton (Rutgers University), William Kuszmaul (Massachusetts Institute of Technology)

Quantum proof systems for iterated exponential time, and beyond  

Joseph Fitzsimons (Singapore University of Technology and Design), Zhengfeng Ji (University of Technology Sydney), Thomas Vidick ( CalTech ), Henry Yuen (University of Toronto)

Quantum state certification

Costin Bădescu (Carnegie Mellon University), Ryan O'Donnell (Carnegie Mellon University), John Wright (Massachusetts Institute of Technology)

Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels

Arun Ganesh (UC Berkeley), Qiuyi (Richard) Zhang (UC Berkeley)

Distributed Edge Connectivity in Sublinear Time

Mohit Daga (KTH Royal Institute of Technology), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute)

Bridging between 0/1 and Linear Programming via Random Walks

Joshua Brakensiek (Stanford University), Venkatesan Guruswami (Carnegie Mellon University)

Static Data Structure Lower Bounds Imply Rigidity

Zeev Dvir (Princeton University), Alexander Golovnev (Harvard University), Omri Weinstein (Columbia University)

$O(\log^2k/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.

Fabrizio Grandoni (IDSIA), Bundit Laekhanukit (Shanghai University of Finance and Economics), Shi Li (University at Buffalo)

Performance of Johnson–Lindenstrauss Transform for k-Means and k-Medians Clustering

Konstantin Makarychev (Northwestern University), Yury Makarychev (TTIC), Ilya Razenshteyn (Microsoft Research)

Testing Unateness Nearly Optimally

Xi Chen (Columbia University), Erik Waingarten (Columbia University)

Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition

Huacheng Yu (Harvard University)

The Log-Approximate-Rank Conjecture is False

Arkadev Chattopadhyay (School of Technology and Computer Science), Nikhil Mande (School of Technology and Computer Science), Suhail Sherif (School of Technology and Computer Science)

The Communication Complexity of Local Search

Yakov Babichenko (Technion), Shahar Dobzinski (Weizmann Institute), Noam Nisan (Hebrew University of Jerusalem)

Stronger L2/L2 Compressed Sensing; Without Iterating

Vasileios Nakos (Harvard University), Zhao Song (UT-Austin)

Canonical form for graphs in quasipolynomial time

Laszlo Babai (University of Chicago)

Spectral Methods from Tensor Networks

Ankur Moitra (MIT), Alexander S. Wein (Courant Institute)

Planar Diameter via Metric Compression

Jason Li (CMU), Merav Parter (Weizmann Institute)

Faster $k$-SAT algorithms using biased-PPSZ

Thomas Dueholm Hansen (University of Copenhagen), Haim Kaplan (Tel Aviv University), Or Zamir (Tel Aviv University), Uri Zwick (Tel Aviv University)

Reconstruction of non-degenerate homogeneous depth three circuits

Neeraj Kayal (Microsoft Research India), Chandan Saha (Indian Institute of Science)

Polynomial Pass Lower bounds for Graph Streaming Algorithms

Sepehr Assadi (Princeton University), Yu Chen (University of Pennsylvania), Sanjeev Khanna (University of Pennsylvania)

Regression from Dependent Observations

Constantinos Daskalakis (MIT), Nishanth Dikkala (MIT), Ioannis Panageas (SUTD)

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Haim Avron (Tel Aviv University), Michael Kapralov (École Polytechnique Fédérale de Lausanne), Cameron Musco (Microsoft Research), Christopher Musco (Princeton University), Ameya Velingker (École Polytechnique Fédérale de Lausanne), Amir Zandieh (École Polytechnique Fédérale de Lausanne)

An Optimal Space Lower Bound for Approximating MAX-CUT

Michael Kapralov (EPFL), Dmitry Krachun (University of Geneva)

Dynamic Sampling from Graphical Models

Weiming Feng (Nanjing University), Nisheeth K. Vishnoi (Yale University), Yitong Yin (Nanjing University)

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

András Gilyén (QuSoft), Yuan Su (QuICS), Guang Hao Low (QuArC), Nathan Wiebe (QuArC)

The Parallel Repetition of Non-Signaling Games: Counterexamples and Dichotomy

Justin Holmgren (Princeton University), Lisa Yang (MIT)

String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure

Dominik Kempa (University of Warwick), Tomasz Kociumaka (University of Warsaw and Bar-Ilan University)

The Reachability Problem for Petri Nets is Not Elementary

Wojciech Czerwinski (University of Warsaw), Slawomir Lasota (University of Warsaw), Ranko Lazic (University of Warwick), Jerome Leroux (CNRS and University of Bordeaux), Filip Mazowiecki (University of Bordeaux)

The Online k-Taxi Problem

Christian Coester (University of Oxford), Elias Koutsoupias (University of Oxford)

Near-Linear Time Insertion-Deletion Codes and (1+$\varepsilon$)-Approximating Edit Distance via Indexing

Bernhard Haeupler (Carnegie Mellon University), Aviad Rubinstein (Stanford University), Amirbehshad Shahrasbi (Carnegie Mellon University)

Learning Restricted Boltzmann Machines via Influence Maximization

Guy Bresler (MIT), Frederic Koehler (MIT), Ankur Moitra (MIT)

Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max

Karl Bringmann (Max Planck Institute for Informatics), Marvin Kunnemann (Max Planck Institute for Informatics), Karol Wegrzycki (University of Warsaw)

On the Approximation Resistance of Balanced Linear Threshold Functions

Aaron Potechin (University of Chicago)

Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications

Sitan Chen (MIT), Ankur Moitra (MIT)

Dynamic Set Cover: Improved Algorithms & Lower Bounds

Amir Abboud (IBM Almaden Research Center), Raghavendra Addanki (University of Massachusetts Amherst), Fabrizio Grandoni (IDSIA), Debmalya Panigrahi (Duke University), Barna Saha (University of Massachusetts Amherst)

Private Selection from Private Candidates

Jingcheng Liu (UC Berkeley), Kunal Talwar (Google Brain)

Gentle Measurement of Quantum States and Differential Privacy

Scott Aaronson (University of Texas at Austin), Guy Rothblum (Weizmann Institute of Science)

Fully Dynamic Spectral Vertex Sparsifiers and Applications

David Durfee (Georgia Tech), Yu Gao (Georgia Tech), Gramoz Goranci (University of Vienna), Richard Peng (Georgia Tech)

Fiat-Shamir: From Practice to Theory

Ran Canetti (BU), Yilei Chen (Visa Research), Justin Holmgren (Princeton), Alex Lombardi (MIT), Guy N. Rothblum (Weizmann Institute of Science), Ron D. Rothblum (Technion), Daniel Wichs (Northeastern)

Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions

Sebastian Forster (University of Salzburg), Gramoz Goranci (University of Vienna)

Weak Zero-Knowledge Beyond the Black-Box Barrier

Nir Bitansky (TAU), Dakshita Khurana (MSR), Omer Paneth (MIT)

Capacity lower bound for the Ising perceptron

Jian Ding (University of Pennsylvania), Nike Sun (Massachusetts Institute of Technology)

Good approximate quantum LDPC codes from spacetime circuit Hamiltonians

Thomas C. Bohdanowicz (California Institute of Technology), Elizabeth Crosson (University of New Mexico), Chinmay Nirkhe (University of California), Henry Yuen (University of Toronto)

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid

Nima Anari (Stanford University), Kuikui Liu (University of Washington), Shayan Oveis Gharan (University of Washington), Cynthia Vinzant (North Carolina State University)

Hamiltonian simulation with nearly optimal dependence on spectral norm

Guang Hao Low (Microsoft Research)

An Exponential Lower Bound on the Sub-Packetization of MSR Codes

Omar Alrabiah (Carnegie Mellon University), Venkatesan Guruswami (Carnegie Mellon University)

$1+\epsilon$ Approximation of Tree Edit Distance in Quadratic Time

Mahdi Boroujeni (University of Maryland), Mohammad Ghodsi (University of Maryland), MohammadTaghi HajiAghayi (University of Maryland), Saeed Seddighin (University of Maryland)

Submodular Maximization with Matroid and Packing Constraints in Parallel

Alina Ene (Boston University), Huy L. Nguyen (Northeastern University), Adrian Vladu (Boston University)

Computing Quartet Distance is Equivalent to Counting 4-Cycles

Bartłomiej Dudek (University of Wrocław), Paweł Gawrychowski (University of Wrocław)

Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions

Andre Linhares (University of Waterloo), Chaitanya Swamy (University of Waterloo)

Quantum Lov{\'a}sz Local Lemma: Shearer's Bound is Tight

Kun He (ICT), Qian Li (Alibaba Group), Xiaoming Sun (ICT), Jiapeng Zhang (University of California)

Towards the Locality of Vizing's Theorem

Hsin-Hao Su (Boston College), Hoa T. Vu (Boston College)

Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme

Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute at Chicago), Sorrachai Yingchareonthawornchai (Michigan State University)

The Number of Minimum k-Cuts: Improving the Karger-Stein Bound

Anupam Gupta (CMU), Euiwoong Lee (NYU), Jason Li (CMU)

Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes

Dylan McKay (Massachusetts Institute of Technology), Cody Murray (Simons Institute), Ryan Williams (Massachusetts Institute of Technology)

On Approximating the Covering Radius and Finding Dense Lattice Subspaces

Daniel Dadush (CWI)

Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation

Moses Charikar (Stanford University), Kirankumar Shiragur (Stanford University), Aaron Sidford (Stanford University)

Explicit $N$-vertex graphs with maximum degree $K$ and diameter $[1+o(1)]\log_{K-1} N$ for each $K-1$ a prime power

Michael Capalbo (CCS)

Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir

Arka Rai Choudhuri (Johns Hopkins University), Pavel Hubacek (Charles University), Chethan Kamath (IST Austria), Krzysztof Pietrzak (IST Austria), Alon Rosen (IDC Herzliya), Guy N. Rothblum (Weizmann Institute of Science)

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Joshua Brakensiek (Stanford University), Sivakanth Gopi (Microsoft Research), Venkatesan Guruswami (Carnegie Mellon University)

New Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity Search

Alessio Conte (National Institute of Informatics), Takeaki Uno (National Institute of Informatics)

Memory-Sample Tradeoffs for Linear Regression with Small Error

Vatsal Sharan (Stanford University), Aaron Sidford (Stanford University), Gregory Valiant (Stanford University)

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

Adam Bene Watts (Massachusetts Institute of Technology), Robin Kothari (Microsoft Research), Luke Schaeffer (Massachusetts Institute of Technology), Avishay Tal (Stanford University)

Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items

Hedyeh Beyhaghi (Cornell University), S. Matthew Weinberg (Princeton University)

Parallelizing greedy for submodular set function maximization in matroids and beyond

Chandra Chekuri (UIUC), Kent Quanrud (UIUC)

Why Extension-Based Proofs Fail

Dan Alistarh (IST Austria), James Aspnes (Yale University), Faith Ellen (University of Toronto), Rati Gelashvili (University of Toronto), Leqi Zhu (University of Toronto)

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

Alexander A. Sherstov (UCLA), Pei Wu (UCLA)

Polylogarithmic approximation for Euler genus on bounded degree graphs

Ken-ichi Kawarabayashi (National Institute of Informatics), Anastasios Sidiropoulos (University of Illinois at Chicago)

Flows in Almost Linear Time via Adaptive Preconditioning

Rasmus Kyng (Harvard), Richard Peng (Georgia Tech), Sushant Sachdeva (University of Toronto), Di Wang (Georgia Tech)

How to Delegate Computations Publicly

Yael Tauman Kalai (Microsoft Research), Omer Paneth (MIT), Lisa Yang (MIT)