STOC 2018 – Proceedings

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2018), June 25–29, 2018, Los Angeles, CA, USA

Frontmatter

Invited Talks (Partial List)

STOC Talks

Session 1A

k-Server via Multiscale Entropic Regularization
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Mądry
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA)

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

Online Load Balancing on Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo
(University of California at Merced, USA; Duke University, USA)

Session 1B

A Converse to Banach's Fixed Point Theorem and Its CLS-Completeness
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)

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

The Art Gallery Problem Is ∃ ℝ-Complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow
(University of Copenhagen, Denmark; Université Libre de Bruxelles, Belgium)

Session 1C

Composable and Versatile Privacy via Truncated CDP
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke
(Princeton University, USA; Harvard University, USA; Weizmann Institute of Science, Israel; IBM Research, USA)

Universal Protocols for Information Dissemination using Emergent Signals
Bartłomiej Dudek and Adrian Kosowski
(University of Wrocław, Poland; Inria, France)

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

Session 2A

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

Session 2B

An Exponential Lower Bound for Individualization-Refinement Algorithms for Graph Isomorphism
Daniel Neuen and Pascal Schweitzer
(RWTH Aachen University, Germany; TU Kaiserslautern, Germany)

Extensor-Coding
Cornelius Brand, Holger Dell, and Thore Husfeldt
(Saarland University, Germany; M2CI, Germany; Lund University, Sweden; IT University of Copenhagen, Denmark)

Session 2C

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

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

STOC Award Papers

Session 3A

(Gap/S)ETH Hardness of SVP
Divesh Aggarwal and Noah Stephens-Davidowitz
(National University of Singapore, Singapore; Princeton University, USA)

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

More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof
(IBM Research, USA; Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Eindhoven University of Technology, Netherlands)

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein
(Massachusetts Institute of Technology, USA; Bar-Ilan University, Israel)

Fine-Grained Reductions from Approximate Counting to Decision
Holger Dell and John Lapinskas
(Saarland University, Germany; M2CI, Germany; University of Oxford, UK)

Session 3B

Universal Points in the Asymptotic Spectrum of Tensors
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
(University of Copenhagen, Denmark; Budapest University of Technology and Economics, Hungary; CWI, Netherlands)

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

Algorithmic Polynomials
Alexander A. Sherstov
(University of California at Los Angeles, USA)

Shadow Tomography of Quantum States
Scott Aaronson
(University of Texas at Austin, USA)

Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, and Nengkun Yu
(University of Waterloo, Canada; Perimeter Institute Waterloo, Canada; Nanjing University, China; University of Technology Sydney, Australia)

Session 3C

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

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

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

Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang
(Simons Institute for the Theory of Computing Berkeley, USA; Georgia Tech, USA)

Session 4A

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

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

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

Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(University of Warwick, UK; Google Research, USA; Massachusetts Institute of Technology, USA; EPFL, Switzerland; IBM Research, USA; University of Warsaw, Poland)

Session 4B

General Strong Polarization
Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan
(Harvard University, USA; Carnegie Mellon University, USA; SUNY Buffalo, USA)

Capacity Upper Bounds for Deletion-Type Channels
Mahdi Cheraghchi
(Imperial College London, UK)

Interactive Coding over the Noisy Broadcast Channel
Klim Efremenko, Gillat Kol, and Raghuvansh Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)

Efficient Decoding of Random Errors for Quantum Expander Codes
Omar Fawzi, Antoine Grospellier, and Anthony Leverrier
(ENS Lyon, France; Inria, France)

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

Session 4C

Near-Optimal Linear Decision Trees for k-SUM and Related Problems
Daniel M. Kane, Shachar Lovett, and Shay Moran
(University of California at San Diego, USA; Institute for Advanced Study at Princeton, USA)

Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup
(University of Copenhagen, Denmark; Max Planck Institute for Informatics, Germany; Sorbonne University, France; UPMC, France; CNRS, France; LIP6, France; Eindhoven University of Technology, Netherlands; DTU, Denmark)

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

The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of California at San Diego, USA)

Session 5A

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

Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase
(University of Wrocław, Poland)

Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen
(University of Lugano, Switzerland; ETH Zurich, Switzerland)

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

Session 5B

Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal, Venkata Koppula, and Brent Waters
(University of Texas at Austin, USA)

