STOC 2018 Accepted Papers


Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins (Cornell), Jerry Li (MIT)

The Adaptive Complexity of Maximizing a Submodular Function
Eric Balkanski (Harvard), Yaron Singer (Harvard)

Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas (USC), Daniel M. Kane (UCSD), Alistair Stewart (USC)

Testing Conditional Independence of Discrete Distributions
Clement L. Canonne (Stanford University), Ilias Diakonikolas (USC), Daniel M. Kane (UCSD), Alistair Stewart (USC), Clement Canonne (Columbia University)

List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas (USC), Daniel M. Kane (UCSD), Alistair Stewart (USC)

Discovering the roots: Uniform closure results for algebraic classes under factoring
Pranjal Dutta (Chennai Mathematical Institute), Nitin Saxena (Indian Institute of Technology, Kanpur), Amit Sinhababu (Indian Institute of Technology, Kanpur)

Bootstrapping variables in algebraic circuits
Manindra Agrawal (IIT Kanpur), Sumanta Ghosh (IIT Kanpur), Nitin Saxena ( IIT Kanpur)

Round Compression for Parallel Matching Algorithms
Artur Czumaj (University of Warwick), Jakub Łącki (Google Research, New York), Aleksander Mądry (MIT), Slobodan Mitrović (EPFL), Krzysztof Onak (IBM Research), Piotr Sankowski (University of Warsaw)

Universal points in the asymptotic spectrum of tensors
Matthias Christandl (University of Copenhagen), Péter Vrana (Budapest University of Technology and Economics), Jeroen Zuiddam (CWI Amsterdam)

Capacity upper bounds for deletion-type channels
Mahdi Cheraghchi (Imperial College London)

Near-optimal linear decision trees for k-SUM and related problems
Daniel Kane (UCSD), Shachar Lovett (UCSD), Shay Moran (IAS, Princeton)

Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Julia Chuzhoy (Toyota Technological Institute at Chicago), David H. K. Kim (University of Chicago), Rachit Nimavat (Toyota Technological Institute at Chicago)

Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Yin Tat Lee (University of Washington), Santosh S. Vempala (Georgia Tech)

A homotopy method for lp regression provably beyond self-concordance and in input-sparsity time
Sebastien Bubeck (Microsoft Research), Michael B. Cohen (MIT), Yin Tat Lee (University of Washington), Yuanzhi Li (Princeton)

A Generalized Turan Problem and its Applications
Asaf Shapira (Tel Aviv University), Lior Gishboliner (Tel Aviv University)

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Mark Braverman (Princeton University), Gil Cohen (Princeton University), Sumegha Garg (Princeton University)

Construction of new local spectral high dimensional expanders
Tali Kaufman (Bar-Ilan University), Izhar Oppenheim (Ben-Gurion University)

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun (Princeton), Robin Kothari (Microsoft Research Redmond), Justin Thaler (Georgetown)

Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality
Yannai A. Gonczarowski (The Hebrew University of Jerusalem and Microsoft Research)

Inapproximability of the independent set polynomial in the complex plane
Ivona Bezakova (Rochester Institute of Technology), Andreas Galanis (University of Oxford), Leslie Ann Goldberg (University of Oxford), Daniel Stefankovic (University of Rochester)

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen (Aarhus University), Omri Weinstein (Columbia University), Huacheng Yu (Harvard University)

A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Michael A. Forbes (University of Illinois at Urbana-Champaign), Amir Shpilka (Tel Aviv University)

The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Tsz Chiu Kwok (University of Waterloo), Lap Chi Lau (University of Waterloo), Yin Tat Lee (University of Washington), Akshay Ramachandran (University of Waterloo)

Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz (UC Berkeley), Ahmed El Alaoui (UC Berkeley), Benjamin Recht (UC Berkeley)

