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 Article Search
Oracle Separation of BQP and PH
Ran Raz and Avishay Tal
(Princeton University, USA; Stanford University, USA)
Publisher's Version Article Search Info
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 Article Search
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 Article Search
The Log-Approximate-Rank Conjecture Is False
Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif
(TIFR, India; Georgetown University, USA)
Publisher's Version Article Search
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 Article Search

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 Article Search
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 Article Search
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 Article Search
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 Article Search
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 Article Search
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Deeparnab Chakrabarty and Chaitanya Swamy
(Dartmouth College, USA; University of Waterloo, Canada)
Publisher's Version Article Search

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 Article Search
Planar Diameter via Metric Compression
Jason Li and Merav Parter
(Carnegie Mellon University, USA; Weizmann Institute of Science, Israel)
Publisher's Version Article Search
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 Article Search
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 Article Search

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 Article Search
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 Article Search
Quantum Weak Coin Flipping
Atul Singh Arora, Jérémie Roland, and Stephan Weis
(Université libre de Bruxelles, Belgium)
Publisher's Version Article Search Info
A Quantum-Inspired Classical Algorithm for Recommendation Systems
Ewin Tang
(University of Texas at Austin, USA)
Publisher's Version Article Search

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 Article Search
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 Article Search
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 Article Search

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 Article Search
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov and Dmitry Krachun
(EPFL, Switzerland; University of Geneva, Switzerland)
Publisher's Version Article Search
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos and Zhao Song
(Harvard University, USA; University of Texas at Austin, USA)
Publisher's Version Article Search

Privacy

Private Selection from Private Candidates
Jingcheng Liu and Kunal Talwar
(University of California at Berkeley, USA; Google Brain, USA)
Publisher's Version Article Search
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 Article Search
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 Article Search Info

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 Article Search Info
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 Article Search
Towards the Locality of Vizing’s Theorem
Hsin-Hao Su and Hoa T. Vu
(Boston College, USA)
Publisher's Version Article Search
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 Article Search
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 Article Search
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 Article Search

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 Article Search
Reconstruction of Non-degenerate Homogeneous Depth Three Circuits
Neeraj Kayal and Chandan Saha
(Microsoft Research, India; Indian Institute of Science, India)
Publisher's Version Article Search
Separating Monotone VP and VNP
Amir Yehudayoff
(Technion, Israel)
Publisher's Version Article Search
On the Approximation Resistance of Balanced Linear Threshold Functions
Aaron Potechin
(University of Chicago, USA)
Publisher's Version Article Search
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 Article Search
DNF Sparsification beyond Sunflowers
Shachar Lovett and Jiapeng Zhang
(University of California at San Diego, USA)
Publisher's Version Article Search

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 Article Search
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 Article Search Info
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 Article Search
Hamiltonian Simulation with Nearly Optimal Dependence on Spectral Norm
Guang Hao Low
(Microsoft Research, USA)
Publisher's Version Article Search
Quantum State Certification
Costin Bădescu, Ryan O'Donnell, and John Wright
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Article Search
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 Article Search

Property Testing

Testing Graphs in Vertex-Distribution-Free Models
Oded Goldreich
(Weizmann Institute of Science, Israel)
Publisher's Version Article Search
Testing Graphs against an Unknown Distribution
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)
Publisher's Version Article Search
Testing Unateness Nearly Optimally
Xi Chen and Erik Waingarten
(Columbia University, USA)
Publisher's Version Article Search
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 Article Search

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 Article Search
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 Article Search
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 Article Search
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 Article Search

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 Article Search
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 Article Search Info
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 Article Search
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 Article Search

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 Article Search Info
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 Article Search
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 Article Search

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 Article Search
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 Article Search
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 Article Search
Computing Quartet Distance Is Equivalent to Counting 4-Cycles
Bartłomiej Dudek and Paweł Gawrychowski
(University of Wrocław, Poland)
Publisher's Version Article Search
Local Decodability of the Burrows-Wheeler Transform
Sandip Sinha and Omri Weinstein
(Columbia University, USA)
Publisher's Version Article Search
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 Article Search

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 Article Search
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, and Aaron Sidford
(Stanford University, USA)
Publisher's Version Article Search
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 Article Search
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 Article Search
Capacity Lower Bound for the Ising Perceptron
Jian Ding and Nike Sun
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Article Search
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler, Frederic Koehler, and Ankur Moitra
(Massachusetts Institute of Technology, USA)
Publisher's Version Article Search

COLT Sister Session ML Foundations

Non-Gaussian Component Analysis using Entropy Methods
Navin Goyal and Abhishek Shetty
(Microsoft Research, India)
Publisher's Version Article Search
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 Article Search
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 Article Search
Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen and Ankur Moitra
(Massachusetts Institute of Technology, USA)
Publisher's Version Article Search
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 Article Search
Memory-Sample Tradeoffs for Linear Regression with Small Error
Vatsal Sharan, Aaron Sidford, and Gregory Valiant
(Stanford University, USA)
Publisher's Version Article Search

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 Article Search
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 Article Search
Spectral Methods from Tensor Networks
Ankur Moitra and Alexander S. Wein
(Massachusetts Institute of Technology, USA; New York University, USA)
Publisher's Version Article Search
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 Article Search
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 Article Search
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Huacheng Yu
(Harvard University, USA)
Publisher's Version Article Search

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 Article Search Info
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
Omar Alrabiah and Venkatesan Guruswami
(Carnegie Mellon University, USA)
Publisher's Version Article Search
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 Article Search
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 Article Search
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 Article Search
On Approximating the Covering Radius and Finding Dense Lattice Subspaces
Daniel Dadush
(CWI, Netherlands)
Publisher's Version Article Search

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 Article Search
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 Article Search
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 Article Search
Optimal Terminal Dimensionality Reduction in Euclidean Space
Shyam Narayanan and Jelani Nelson
(Harvard University, USA)
Publisher's Version Article Search
Dynamic Sampling from Graphical Models
Weiming Feng, Nisheeth K. Vishnoi, and Yitong Yin
(Nanjing University, China; Yale University, USA)
Publisher's Version Article Search

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 Article Search
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 Article Search
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 Article Search
How to Delegate Computations Publicly
Yael Tauman Kalai, Omer Paneth, and Lisa Yang
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Article Search

Algorithms

On a Generalization of Iterated and Randomized Rounding
Nikhil Bansal
(CWI, Netherlands; Eindhoven University of Technology, Netherlands)
Publisher's Version Article Search
The Online 𝑘-Taxi Problem
Christian Coester and Elias Koutsoupias
(University of Oxford, UK)
Publisher's Version Article Search
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 Article Search
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 Article Search

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 Article Search
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 Article Search
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 Article Search

Complexity Theory II

Sylvester-Gallai Type Theorems for Quadratic Polynomials
Amir Shpilka
(Tel Aviv University, Israel)
Publisher's Version Article Search
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 Article Search
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 Article Search

Graph Canonization

Canonical Form for Graphs in Quasipolynomial Time: Preliminary Report
László Babai
(University of Chicago, USA)
Publisher's Version Article Search
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 Article Search

proc time: 1.56