STOC 2019
51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2019)
Powered by
Conference Publishing Consulting
51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2019), June 23–26, 2019, Phoenix, AZ, USA

STOC 2019 – Proceedings

 Contents - Abstracts - Authors

Frontmatter

Title Page


Welcome from the Program Chair


STOC 2019 Conference Organization


Sponsors


Award Papers and More

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant
(Stanford University, USA; University of Washington, USA; North Carolina State University, USA)


 Publisher's Version
Oracle Separation of BQP and PH
Ran Raz and Avishay Tal
(Princeton University, USA; Stanford University, USA)


 Publisher's Version
The Reachability Problem for Petri Nets Is Not Elementary
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki
(University of Warsaw, Poland; University of Warwick, UK; CNRS, France; University of Bordeaux, France)


 Publisher's Version
Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds
Lijie Chen and Roei Tell
(Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel)


 Publisher's Version
The Log-Approximate-Rank Conjecture Is False
Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif
(TIFR, India; Georgetown University, USA)


 Publisher's Version
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg and László A. Végh
(University of Illinois at Urbana-Champaign, USA; London School of Economics and Political Science, UK)


 Publisher's Version

Discrete Optimization

An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
(Harvard University, USA; Stanford University, USA)


 Publisher's Version
Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond
Chandra Chekuri and Kent Quanrud
(University of Illinois at Urbana-Champaign, USA)


 Publisher's Version
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyễn, and Adrian Vladu
(Boston University, USA; Northeastern University, USA)


 Publisher's Version
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, and Amin Karbasi
(Yale University, USA; Open University of Israel, Israel)


 Publisher's Version
Dynamic Set Cover: Improved Algorithms and Lower Bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha
(IBM Research, USA; University of Massachusetts at Amherst, USA; IDSIA, Switzerland; Duke University, USA)


 Publisher's Version
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Deeparnab Chakrabarty and Chaitanya Swamy
(Dartmouth College, USA; University of Waterloo, Canada)


 Publisher's Version