k-server via multiscale entropic regularization
Sebastien Bubeck (Microsoft Research), Michael Cohen (MIT), James R. Lee (University of Washington), Yin Tat Lee (University of Washington), Aleksander Madry (MIT)

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity
Eshan Chattopadhyay (Cornell University and IAS), Pooya Hatami (University of Texas at Austin), Omer Reingold (Stanford University), Avishay Tal (Stanford University)

Shadow Tomography of Quantum States
Scott Aaronson (UT Austin)

Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur (Weizmann Institute of Science), Subhash Khot (New York University), Guy Kindler (The Hebrew University of Jerusalem), Dor Minzer (Tel Aviv University), Muli Safra (Tel Aviv University)

On Non-Optimally Expanding Sets in Grassmann Graphs
Irit Dinur (Weizmann Institute of Science), Subhash Khot (New York University), Guy Kindler (The Hebrew University of Jerusalem), Dor Minzer (Tel Aviv University), Muli Safra (Tel Aviv University)

Metric Embedding via Shortest Path Decompositions
Ittai Abraham (VMWare), Arnold Filtser (Ben-Gurion University of the Negev), Anupam Gupta (Carnegie Mellon University), Ofer Neiman (Ben-Gurion University of the Negev)

On Approximating the Number of k-cliques in Sublinear Time
Talya Eden (Tel Aviv University), Dana Ron (Tel Aviv University), C. Seshadhri (University of California, Santa Cruz)

Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek (Technion), Shay Kutten (Technion), Ron Lavi (Technion), Yangguang Shi (Technion)

At the Roots of Dictionary Compression: String Attractors
Dominik Kempa (University of Helsinki), Nicola Prezza (Technical University of Denmark)

General Strong Polarization
Jarosław Błasiok (Harvard), Venkatesan Guruswami (CMU), Preetum Nakkiran (Harvard), Atri Rudra (University at Buffalo, SUNY), Madhu Sudan (Harvard)

Universal Protocols for Information Dissemination using Emergent Signals
Bartlomiej Dudek (University of Wroclaw), Adrian Kosowski (Inria Paris)

The minimum Euclidean-norm point in a convex polytope: Wolfe’s combinatorial algorithm is exponential
Jesus De Loera (University of California, Davis), Jamie Haddock (University of California, Davis), Luis Rademacher (University of California, Davis)

Quantified Derandomization of Linear Threshold Circuits
Roei Tell (Weizmann Institute of Science)

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson (EPFL), Jakub Tarnawski (EPFL), László Végh (London School of Economics)

A Friendly Smoothed Analysis of the Simplex Method
Daniel Dadush (CWI), Sophie Huiberts (CWI)

Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi (Columbia University), Konstantin Makarychev (Northwestern University), Yury Makarychev (TTIC), Ilya Razenshteyn (Columbia University)

Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty (Charles University, Prague), Lior Kamma (MADALGO. Aarhus University), Kasper Green Larsen (MADALGO. Aarhus University)

Generalized matrix completion and algebraic natural proofs
Markus Blaeser (Saarland University), Christian Ikenmeyer (Max-Planck-Institute for Informatics), Gorav Jindal (Max-Planck-Institute for Informatics), Vladimir Lysikov (Saarland University)

Sparse Kneser graphs are Hamiltonian
Torsten Mütze (Technische Universität Berlin), Jerri Nummenpalo (ETH Zurich), Bartosz Walczak (Jagiellonian University)

Shape of Diffusion and Size of Monochromatic Region of a Two-Dimensional Spin System
Hamed Omidvar (UC San Diego), Massimo Franceschetti (UC San Diego)

Monotone Circuit Lower Bounds from Resolution
Ankit Garg (Microsoft Research New England), Mika Göös (Harvard University), Pritish Kamath (MIT), Dmitry Sokolov (KTH)

(Gap/S)ETH Hardness of SVP
Divesh Aggarwal (Centre for Quantum Technologies, NUS), Noah Stephens-Davidowitz (Princeton University)

