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

STOC 2018 – Proceedings

 Contents - Abstracts - Authors

Frontmatter

Title Page
Article: stoc18foreword-fm000-p doi:
Welcome from the Program Chair
Article: stoc18foreword-fm001-p doi:
STOC 2018 Conference Organization
Article: stoc18foreword-fm002-p doi:
List of Invited Plenary Talks and Tutorials
Article: stoc18foreword-fm004-p doi:
Sponsors
Article: stoc18foreword-fm003-p doi:

Invited Talks (Partial List)

Dynamic Matching in School Choice: Efficient Seat Reassignment after Late Cancellations (Invited Talk)
Irene Lo
(Columbia University, USA)
Publisher's Version Article: stoc18key-idk3-p doi:10.1145/3188745.3232193
Generalization and Equilibrium in Generative Adversarial Nets (GANs) (Invited Talk)
Tengyu Ma
(Stanford University, USA)
Publisher's Version Article: stoc18key-idk8-p doi:10.1145/3188745.3232194

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)
Article: stoc18main-p111-p doi:
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)
Publisher's Version Article: stoc18main-p214-p doi:10.1145/3188745.3188858
Online Load Balancing on Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo
(University of California at Merced, USA; Duke University, USA)
Publisher's Version Article: stoc18main-p439-p doi:10.1145/3188745.3188966

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)
Publisher's Version Article: stoc18main-p443-p doi:10.1145/3188745.3188968
Consensus Halving Is PPA-Complete
Aris Filos-Ratsikas and Paul W. Goldberg
(University of Oxford, UK)
Publisher's Version Article: stoc18main-p257-p doi:10.1145/3188745.3188880
The Art Gallery Problem Is ∃ ℝ-Complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow
(University of Copenhagen, Denmark; Université Libre de Bruxelles, Belgium)
Article: stoc18main-p233-p doi:

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)
Publisher's Version Article: stoc18main-p384-p doi:10.1145/3188745.3188946
Universal Protocols for Information Dissemination using Emergent Signals
Bartłomiej Dudek and Adrian Kosowski
(University of Wrocław, Poland; Inria, France)
Publisher's Version Article: stoc18main-p142-p doi:10.1145/3188745.3188818
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)
Publisher's Version Article: stoc18main-p167-p doi:10.1145/3188745.3188836

Session 2A

Stochastic Bandits Robust to Adversarial Corruptions
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme
(Cornell University, USA; Google Research, USA)
Publisher's Version Article: stoc18main-p304-p doi:10.1145/3188745.3188918
Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality
Yannai A. Gonczarowski
(Hebrew University of Jerusalem, Israel; Microsoft Research, Israel)
Publisher's Version Article: stoc18main-p76-p doi:10.1145/3188745.3188786
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)
Publisher's Version Article: stoc18main-p383-p doi:10.1145/3188745.3188944

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)
Publisher's Version Article: stoc18main-p286-p doi:10.1145/3188745.3188900
Extensor-Coding
Cornelius Brand, Holger Dell, and Thore Husfeldt
(Saarland University, Germany; M2CI, Germany; Lund University, Sweden; IT University of Copenhagen, Denmark)
Publisher's Version Article: stoc18main-p288-p doi:10.1145/3188745.3188902
The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds
Krzysztof Onak and Xiaorui Sun
(IBM Research, USA; Microsoft Research, USA)
Publisher's Version Article: stoc18main-p404-p doi:10.1145/3188745.3188952

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)
Publisher's Version Article: stoc18main-p382-p doi:10.1145/3188745.3188942
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)
Publisher's Version Article: stoc18main-p101-p doi:10.1145/3188745.3188794
Operator Scaling with Specified Marginals
Cole Franks
(Rutgers University, USA)
Publisher's Version Article: stoc18main-p339-p doi:10.1145/3188745.3188932

STOC Award Papers

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, and László A. Végh
(EPFL, Switzerland; London School of Economics, UK)
Publisher's Version Article: stoc18main-p150-p doi:10.1145/3188745.3188824
An Almost-Linear Time Algorithm for Uniform Random Spanning Tree Generation
Aaron Schild
(University of California at Berkeley, USA)
Publisher's Version Article: stoc18main-p201-p doi:10.1145/3188745.3188852

Session 3A