Planar Graphs Algorithms

Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann
(King's College London, UK; University of Wrocław, Poland; IDC Herzliya, Israel; University of Haifa, Israel)


 Publisher's Version
Planar Diameter via Metric Compression
Jason Li and Merav Parter
(Carnegie Mellon University, USA; Weizmann Institute of Science, Israel)


 Publisher's Version
Polylogarithmic Approximation for Euler Genus on Bounded Degree Graphs
Ken-ichi Kawarabayashi and Anastasios Sidiropoulos
(National Institute of Informatics, Japan; University of Illinois at Chicago, USA)


 Publisher's Version
Planar Graphs of Bounded Degree Have Bounded Queue Number
Michael Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
(University of Tübingen, Germany; University of Cologne, Germany; KIT, Germany; University of Perugia, Italy; National Technical University of Athens, Greece)


 Publisher's Version

Quantum Computing I

The Parallel Repetition of Non-signaling Games: Counterexamples and Dichotomy
Justin Holmgren and Lisa Yang
(Princeton University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe
(CWI, Netherlands; University of Amsterdam, Netherlands; University of Maryland, USA; Microsoft Research, USA)


 Publisher's Version
Quantum Weak Coin Flipping
Atul Singh Arora, Jérémie Roland, and Stephan Weis
(Université libre de Bruxelles, Belgium)


 Publisher's Version
A Quantum-Inspired Classical Algorithm for Recommendation Systems
Ewin Tang
(University of Texas at Austin, USA)


 Publisher's Version

Graph Algorithms I

The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)


 Publisher's Version
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(KTH, Sweden; Toyota Technological Institute at Chicago, USA; Michigan State University, USA; Aalto University, Finland)


 Publisher's Version
O(log² k / log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li
(IDSIA, Switzerland; Shanghai University of Finance and Economics, China; SUNY Buffalo, USA)


 Publisher's Version

Streaming

Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Sepehr Assadi, Yu Chen, and Sanjeev Khanna
(Princeton University, USA; University of Pennsylvania, USA)


 Publisher's Version
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov and Dmitry Krachun
(EPFL, Switzerland; University of Geneva, Switzerland)


 Publisher's Version
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos and Zhao Song
(Harvard University, USA; University of Texas at Austin, USA)


 Publisher's Version

Privacy

Private Selection from Private Candidates
Jingcheng Liu and Kunal Talwar
(University of California at Berkeley, USA; Google Brain, USA)


 Publisher's Version
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman
(Stanford University, USA; Simons Institute for the Theory of Computing Berkeley, USA; Boston University, USA; Northeastern University, USA)


 Publisher's Version
Gentle Measurement of Quantum States and Differential Privacy
Scott Aaronson and Guy N. Rothblum
(University of Texas at Austin, USA; Weizmann Institute of Science, Israel)


 Publisher's Version

Graph Algorithms II Distributed/Dynamic

Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein and Danupon Nanongkai
(Rutgers University, USA; KTH, Sweden)


 Publisher's Version
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak
(KTH, Sweden; University of Vienna, Austria; Toyota Technological Institute at Chicago, USA)


 Publisher's Version
Towards the Locality of Vizing’s Theorem
Hsin-Hao Su and Hoa T. Vu
(Boston College, USA)


 Publisher's Version
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen
(Rutgers University, USA; University of Copenhagen, Denmark)


 Publisher's Version
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster and Gramoz Goranci
(University of Salzburg, Austria; University of Vienna, Austria)


 Publisher's Version
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
Julia Chuzhoy and Sanjeev Khanna
(Toyota Technological Institute at Chicago, USA; University of Pennsylvania, USA)


 Publisher's Version

Complexity Theory I Circuits

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0
Alexander A. Sherstov and Pei Wu
(University of California at Los Angeles, USA)


 Publisher's Version
Reconstruction of Non-degenerate Homogeneous Depth Three Circuits
Neeraj Kayal and Chandan Saha
(Microsoft Research, India; Indian Institute of Science, India)


 Publisher's Version
Separating Monotone VP and VNP
Amir Yehudayoff
(Technion, Israel)


 Publisher's Version
On the Approximation Resistance of Balanced Linear Threshold Functions
Aaron Potechin
(University of Chicago, USA)


 Publisher's Version
A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh
(IIT Bombay, India; IIT Hyderabad, India)


 Publisher's Version
DNF Sparsification beyond Sunflowers
Shachar Lovett and Jiapeng Zhang
(University of California at San Diego, USA)


 Publisher's Version

Quantum Computation II

Quantum Lovász Local Lemma: Shearer’s Bound Is Tight
Kun He, Qian Li, Xiaoming Sun, and Jiapeng Zhang
(Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China; Shenzhen Institute of Computing Sciences, China; Shenzhen University, China; University of California at San Diego, USA)


 Publisher's Version
Quantum Proof Systems for Iterated Exponential Time, and Beyond
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen
(Horizon Quantum Computing, Singapore; University of Technology Sydney, Australia; California Institute of Technology, USA; University of Toronto, Canada)


 Publisher's Version
Good Approximate Quantum LDPC Codes from Spacetime Circuit Hamiltonians
Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen
(California Institute of Technology, USA; University of New Mexico, USA; University of California at Berkeley, USA; University of Toronto, Canada)


 Publisher's Version
Hamiltonian Simulation with Nearly Optimal Dependence on Spectral Norm
Guang Hao Low
(Microsoft Research, USA)


 Publisher's Version
Quantum State Certification
Costin Bădescu, Ryan O'Donnell, and John Wright
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Stanford University, USA)


 Publisher's Version

Property Testing

Testing Graphs in Vertex-Distribution-Free Models
Oded Goldreich
(Weizmann Institute of Science, Israel)


 Publisher's Version
Testing Graphs against an Unknown Distribution
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)


 Publisher's Version
Testing Unateness Nearly Optimally
Xi Chen and Erik Waingarten
(Columbia University, USA)


 Publisher's Version
Random Walks and Forbidden Minors II: A poly(d ε⁻¹)-Query Tester for Minor-Closed Properties of Bounded Degree Graphs
Akash Kumar, C. Seshadhri, and Andrew Stolman
(Purdue University, USA; University of California at Santa Cruz, USA)


 Publisher's Version

Constraint Satisfaction

Bridging between 0/1 and Linear Programming via Random Walks
Joshua Brakensiek and Venkatesan Guruswami
(Stanford University, USA; Carnegie Mellon University, USA)


 Publisher's Version
Faster k-SAT Algorithms using Biased-PPSZ
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick
(University of Copenhagen, Denmark; Tel Aviv University, Israel)


 Publisher's Version
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Joshua Brakensiek, Sivakanth Gopi, and Venkatesan Guruswami
(Stanford University, USA; Microsoft Research, USA; Carnegie Mellon University, USA)


 Publisher's Version
Algebraic Approach to Promise Constraint Satisfaction
Jakub Bulín, Andrei Krokhin, and Jakub Opršal
(Charles University in Prague, Czechia; University of Durham, UK)


 Publisher's Version

Pseudorandomness / Algorithmic Game Theory

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


 Publisher's Version
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, and Avishay Tal
(University of California at Los Angeles, USA; Stanford University, USA)


 Publisher's Version
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas and Paul W. Goldberg
(EPFL, Switzerland; University of Oxford, UK)


 Publisher's Version