Distribution-free Junta Testing
Zhengyang Liu (Shanghai Jiao Tong University), Xi Chen (Columbia University), Rocco A. Servedio (Columbia University), Ying Sheng (Columbia University), Jinyu Xie (Columbia University)

Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal (UT Austin), Venkata Koppula (UT Austin), Brent Waters (UT Austin)

Data-Dependent Hashing via Nonlinear Spectral Gaps
Alexandr Andoni (Columbia University), Assaf Naor (Princeton University), Aleksandar Nikolov (University of Toronto), Ilya Razenshteyn (Columbia University), Erik Waingarten (Columbia University)

A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin (University of Washington), Shayan Oveis Gharan (University of Washington), Robbie Weber (University of Washington)

The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal (TU Eindhoven), Daniel Dadush (CWI Amsterdam), Shashwat Garg (TU Eindhoven), Shachar Lovett (University of California, San Diego)

An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild (University of California, Berkeley)

Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg (Eindhoven University of Technology), Hans L. Bodlaender (Utrecht University and Eindhoven University of Technology), Sándor Kisfaludi-Bak (Eindhoven University of Technology), Dániel Marx (Hungarian Academy of Sciences (MTA SZTAKI)), Tom C. van der Zanden (Utrecht University)

Clique Is Hard on Average for Regular Resolution
Albert Atserias (Universitat Politècnica de Catalunya), Ilario Bonacina (Universitat Politècnica de Catalunya), Susanna F. de Rezende (KTH Royal Institute of Technology), Massimo Lauria (Sapienza Università di Roma), Jakob Nordström (KTH Royal Institute of Technology), Alexander Razborov (University of Chicago)

How to Match when All Vertices Arrive Online
Zhiyi Huang (The University of Hong Kong), Ning Kang (The University of Hong Kong), Zhihao Gavin Tang (The University of Hong Kong), Xiaowei Wu (The University of Hong Kong), Yuhao Zhang (The University of Hong Kong), Xue Zhu (The University of Hong Kong)

New Classes of Distributed Time Complexity
Alkida Balliu (Aalto University), Juho Hirvonen (University of Freiburg), Janne H. Korhonen (Aalto University), Tuomo Lempiäinen (Aalto University), Dennis Olivetti (Aalto University), Jukka Suomela (Aalto University)

Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman (MIT), Joshua R. Wang (Stanford University), Huacheng Yu (Harvard University)

Smooth heaps and a dual view of self-adjusting data structures
László Kozma (TU Eindhoven), Thatchaphol Saranurak (KTH Royal Institute of Technology, Stockholm)

Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev
Yin Tat Lee (University of Washington), Santosh S. Vempala (Georgia Tech)

The Art Gallery Problem is ∃ℝ-complete
Mikkel Abrahamsen (University of Copenhagen), Anna Adamaszek (University of Copenhagen), Tillmann Miltzow (Universite libre de Bruxelles)

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
Nir Bitansky (Tel Aviv University), Yael Tauman Kalai (Microsoft), Omer Paneth (MIT)

Non-Malleable Secret Sharing
Vipul Goyal (CMU), Ashutosh Kumar (UCLA, Microsoft Research, India)

Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay (TIFR, Mumbai), Michal Koucký (Charles University, Prague), Bruno Loff (INESC-Tec and University of Porto), Sagnik Mukhopadhyay (KTH Royal Institute of Technology)

Fast Algorithms for Knapsack via Convolution and Prediction
MohammadHossein Bateni (Google), MohammadTaghi Hajiaghayi (University of Maryland), Saeed Seddighin (University of Maryland), Cliff Stein (Columbia University)

Fast Fencing
Mikkel Abrahamsen (University of Copenhagen), Anna Adamaszek (University of Copenhagen), Karl Bringmann (Max Planck Institute for Informatics, Saarbrücken), Vincent Cohen-Addad (Université Paris-Sorbonne, UPMC, CNRS), Mehran Mehr (Technische Universiteit Eindhoven), Eva Rotenberg (Technical University of Denmark), Alan Roytman (University of Copenhagen), Mikkel Thorup (University of Copenhagen)