Multi-collision Resistance: A Paradigm for Keyless Hash Functions
Nir Bitansky, Yael Tauman Kalai, and Omer Paneth
(Tel Aviv University, Israel; Microsoft, USA; Massachusetts Institute of Technology, USA)

Non-malleable Secret Sharing
Vipul Goyal and Ashutosh Kumar
(Carnegie Mellon University, USA; University of California at Los Angeles, USA)

Succinct Delegation for Low-Space Non-deterministic Computation
Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
(University of California at Los Angeles, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA)

Session 5C

On Approximating the Number of k-Cliques in Sublinear Time
Talya Eden, Dana Ron, and C. Seshadhri
(Tel Aviv University, Israel; University of California at Santa Cruz, USA)

Testing Conditional Independence of Discrete Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(Stanford University, USA; University of Southern California, USA; University of California at San Diego, USA)

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

A Generalized Turán Problem and Its Applications
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)

Session 6A

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

Smooth Heaps and a Dual View of Self-Adjusting Data Structures
László Kozma and Thatchaphol Saranurak
(Eindhoven University of Technology, Netherlands; KTH, Sweden)

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

At the Roots of Dictionary Compression: String Attractors
Dominik Kempa and Nicola Prezza
(University of Helsinki, Finland; DTU, Denmark; University of Pisa, Italy)

Session 6B

Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov
(Universitat Politècnica de Catalunya, Spain; KTH, Sweden; Sapienza University of Rome, Italy; University of Chicago, USA; Russian Academy of Sciences, Russia)

On the Complexity of Hazard-Free Circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah
(Max Planck Institute for Informatics, Germany; Saarland University, Germany; M2CI, Germany; Newcastle University, UK; IIT Hyderabad, India)

Monotone Circuit Lower Bounds from Resolution
Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
(Microsoft Research, USA; Harvard University, USA; Massachusetts Institute of Technology, USA; KTH, Sweden)

Session 6C

Sparse Kneser Graphs Are Hamiltonian
Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak
(TU Berlin, Germany; ETH Zurich, Switzerland; Jagiellonian University, Poland)

Counting Hypergraph Colourings in the Local Lemma Regime
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang
(University of Edinburgh, UK; Shanghai Jiao Tong University, China; Shanghai University of Finance and Economics, China; Chinese University of Hong Kong, China)

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

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

Session 7A

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

Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, and Huacheng Yu
(Massachusetts Institute of Technology, USA; Stanford University, USA; Harvard University, USA)

Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay
(TIFR, India; Charles University in Prague, Czechia; INESC TEC, Portugal; University of Porto, Portugal; KTH, Sweden)

Session 7B

Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins and Jerry Li
(Cornell University, USA; Massachusetts Institute of Technology, USA)

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

Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)

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

Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Columbia University, USA; Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)

Session 7C

A Matrix Expander Chernoff Bound
Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava
(Microsoft Research, USA; University of Washington, USA; Harvard University, USA; University of Texas at Austin, USA; University of California at Berkeley, USA)

An Homotopy Method for l_p Regression Provably beyond Self-Concordance and in Input-Sparsity Time
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of Washington, USA; Princeton University, USA)

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

Session 8A

Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring
Pranjal Dutta, Nitin Saxena, and Amit Sinhababu
(Chennai Mathematical Institute, India; IIT Kanpur, India)

Bootstrapping Variables in Algebraic Circuits
Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena
(IIT Kanpur, India)

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

Generalized Matrix Completion and Algebraic Natural Proofs
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov
(Saarland University, Germany; Max Planck Institute for Informatics, Germany)

Lifting Nullstellensatz to Monotone Span Programs over Any Field
Toniann Pitassi and Robert Robere
(University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)

Session 8B

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

Inapproximability of the Independent Set Polynomial in the Complex Plane
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič
(Rochester Institute of Technology, USA; University of Oxford, UK; University of Rochester, USA)

Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium
Pravesh K. Kothari and Ruta Mehta
(Princeton University, USA; Institute for Advanced Study at Princeton, USA; University of Illinois at Urbana-Champaign, USA)

Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht
(University of California at Berkeley, USA)

Session 8C

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

On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi
(Weizmann Institute of Science, Israel; Max Planck Institute for Informatics, Germany; Shanghai University of Finance and Economics, China; University of California at Berkeley, USA)

Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen
(Charles University in Prague, Czechia; Aarhus University, Denmark)

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

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