The Communication Complexity of Local Search
Yakov Babichenko, Shahar Dobzinski, and Noam Nisan
(Technion, Israel; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)


 Publisher's Version

EC Joint Session

Settling the Sample Complexity of Single-Parameter Revenue Maximization
Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang
(Tsinghua University, China; University of Hong Kong, China)


 Publisher's Version
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao
(Columbia University, USA; Shanghai University of Finance and Economics, China; Hong Kong University of Science and Technology, China; Shanghai Jiao Tong University, China)


 Publisher's Version
Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
Hedyeh Beyhaghi and S. Matthew Weinberg
(Cornell University, USA; Princeton University, USA)


 Publisher's Version

Stringology

Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA; Stanford University, USA)


 Publisher's Version
1+ε Approximation of Tree Edit Distance in Quadratic Time
Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin
(Sharif University of Technology, Iran; Institute for Research in Fundamental Sciences, Iran; University of Maryland, USA)


 Publisher's Version
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh and Qiuyi (Richard) Zhang
(University of California at Berkeley, USA)


 Publisher's Version
Computing Quartet Distance Is Equivalent to Counting 4-Cycles
Bartłomiej Dudek and Paweł Gawrychowski
(University of Wrocław, Poland)


 Publisher's Version
Local Decodability of the Burrows-Wheeler Transform
Sandip Sinha and Omri Weinstein
(Columbia University, USA)


 Publisher's Version
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa and Tomasz Kociumaka
(University of Warwick, UK; University of Warsaw, Poland; Bar-Ilan University, Israel)


 Publisher's Version

Algorithmic Statistics

Approximation Algorithms for Distributionally-Robust Stochastic Optimization with Black-Box Distributions
André Linhares and Chaitanya Swamy
(University of Waterloo, Canada)


 Publisher's Version
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, and Aaron Sidford
(Stanford University, USA)


 Publisher's Version
Communication Complexity of Estimating Correlations
Uri Hadar, Jingbo Liu, Yury Polyanskiy, and Ofer Shayevitz
(Tel Aviv University, Israel; Massachusetts Institute of Technology, USA)


 Publisher's Version
Degree-𝑑 Chow Parameters Robustly Determine Degree-𝑑 PTFs (and Algorithmic Applications)
Ilias Diakonikolas and Daniel M. Kane
(University of Southern California, USA; University of California at San Diego, USA)


 Publisher's Version
Capacity Lower Bound for the Ising Perceptron
Jian Ding and Nike Sun
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler, Frederic Koehler, and Ankur Moitra
(Massachusetts Institute of Technology, USA)


 Publisher's Version

COLT Sister Session ML Foundations

Non-Gaussian Component Analysis using Entropy Methods
Navin Goyal and Abhishek Shetty
(Microsoft Research, India)


 Publisher's Version
Private PAC Learning Implies Finite Littlestone Dimension
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; University of Chicago, USA)


 Publisher's Version
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke
(Microsoft Research, USA; University of Washington, USA; Stanford University, USA)


 Publisher's Version
Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen and Ankur Moitra
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Regression from Dependent Observations
Constantinos Daskalakis, Nishanth Dikkala, and Ioannis Panageas
(Massachusetts Institute of Technology, USA; Singapore University of Technology and Design, Singapore)


 Publisher's Version
Memory-Sample Tradeoffs for Linear Regression with Small Error
Vatsal Sharan, Aaron Sidford, and Gregory Valiant
(Stanford University, USA)


 Publisher's Version

Matrix Methods

Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang
(Harvard University, USA; Georgia Tech, USA; Microsoft Research, USA; University of Toronto, Canada)


 Publisher's Version
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng
(Georgia Tech, USA; University of Vienna, Austria)


 Publisher's Version
Spectral Methods from Tensor Networks
Ankur Moitra and Alexander S. Wein
(Massachusetts Institute of Technology, USA; New York University, USA)


 Publisher's Version
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, and Zhao Song
(Massachusetts Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA; University of Texas at Austin, USA)


 Publisher's Version
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, and Karol Węgrzycki
(Max Planck Institute for Informatics, Germany; University of Warsaw, Poland)


 Publisher's Version
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Huacheng Yu
(Harvard University, USA)


 Publisher's Version

Lower Bounds/Metric Algs

Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir, Alexander Golovnev, and Omri Weinstein
(Princeton University, USA; Harvard University, USA; Columbia University, USA)


 Publisher's Version
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
Omar Alrabiah and Venkatesan Guruswami
(Carnegie Mellon University, USA)


 Publisher's Version
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu
(IST Austria, Austria; Yale University, USA; University of Toronto, Canada)


 Publisher's Version