(Gap/S)ETH Hardness of SVP
Divesh Aggarwal and Noah Stephens-Davidowitz
(National University of Singapore, Singapore; Princeton University, USA)
Publisher's Version Article: stoc18main-p183-p doi:10.1145/3188745.3188840
Fine-Grained Complexity for Sparse Graphs
Udit Agarwal and Vijaya Ramachandran
(University of Texas at Austin, USA)
Publisher's Version Article: stoc18main-p268-p doi:10.1145/3188745.3188888
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)
Publisher's Version Article: stoc18main-p376-p doi:10.1145/3188745.3188938
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)
Publisher's Version Article: stoc18main-p403-p doi:10.1145/3188745.3188950
Fine-Grained Reductions from Approximate Counting to Decision
Holger Dell and John Lapinskas
(Saarland University, Germany; M2CI, Germany; University of Oxford, UK)
Publisher's Version Article: stoc18main-p307-p doi:10.1145/3188745.3188920

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)
Publisher's Version Article: stoc18main-p32-p doi:10.1145/3188745.3188766
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)
Publisher's Version Article: stoc18main-p75-p doi:10.1145/3188745.3188784
Algorithmic Polynomials
Alexander A. Sherstov
(University of California at Los Angeles, USA)
Publisher's Version Article: stoc18main-p427-p doi:10.1145/3188745.3188958
Shadow Tomography of Quantum States
Scott Aaronson
(University of Texas at Austin, USA)
Publisher's Version Article: stoc18main-p113-p doi:10.1145/3188745.3188802
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)
Publisher's Version Article: stoc18main-p294-p doi:10.1145/3188745.3188908

Session 3C

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Mark Braverman, Gil Cohen, and Sumegha Garg
(Princeton University, USA)
Publisher's Version Article: stoc18main-p68-p doi:10.1145/3188745.3188780
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)
Publisher's Version Article: stoc18main-p112-p doi:10.1145/3188745.3188800
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)
Publisher's Version Article: stoc18main-p114-p doi:10.1145/3188745.3188804
A Friendly Smoothed Analysis of the Simplex Method
Daniel Dadush and Sophie Huiberts
(CWI, Netherlands)
Publisher's Version Article: stoc18main-p151-p doi:10.1145/3188745.3188826
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang
(Simons Institute for the Theory of Computing Berkeley, USA; Georgia Tech, USA)
Publisher's Version Article: stoc18main-p429-p doi:10.1145/3188745.3188960

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)
Publisher's Version Article: stoc18main-p293-p doi:10.1145/3188745.3188906
Improved Distributed Algorithms for Exact Shortest Paths
Mohsen Ghaffari and Jason Li
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
Publisher's Version Article: stoc18main-p394-p doi:10.1145/3188745.3188948
An Optimal Distributed (Δ+1)-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, and Seth Pettie
(University of Michigan, USA; Tsinghua University, China)
Publisher's Version Article: stoc18main-p436-p doi:10.1145/3188745.3188964
Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman
(Georgetown University, USA)
Publisher's Version Article: stoc18main-p320-p doi:10.1145/3188745.3188926
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)
Article: stoc18main-p15-p doi:

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)
Publisher's Version Article: stoc18main-p140-p doi:10.1145/3188745.3188816
Capacity Upper Bounds for Deletion-Type Channels
Mahdi Cheraghchi
(Imperial College London, UK)
Publisher's Version Article: stoc18main-p42-p doi:10.1145/3188745.3188768
Interactive Coding over the Noisy Broadcast Channel
Klim Efremenko, Gillat Kol, and Raghuvansh Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
Publisher's Version Article: stoc18main-p262-p doi:10.1145/3188745.3188884
Efficient Decoding of Random Errors for Quantum Expander Codes
Omar Fawzi, Antoine Grospellier, and Anthony Leverrier
(ENS Lyon, France; Inria, France)
Publisher's Version Article: stoc18main-p263-p doi:10.1145/3188745.3188886
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)
Publisher's Version Article: stoc18main-p326-p doi:10.1145/3188745.3188928

Session 4C

The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm Is Exponential
Jesús A. De Loera, Jamie Haddock, and Luis Rademacher
(University of California at Davis, USA)
Article: stoc18main-p143-p doi:
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)
Publisher's Version Article: stoc18main-p49-p doi:10.1145/3188745.3188770
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)
Publisher's Version Article: stoc18main-p248-p doi:10.1145/3188745.3188878
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)
Publisher's Version Article: stoc18main-p204-p doi:10.1145/3188745.3188854
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)
Publisher's Version Article: stoc18main-p195-p doi:10.1145/3188745.3188850