Consensus Halving is PPA-Complete
Aris Filos-Ratsikas (University of Oxford), Paul W. Goldberg (University of Oxford)

Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy (Microsoft Research India), Shi Li (University of Buffalo), Sai Sandeep (Microsoft Research India)

Interactive Coding Over the Noisy Broadcast Channel
Klim Efremenko (Tel-Aviv University), Gillat Kol (Princeton University), Raghuvansh Saxena (Princeton University)

Efficient decoding of random errors for quantum expander codes
Omar Fawzi (Ens Lyon), Antoine Grospellier (Inria Paris), Anthony Leverrier (Inria Paris)

Fine-Grained Complexity for Sparse Graphs
Udit Agarwal (University of Texas at Austin), Vijaya Ramachandran (University of Texas at Austin)

A Matrix Expander Chernoff Bound
Ankit Garg (Microsoft Research New England), Yin Tat Lee (University Washington), Zhao Song (Harvard University & UT-Austin), Nikhil Srivastava (UC Berkeley)

Sum-of-squares meets Nash:lower bounds for finding any equilibrium
Pravesh Kothari (Princeton University/IAS), Ruta Mehta (University of Illinois at Urbana-Champaign)

A (5/3+ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
Fabrizio Grandoni (IDSIA), Tobias Mömke (University of Bremen and Saarland University), Andreas Wiese (Universidad de Chile), Hang Zhou (École Polytechnique)

On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S. (Weizmann Institute of Science), Bundit Laekhanukit (Shanghai University of Finance and Economics), Pasin Manurangsi (University of California, Berkeley)

Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni (IDSIA), Christos Kalaitzis (ETH Zurich), Rico Zenklusen (ETH Zurich)

An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism
Daniel Neuen (RWTH Aachen University), Pascal Schweitzer (RWTH Aachen University)

Extensor-coding
Cornelius Brand (Saarland University and Cluster of Excellence (MMCI)), Holger Dell (Saarland University and Cluster of Excellence (MMCI)), Thore Husfeldt (Lund University and Basic Algorithms Research Copenhagen, ITU Copenhagen)

Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson (University of Illinois at Urbana-Champaign), Kyle Fox (The University of Texas at Dallas), Luvsandondov Lkhamsuren (Airbnb)

Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari (ETH Zurich, Switzerland), Fabian Kuhn (University of Freiburg), Yannic Maus (University of Freiburg), Jara Uitto (ETH Zurich & University of Freiburg)

Capacity Approaching Codes for Low Noise Interactive Quantum Communication
Debbie Leung (University of Waterloo), Ashwin Nayak (University of Waterloo), Ala Shayeghi (University of Waterloo), Dave Touchette (University of Waterloo, Perimeter Institute), Penghui Yao (University of Maryland), Nengkun Yu (University of Technology Sydney)

Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Cody Murray (MIT), Ryan Williams (MIT)

On the complexity of hazard-free circuits
Christian Ikenmeyer (Max Planck Institute for Informatics), Balagopal Komarath (Saarland University), Christoph Lenzen (Max Planck Institute for Informatics), Vladimir Lysikov (Saarland University), Andrey Mokhov (Newcastle University), Karteek Sreenivasaiah (Indian Institute of Technology Hyderabad)

Lifting Nullstellensatz to Monotone Span Programs over Any Field
Toniann Pitassi (University of Toronto and IAS), Robert Robere (University of Toronto)

Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein (Harvard University)

Stochastic bandits robust to adversarial corruptions
Thodoris Lykouris (Cornell University), Vahab Mirrokni (Google Research), Renato Paes Leme (Google Research)

Fine-grained reductions from approximate counting to decision
Holger Dell (Saarland University and Cluster of Excellence (MMCI)), John Lapinskas (University of Oxford)

Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi (University of Pennsylvania), Krzysztof Onak (IBM Research), Baruch Schieber (IBM Research), Shay Solomon (IBM Research)

Succinct Delegation for Low-Space Non-Deterministic Computation
Saikrishna Badrinarayanan (UCLA), Yael Tauman Kalai (Microsoft Research, MIT), Dakshita Khurana (UCLA), Amit Sahai (UCLA), Daniel Wichs (Northeastern University)

Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman (Georgetown University)

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Gil Cohen (Princeton University), Bernhard Haeupler (Carnegie Mellon University), Leonard Schulman (California Institute of Technology)

Constant-Factor Approximation for Ordered k-Median
Jaroslaw Byrka (University of Wroclaw), Krzysztof Sornat (University of Wroclaw), Joachim Spoerhase (University of Wroclaw)

Operator Scaling with Specified Marginals
Cole Franks (Rutgers University)

Counting hypergraph colourings in the local lemma regime
Heng Guo (University of Edinburgh), Chao Liao (Shanghai Jiao Tong University), Pinyan Lu (Shanghai University of Finance and Economics), Chihao Zhang (The Chinese University of Hong Kong)

Breaking the Circuit-Size Barrier in Secret Sharing
Tianren Liu (MIT), Vinod Vaikuntanathan (MIT)

More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud (IBM Almaden Research Center), Karl Bringmann (Max Planck Institute for Informatics), Holger Dell (Saarland University and Cluster of Excellence (MMCI)), Jesper Nederlof (Eindhoven University of Technology)

Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler (Carnegie Mellon University), Amirbehshad Shahrasbi (Carnegie Mellon University)

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu (Microsoft Research Redmond), Ankit Garg (Microsoft Research New England), Yuanzhi Li (Princeton University), Rafael Oliveira (University of Toronto), Avi Wigderson (Institute for Advanced Study)

A Tighter Welfare Guarantee for First-Price Auctions
Darrell Hoy (Tremor Technologies), Samuel Taggart (Oberlin College), Zihe Wang (Shanghai University of Finance and Economics)

Composable and Versatile Privacy via Truncated CDP
Mark Bun (Princeton University), Cynthia Dwork (Harvard University), Guy Rothblum (Weizmann Institute), Thomas Steinke (IBM Research - Almaden)

Improved Distributed Algorithms for Exact Shortest Paths
Mohsen Ghaffari (ETH Zurich), Jason Li (Carnegie Mellon University)

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs (MIT), Liam Roditty (Bar Ilan University), Gilad Segal (Bar Ilan University), Virginia Vassilevska Williams (MIT), Nicole Wein (MIT)

The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds
Krzysztof Onak (IBM Research), Xiaorui Sun (Microsoft Research)

Prediction with a Short Memory
Sham Kakade (University of Washington), Percy Liang (Stanford University), Vatsal Sharan (Stanford University), Gregory Valiant (Stanford University)

Interactive Compression to External Information
Mark Braverman (Princeton University), Gillat Kol (Princeton University)

Algorithmic Polynomials
Alexander A. Sherstov (UCLA)

Incomplete Nested Dissection
Rasmus Kyng (Simons Institute), Richard Peng (Georgia Tech), Robert Schwieterman (Georgia Tech), Peng Zhang (Georgia Tech)

Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg (Princeton University), Ran Raz (Princeton University), Avishay Tal (Stanford University)

An Optimal Distributed (Δ+1)-Coloring Algorithm?
Yi-Jun Chang (University of Michigan), Wenzheng Li (Tsinghua University), Seth Pettie (University of Michigan)

Online Load balancing on Related Machines
Sungjin Im (UC Merced), Nathaniel Kell (Duke University), Debmalya Panigrahi (Duke University), Maryam Shadloo (UC Merced)

A Converse to Banach's Fixed Point Theorem and its CLS Completeness
Costis Daskalakis (MIT), Christos Tzamos (Microsoft Research), Manolis Zampetakis (MIT)

Robust Moment Estimation and Improved Clustering via Sum of Squares
Pravesh Kothari (Institute for Advanced Study, Princeton), Jacob Steinhardt (Stanford University), David Steurer (ETH Zurich)