Lower Bounds for External Memory Integer Sorting via Network Coding
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi
(University of Maryland, USA; Aarhus University, Denmark; Cornell University, USA)


 Publisher's Version
Algorithmic Pirogov-Sinai Theory
Tyler Helmuth, Will Perkins, and Guus Regts
(University of Bristol, UK; University of Illinois at Chicago, USA; University of Amsterdam, Netherlands)


 Publisher's Version
On Approximating the Covering Radius and Finding Dense Lattice Subspaces
Daniel Dadush
(CWI, Netherlands)


 Publisher's Version

ML Foundations II

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
(Northwestern University, USA; Toyota Technological Institute at Chicago, USA; Microsoft Research, USA)


 Publisher's Version
Oblivious Dimension Reduction for k-Means: Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn
(Sapienza University of Rome, Italy; Zalando, Switzerland; CNRS, France; IDSIA, Switzerland)


 Publisher's Version
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh
(Tel Aviv University, Israel; EPFL, Switzerland; Microsoft Research, USA; Princeton University, USA; Google Research, USA)


 Publisher's Version
Optimal Terminal Dimensionality Reduction in Euclidean Space
Shyam Narayanan and Jelani Nelson
(Harvard University, USA)


 Publisher's Version
Dynamic Sampling from Graphical Models
Weiming Feng, Nisheeth K. Vishnoi, and Yitong Yin
(Nanjing University, China; Yale University, USA)


 Publisher's Version

Cryptography

Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs
(Boston University, USA; Tel Aviv University, Israel; Visa Research, USA; Princeton University, USA; Massachusetts Institute of Technology, USA; Weizmann Institute of Science, Israel; Technion, Israel; Northeastern University, USA)


 Publisher's Version
Weak Zero-Knowledge Beyond the Black-Box Barrier
Nir Bitansky, Dakshita Khurana, and Omer Paneth
(Tel Aviv University, Israel; Microsoft Research, USA; University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
(Johns Hopkins University, USA; Charles University in Prague, Czechia; IST Austria, Austria; IDC Herzliya, Israel; Weizmann Institute of Science, Israel)


 Publisher's Version
How to Delegate Computations Publicly
Yael Tauman Kalai, Omer Paneth, and Lisa Yang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version

Algorithms

On a Generalization of Iterated and Randomized Rounding
Nikhil Bansal
(CWI, Netherlands; Eindhoven University of Technology, Netherlands)


 Publisher's Version
The Online 𝑘-Taxi Problem
Christian Coester and Elias Koutsoupias
(University of Oxford, UK)


 Publisher's Version
Achieving Optimal Backlog in Multi-processor Cup Games
Michael A. Bender, Martín Farach-Colton, and William Kuszmaul
(Stony Brook University, USA; Rutgers University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Planar Point Sets Determine Many Pairwise Crossing Segments
János Pach, Natan Rubin, and Gábor Tardos
(EPFL, Switzerland; Renyi Institute, Hungary; Ben-Gurion University of the Negev, Israel; Central European University, Hungary)


 Publisher's Version

Graph Algorithms III

Graph Pattern Detection: Hardness for All Induced Patterns and Faster Non-induced Cycles
Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams
(Massachusetts Institute of Technology, USA)


 Publisher's Version
New Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity Search
Alessio Conte and Takeaki Uno
(National Institute of Informatics, Japan; University of Pisa, Italy)


 Publisher's Version
Explicit 𝑁-Vertex Graphs with Maximum Degree 𝐾 and Diameter [1+𝑜(1)]log𝐾-1 𝑁 for Each 𝐾-1 a Prime Power
Michael Capalbo
(Center for Computing Sciences, USA)


 Publisher's Version

Complexity Theory II

Sylvester-Gallai Type Theorems for Quadratic Polynomials
Amir Shpilka
(Tel Aviv University, Israel)


 Publisher's Version
Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes
Dylan M. McKay, Cody D. Murray, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)


 Publisher's Version
Mean-Field Approximation, Convex Hierarchies, and the Optimality of Correlation Rounding: A Unified Perspective
Vishesh Jain, Frederic Koehler, and Andrej Risteski
(Massachusetts Institute of Technology, USA)


 Publisher's Version

Graph Canonization

Canonical Form for Graphs in Quasipolynomial Time: Preliminary Report
László Babai
(University of Chicago, USA)


 Publisher's Version
A Unifying Method for the Design of Algorithms Canonizing Combinatorial Objects
Pascal Schweitzer and Daniel Wiebking
(TU Kaiserslautern, Germany; RWTH Aachen University, Germany)


 Publisher's Version

proc time: 0.78