Session 5A

Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, Ron Lavi, and Yangguang Shi
(Technion, Israel)
Publisher's Version Article: stoc18main-p121-p doi:10.1145/3188745.3188812
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)
Publisher's Version Article: stoc18main-p278-p doi:10.1145/3188745.3188894
Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase
(University of Wrocław, Poland)
Publisher's Version Article: stoc18main-p338-p doi:10.1145/3188745.3188930
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen
(University of Lugano, Switzerland; ETH Zurich, Switzerland)
Publisher's Version Article: stoc18main-p284-p doi:10.1145/3188745.3188898
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)
Publisher's Version Article: stoc18main-p260-p doi:10.1145/3188745.3188882

Session 5B

Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal, Venkata Koppula, and Brent Waters
(University of Texas at Austin, USA)
Publisher's Version Article: stoc18main-p187-p doi:10.1145/3188745.3188844
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)
Publisher's Version Article: stoc18main-p236-p doi:10.1145/3188745.3188870
Non-malleable Secret Sharing
Vipul Goyal and Ashutosh Kumar
(Carnegie Mellon University, USA; University of California at Los Angeles, USA)
Publisher's Version Article: stoc18main-p238-p doi:10.1145/3188745.3188872
Breaking the Circuit-Size Barrier in Secret Sharing
Tianren Liu and Vinod Vaikuntanathan
(Massachusetts Institute of Technology, USA)
Publisher's Version Article: stoc18main-p368-p doi:10.1145/3188745.3188936
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)
Publisher's Version Article: stoc18main-p312-p doi:10.1145/3188745.3188924

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)
Publisher's Version Article: stoc18main-p120-p doi:10.1145/3188745.3188810
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)
Publisher's Version Article: stoc18main-p11-p doi:10.1145/3188745.3188756
Distribution-Free Junta Testing
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie
(Shanghai Jiao Tong University, China; Columbia University, USA)
Publisher's Version Article: stoc18main-p186-p doi:10.1145/3188745.3188842
A Generalized Turán Problem and Its Applications
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)
Publisher's Version Article: stoc18main-p63-p doi:10.1145/3188745.3188778
Construction of New Local Spectral High Dimensional Expanders
Tali Kaufman and Izhar Oppenheim
(Bar-Ilan University, Israel; Ben-Gurion University of the Negev, Israel)
Publisher's Version Article: stoc18main-p70-p doi:10.1145/3188745.3188782

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)
Publisher's Version Article: stoc18main-p189-p doi:10.1145/3188745.3188846
Smooth Heaps and a Dual View of Self-Adjusting Data Structures
László Kozma and Thatchaphol Saranurak
(Eindhoven University of Technology, Netherlands; KTH, Sweden)
Publisher's Version Article: stoc18main-p225-p doi:10.1145/3188745.3188864
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)
Publisher's Version Article: stoc18main-p309-p doi:10.1145/3188745.3188922
At the Roots of Dictionary Compression: String Attractors
Dominik Kempa and Nicola Prezza
(University of Helsinki, Finland; DTU, Denmark; University of Pisa, Italy)
Publisher's Version Article: stoc18main-p125-p doi:10.1145/3188745.3188814
Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
Publisher's Version Article: stoc18main-p379-p doi:10.1145/3188745.3188940

Session 6B

Quantified Derandomization of Linear Threshold Circuits
Roei Tell
(Weizmann Institute of Science, Israel)
Publisher's Version Article: stoc18main-p147-p doi:10.1145/3188745.3188822
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)
Publisher's Version Article: stoc18main-p211-p doi:10.1145/3188745.3188856
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)
Publisher's Version Article: stoc18main-p297-p doi:10.1145/3188745.3188912
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Cody Murray and Ryan Williams
(Massachusetts Institute of Technology, USA)
Publisher's Version Article: stoc18main-p295-p doi:10.1145/3188745.3188910
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)
Publisher's Version Article: stoc18main-p179-p doi:10.1145/3188745.3188838

Session 6C

