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

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

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

Consensus Halving Is PPA-Complete
Aris Filos-Ratsikas and Paul W. Goldberg

(University of Oxford, UK)

Publisher's Version

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

Publisher's Version

Info

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

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

Publisher's Version

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

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

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

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

Info

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

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

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

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

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

Operator Scaling with Specified Marginals
Cole Franks
(Rutgers University, USA)

Publisher's Version

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

An Almost-Linear Time Algorithm for Uniform Random Spanning Tree Generation
Aaron Schild
(University of California at Berkeley, USA)

Publisher's Version

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

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

Publisher's Version

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

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

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

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

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

Algorithmic Polynomials
Alexander A. Sherstov

(University of California at Los Angeles, USA)

Publisher's Version

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

Publisher's Version

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

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

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

Info

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

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

Publisher's Version

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

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

Improved Distributed Algorithms for Exact Shortest Paths
Mohsen Ghaffari

and Jason Li
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)

Publisher's Version

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

(University of Michigan, USA; Tsinghua University, China)

Publisher's Version

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

Publisher's Version

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)

Publisher's Version

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

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

Publisher's Version

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

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

Publisher's Version

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

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)

Publisher's Version

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

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

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

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

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

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

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

Publisher's Version

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

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

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

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

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

Publisher's Version

Breaking the Circuit-Size Barrier in Secret Sharing
Tianren Liu and Vinod Vaikuntanathan

(Massachusetts Institute of Technology, USA)

Publisher's Version

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

Info

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

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

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

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

Publisher's Version

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

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

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

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

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

Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler

and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)

Publisher's Version

Session 6B

Quantified Derandomization of Linear Threshold Circuits
Roei Tell

(Weizmann Institute of Science, Israel)

Publisher's Version

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

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

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

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

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

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

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

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

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

Session 7A

Interactive Compression to External Information
Mark Braverman and Gillat Kol

(Princeton University, USA)

Publisher's Version

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

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

Publisher's Version

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

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

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

Info

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

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

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

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

Publisher's Version

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

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

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

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

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)

Publisher's Version

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

Publisher's Version

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

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

Publisher's Version

Info

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

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

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

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

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

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

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

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

Publisher's Version

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

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

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

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

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

proc time: 22.8