Sparse Kneser Graphs Are Hamiltonian
Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak
(TU Berlin, Germany; ETH Zurich, Switzerland; Jagiellonian University, Poland)
Publisher's Version Article: stoc18main-p166-p doi:10.1145/3188745.3188834
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber
(University of Washington, USA)
Publisher's Version Article: stoc18main-p191-p doi:10.1145/3188745.3188848
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)
Publisher's Version Article: stoc18main-p364-p doi:10.1145/3188745.3188934
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)
Publisher's Version Article: stoc18main-p115-p doi:10.1145/3188745.3188806
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)
Publisher's Version Article: stoc18main-p116-p doi:10.1145/3188745.3188808

Session 7A

Interactive Compression to External Information
Mark Braverman and Gillat Kol
(Princeton University, USA)
Publisher's Version Article: stoc18main-p413-p doi:10.1145/3188745.3188956
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, and Huacheng Yu
(Aarhus University, Denmark; Columbia University, USA; Harvard University, USA)
Publisher's Version Article: stoc18main-p97-p doi:10.1145/3188745.3188790
Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, and Avishay Tal
(Princeton University, USA; Stanford University, USA)
Publisher's Version Article: stoc18main-p430-p doi:10.1145/3188745.3188962
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)
Publisher's Version Article: stoc18main-p223-p doi:10.1145/3188745.3188862
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)
Publisher's Version Article: stoc18main-p242-p doi:10.1145/3188745.3188874

Session 7B

Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins and Jerry Li
(Cornell University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Article: stoc18main-p3-p doi:10.1145/3188745.3188748
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)
Publisher's Version Article: stoc18main-p444-p doi:10.1145/3188745.3188970
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
Publisher's Version Article: stoc18main-p12-p doi:10.1145/3188745.3188758
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)
Publisher's Version Article: stoc18main-p10-p doi:10.1145/3188745.3188754
Prediction with a Short Memory
Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant
(Stanford University, USA; University of Washington, USA)
Publisher's Version Article: stoc18main-p410-p doi:10.1145/3188745.3188954
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)
Publisher's Version Article: stoc18main-p152-p doi:10.1145/3188745.3188828

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)
Publisher's Version Article: stoc18main-p275-p doi:10.1145/3188745.3188890
Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Yin Tat Lee and Santosh S. Vempala
(University of Washington, USA; Microsoft Research, USA; Georgia Tech, USA)
Publisher's Version Article: stoc18main-p55-p doi:10.1145/3188745.3188774
Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev
Yin Tat Lee and Santosh S. Vempala
(University of Washington, USA; Microsoft Research, USA; Georgia Tech, USA)
Publisher's Version Article: stoc18main-p230-p doi:10.1145/3188745.3188866
An Homotopy Method for lp 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)
Publisher's Version Article: stoc18main-p62-p doi:10.1145/3188745.3188776
The Adaptive Complexity of Maximizing a Submodular Function
Eric Balkanski and Yaron Singer
(Harvard University, USA)
Publisher's Version Article: stoc18main-p8-p doi:10.1145/3188745.3188752

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)
Publisher's Version Article: stoc18main-p13-p doi:10.1145/3188745.3188760
Bootstrapping Variables in Algebraic Circuits
Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena
(IIT Kanpur, India)
Publisher's Version Article: stoc18main-p14-p doi:10.1145/3188745.3188762
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)
Publisher's Version Article: stoc18main-p98-p doi:10.1145/3188745.3188792
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)
Publisher's Version Article: stoc18main-p165-p doi:10.1145/3188745.3188832
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)
Publisher's Version Article: stoc18main-p301-p doi:10.1145/3188745.3188914

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)
Publisher's Version Article: stoc18main-p53-p doi:10.1145/3188745.3188772
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)
Publisher's Version Article: stoc18main-p77-p doi:10.1145/3188745.3188788
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)
Publisher's Version Article: stoc18main-p277-p doi:10.1145/3188745.3188892
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)
Publisher's Version Article: stoc18main-p106-p doi:10.1145/3188745.3188796
Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
(Harvard University, USA)
Publisher's Version Article: stoc18main-p302-p doi:10.1145/3188745.3188916

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)
Publisher's Version Article: stoc18main-p247-p doi:10.1145/3188745.3188876
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)
Publisher's Version Article: stoc18main-p281-p doi:10.1145/3188745.3188896
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)
Publisher's Version Article: stoc18main-p160-p doi:10.1145/3188745.3188830
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)
Publisher's Version Article: stoc18main-p220-p doi:10.1145/3188745.3188860
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)
Publisher's Version Article: stoc18main-p289-p doi:10.1145/3188745.3188904

proc time: 8.75