STOC 2025 – Proceedings

Frontmatter

Best Papers

Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
Yeyuan Chen and Zihan Zhang
(University of Michigan at Ann Arbor, USA; Ohio State University, USA)

Publisher's Version

Simulating Time with Square-Root Space
R. Ryan Williams
(Massachusetts Institute of Technology, USA)

Publisher's Version

Vizing’s Theorem in Near-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, and Tianyi Zhang
(University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland)

Publisher's Version Video

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin
(Tsinghua University, China; Stanford University, USA; MPI-INF, Germany)

Publisher's Version

Quasi-Linear Size PCPs with Small Soundness from HDX
Mitali Bafna, Dor Minzer, Nikhil Vyas, and Zhiwei Yun
(Massachusetts Institute of Technology, USA; Harvard University, USA)

Publisher's Version

Session 2A

Asymptotically Optimal Hardness for 𝑘-Set Packing and 𝑘-Matroid Intersection
Euiwoong Lee, Ola Svensson, and Theophile Thiery
(University of Michigan, USA; EPFL, Switzerland)

Publisher's Version

On Approximability of Satisfiable 𝑘-CSPs: V
Amey Bhangale, Subhash Khot, and Dor Minzer
(University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Hardness of 4-Colouring 𝐺-Colourable Graphs
Sergey Avvakumov, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner
(Tel Aviv University, Israel; Masaryk University, Czechia; University of Birmingham, UK; IST Austria, Austria)

Publisher's Version

Sum-of-Squares Lower Bounds for Coloring Random Graphs
Aaron Potechin and Jeff Xu
(University of Chicago, USA; Carnegie Mellon University, USA)

Publisher's Version

Hypercontractivity on HDX II: Symmetrization and 𝑞-Norms
Max Hopkins
(Princeton University, USA)

Publisher's Version

Parallel Repetition for 3-Player 𝘟𝘖𝘙 Games
Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, and Dor Minzer
(University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 2B

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Tuukka Korhonen
(University of Copenhagen, Denmark)

Publisher's Version

Network Unreliability in Almost-Linear Time
Ruoxu Cen, Jason Li, and Debmalya Panigrahi
(Duke University, USA; Carnegie Mellon University, USA)

Publisher's Version

Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak
(New York University, USA; University of Warwick, UK; University of Vienna, Austria; University of Michigan, USA)

Publisher's Version

Breaking the 𝑂(𝑚𝑛)-Time Barrier for Vertex-Weighted Global Minimum Cut
Julia Chuzhoy and Ohad Trabelsi
(Toyota Technological Institute at Chicago, USA)

Publisher's Version

Fully Dynamic Biconnectivity in Õ(log² n) Time
Jacob Holm, Wojciech Nadara, Eva Rotenberg, and Marek Sokołowski
(University of Copenhagen, Denmark; DTU, Denmark; University of Warsaw, Poland; MPI-INF, Germany)

Publisher's Version

Approximating the Held–Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
Zhuan Khye Koh, Omri Weinstein, and Sorrachai Yingchareonthawornchai
(Boston University, USA; Hebrew University of Jerusalem, Israel; ETH Zurich, Switzerland)

Publisher's Version

Session 2C

Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P Hardness
Dakshita Khurana and Kabir Tomer
(University of Illinois at Urbana-Champaign, USA; NTT Research, USA)

Publisher's Version

Quantum-Computable One-Way Functions without One-Way Functions
William Kretschmer, Luowen Qian, and Avishay Tal
(Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA; University of California at Berkeley, USA)

Publisher's Version

A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
John Bostanci, Barak Nehoran, and Mark Zhandry
(Columbia University, USA; Princeton University, USA; NTT Research, USA)

Publisher's Version

Quantum One-Time Programs, Revisited
Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, and Vinod Vaikuntanathan
(Massachusetts Institute of Technology, USA; Fujitsu Research, USA; Carnegie Mellon University, USA; University of California at Berkeley, USA)

Publisher's Version

A Bound on the Quantum Value of All Compiled Nonlocal Games
Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, and Michael Walter
(Ruhr University Bochum, Germany; Bocconi University, Italy; University of Ottawa, Canada)

Publisher's Version

Classical Commitments to Quantum States
Sam Gunn, Yael Tauman Kalai, Anand Natarajan, and Ági Villányi
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 2D

Linear Hashing Is Optimal
Michael Jaber, Vinayak M. Kumar, and David Zuckerman
(University of Texas at Austin, USA)

Publisher's Version

A Framework for Building Data Structures from Communication Protocols
Alexandr Andoni, Shunhua Jiang, and Omri Weinstein
(Columbia University, USA; Hebrew University of Jerusalem, Israel)

Publisher's Version

Optimal Non-oblivious Open Addressing
Michael A. Bender, William Kuszmaul, and Renfei Zhou
(Stony Brook University, USA; Carnegie Mellon University, USA)

Publisher's Version

Optimal Static Dictionary with Worst-Case Constant Query Time
Yang Hu, Jingxun Liang, Huacheng Yu, Junkai Zhang, and Renfei Zhou
(Tsinghua University, China; Carnegie Mellon University, USA; Princeton University, USA)

Publisher's Version

On the Hardness Hierarchy for the 𝑂(𝑛 √log 𝑛) Complexity in the Word RAM
Dominik Kempa and Tomasz Kociumaka
(Stony Brook University, USA; MPI-INF, Germany)

Publisher's Version

Session 4A

The Hypergraph Removal Process
Felix Joos and Marcus Kühn
(Heidelberg University, Germany)

Publisher's Version

Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
Kiril Bangachev and Guy Bresler
(Massachusetts Institute of Technology, USA)

Publisher's Version

A Sharp Version of Talagrand’s Selector Process Conjecture and an Application to Rounding Fractional Covers
Huy Tuan Pham
(Institute for Advanced Study at Princeton, USA)

Publisher's Version

Disjoint Connected Dominating Sets in Pseudorandom Graphs
Nemanja Draganić and Michael Krivelevich
(University of Oxford, UK; Tel Aviv University, Israel)

Publisher's Version

Minimum Degree Edge-Disjoint Hamilton Cycles in Random Directed Graphs
Asaf Ferber and Adva Mond
(University of California at Irvine, USA; King's College London, UK)

Publisher's Version

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
Jason Gaitonde, Ankur Moitra, and Elchanan Mossel
(Massachusetts Institute of Technology, USA)

Publisher's Version

Session 4B

Optimality of Frequency Moment Estimation
Mark Braverman and Or Zamir
(Princeton University, USA; Tel Aviv University, Israel)

Publisher's Version

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu, and Zhewei Wei
(Fudan University, China; Renmin University of China, China)

Publisher's Version

Harmonic Decomposition in Data Sketches
Dingyu Wang
(University of Michigan, USA)

Publisher's Version

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou
(Princeton University, USA; Carnegie Mellon University, USA; Texas A&M University, USA)

Publisher's Version

Efficient Algorithms and New Characterizations for CSP Sparsification
Sanjeev Khanna, Aaron Putterman, and Madhu Sudan
(University of Pennsylvania, USA; Harvard University, USA)

Publisher's Version

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Sepehr Assadi, Sanjeev Khanna, and Aaron Putterman
(University of Waterloo, Canada; University of Pennsylvania, USA; Harvard University, USA)

Publisher's Version

Session 4C

Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation
Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang
(Harvard University, USA; Tsinghua University, China)

Publisher's Version

Single-Copy Stabilizer Testing
Marcel Hinsche and Jonas Helsen
(Freie Universität Berlin, Germany; IBM Quantum Zurich, Switzerland; CWI, Netherlands; QuSoft, Netherlands)

Publisher's Version

Distributed Quantum Advantage for Local Problems
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren
(Gran Sasso Science Institute, Italy; CISPA Helmholtz Center for Information Security, Germany; University of Calgary, Canada; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; Bocconi Institute for Data Science and Analytics, Italy; Aalto University, Finland; Nagoya University, Japan; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France)

Publisher's Version

The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement
Adam Bouland, Tudor Giurgică-Tiron, and John Wright
(Stanford University, USA; University of Maryland, USA; University of California at Berkeley, USA)

Publisher's Version

Positive Bias Makes Tensor-Network Contraction Tractable
Jiaqing Jiang, Jielun Chen, Norbert Schuch, and Dominik Hangleiter
(California Institute of Technology, USA; University of Vienna, Austria; University of California at Berkeley, USA; University of Maryland, USA; NIST, USA)

Publisher's Version

Session 4D

Multi-parameter Mechanisms for Consumer Surplus Maximization
Tomer Ezra, Daniel Schoepflin, and Ariel Shaulker
(Harvard University, USA; Rutgers University, USA; Weizmann Institute of Science, Israel)

Publisher's Version

Approximation Guarantees of Median Mechanism in ℝᵈ
Nikolai Gravin and Jianhao Jia
(Shanghai University of Finance and Economics, China)

Publisher's Version

Monotone Contractions
Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani
(University of Liverpool, UK; University of Illinois at Urbana-Champaign, USA; Alan Turing Institute, UK)

Publisher's Version

Faster Rates for No-Regret Learning in General Games via Cautious Optimism
Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina
(Massachusetts Institute of Technology, USA; Google DeepMind, UK)

Publisher's Version

Computational Lower Bounds for No-Regret Learning in Normal-Form Games
Ioannis Anagnostides, Alkis Kalavasis, and Tuomas Sandholm
(Carnegie Mellon University, USA; Yale University, USA)

Publisher's Version

Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Charilaos Pipis, and Jon Schneider
(Massachusetts Institute of Technology, USA; Google Research, USA)

Publisher's Version

Session 5A

The Structure of Catalytic Space: Capturing Randomness and Time via Compression
James Cook, Jiatu Li, Ian Mertz, and Edward Pyne
(Unaffiliated, Canada; Massachusetts Institute of Technology, USA; University of Warwick, UK)

Publisher's Version

Constant-Cost Communication Is Not Reducible to k-Hamming Distance
Yuting Fang, Mika Göös, Nathaniel Harms, and Pooya Hatami
(Ohio State University, USA; EPFL, Switzerland)

Publisher's Version

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
Simon Mackenzie and Abdallah Saffidine
(Unaffiliated, Australia; Potassco Solutions, Germany)

Publisher's Version

Lifting to Bounded-Depth and Regular Resolutions over Parities via Games
Yaroslav Alekseev and Dmitry Itsykson
(Technion, Israel; Ben-Gurion University of the Negev, Israel)

Publisher's Version

Extractors for Samplable Distributions with Low Min-Entropy
Marshall Ball, Ronen Shaltiel, and Jad Silbak
(New York University, USA; University of Haifa, Israel; Northeastern University, USA)

Publisher's Version

Leakage-Resilient Extractors against Number-on-Forehead Protocols
Eshan Chattopadhyay and Jesse Goodman
(Cornell University, USA; University of Texas at Austin, USA)

Publisher's Version

Session 5B

A (2+ε)-Approximation Algorithm for Metric 𝑘-Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, and Ola Svensson
(Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Aarhus University, Denmark; EPFL, Switzerland)

Publisher's Version

On Approximability of the Permanent of PSD Matrices
Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan
(University of Washington, USA; University of California at Berkeley, USA)

Publisher's Version

Rounding Large Independent Sets on Expanders
Mitali Bafna, Jun-Ting Hsieh, and Pravesh K. Kothari
(Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Princeton University, USA)

Publisher's Version

Optimal Rounding for Sparsest Cut
Alan Chang, Assaf Naor, and Kevin Ren
(Washington University in St. Louis, USA; Princeton University, USA)

Publisher's Version

A 5/4-Approximation for Two-Edge Connectivity
Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim, Afrouz Jabal Ameli, and Alexander Lindermayr
(IDSIA at USI-SUPSI, Switzerland; Indian Institute of Science, India; University of Bremen, Germany; Eindhoven University of Technology, Netherlands)

Publisher's Version

Near-Optimal Dimension Reduction for Facility Location
Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Di Yue
(Nanjing University, China; Peking University, China; Weizmann Institute of Science, Israel)

Publisher's Version

Session 5C

Locality vs Quantum Codes
Samuel Dai and Ray Li
(Northeastern University, USA; Santa Clara University, USA)

Publisher's Version

Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes
Louis Golowich and Ting-Chun Lin
(University of California at Berkeley, USA; University of California at San Diego, USA; Hon Hai Research Institute, Taiwan)

Publisher's Version

Good Binary Quantum Codes with Transversal CCZ Gate
Quynh T. Nguyen
(Harvard University, USA)

Publisher's Version

Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates
Louis Golowich and Venkatesan Guruswami
(University of California at Berkeley, USA)

Publisher's Version

Pauli Measurements Are Not Optimal for Single-Copy Tomography
Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, and Nengkun Yu
(Cornell University, USA; Rice University, USA; Stony Brook University, USA)

Publisher's Version

Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads
Quynh T. Nguyen and Christopher A. Pattison
(Harvard University, USA; California Institute of Technology, USA)

Publisher's Version

Quantum Advantage from Soft Decoders
André Chailloux and Jean-Pierre Tillich
(Inria, France)

Publisher's Version

Session 5D

Asymptotic Tensor Rank Is Characterized by Polynomials
Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Péter Vrana, and Jeroen Zuiddam
(University of Copenhagen, Denmark; University of Amsterdam, Netherlands; Budapest University of Technology and Economics, Hungary)

Publisher's Version

Computing Moment Polytopes of Tensors, with Applications in Algebraic Complexity and Quantum Information
Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, and Jeroen Zuiddam
(Ruhr University Bochum, Germany; University of Amsterdam, Netherlands; University of Copenhagen, Denmark)

Publisher's Version

On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications
Joshua A. Grochow and Youming Qiao
(University of Colorado Boulder, USA; University of Technology Sydney, Australia)

Publisher's Version

On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings
Joshua A. Grochow, Youming Qiao, Katherine E. Stange, and Xiaorui Sun
(University of Colorado Boulder, USA; University of Technology Sydney, Australia; University of Illinois at Chicago, USA)

Publisher's Version

Error-Correction of Matrix Multiplication Algorithms
Shuichi Hirahara and Nobutaka Shimizu
(National Institute of Informatics, Japan; Institute of Science Tokyo, Japan)

Publisher's Version

Matrix Chaos Inequalities and Chaos of Combinatorial Type
Afonso S. Bandeira, Kevin Lucca, Petar Nizic-Nikolac, and Ramon van Handel
(ETH Zurich, Switzerland; Princeton University, USA)

Publisher's Version

Session 6A

How to Construct Random Unitaries
Fermi Ma and Hsin-Yuan Huang
(Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; Google, USA; California Institute of Technology, USA)

Publisher's Version

High Rate Multivariate Polynomial Evaluation Codes
Swastik Kopparty, Mrinal Kumar, and Harry Sha
(University of Toronto, Canada; TIFR, India)

Publisher's Version

Tensor Concentration Inequalities: A Geometric Approach
Afonso S. Bandeira, Sivakanth Gopi, Haotian Jiang, Kevin Lucca, and Thomas Rothvoss
(ETH Zurich, Switzerland; Microsoft Research, USA; University of Chicago, USA; University of Washington, USA)

Publisher's Version

Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier
Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O'Donnell, and Rachel Yun Zhang
(Carnegie Mellon University, USA; University of California at San Diego, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Explicit Codes Approaching Generalized Singleton Bound using Expanders
Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava, and Madhur Tulsiani
(University of Illinois at Urbana-Champaign, USA; Stanford University, USA; Rutgers University, USA; Institute for Advanced Study at Princeton, USA; Toyota Technological Institute at Chicago, USA)

Publisher's Version

List-Decoding Capacity Implies Capacity on the 𝑞-ary Symmetric Channel
Francisco Pernice, Oscar Sprumont, and Mary Wootters
(Massachusetts Institute of Technology, USA; University of Washington, USA; Stanford University, USA)

Publisher's Version

Session 6B

Counting Random 𝑘-SAT near the Satisfiability Threshold
Zongchen Chen, Aditya Lonkar, Chunyang Wang, Kuan Yang, and Yitong Yin
(Georgia Institute of Technology, USA; Nanjing University, China; Shanghai Jiao Tong University, China)

Publisher's Version

Rapid Mixing at the Uniqueness Threshold
Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang
(Nanjing University, China; Georgia Institute of Technology, USA)

Publisher's Version

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
Youngtak Sohn and Alexander S. Wein
(Brown University, USA; University of California at Davis, USA)

Publisher's Version

Phase Transitions via Complex Extensions of Markov Chains
Jingcheng Liu, Chunyang Wang, Yitong Yin, and Yixiao Yu
(Nanjing University, China)

Publisher's Version

Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses
Brice Huang, Sidhanth Mohanty, Amit Rajaraman, and David X. Wu
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)

Publisher's Version

Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
Yunbum Kook and Santosh S. Vempala
(Georgia Institute of Technology, USA)

Publisher's Version

Session 6C

Universal SNARGs for NP from Proofs of Correctness
Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, and Surya Mathialagan
(Northeastern University, USA; Massachusetts Institute of Technology, USA; Princeton University, USA)

Publisher's Version

Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness
Liyan Chen, Cody Freitag, Zhengzhong Jin, and Daniel Wichs
(Tsinghua University, China; Northeastern University, USA; NTT Research, USA)

Publisher's Version

Succinct Non-interactive Arguments of Proximity
Liyan Chen, Zhengzhong Jin, and Daniel Wichs
(Tsinghua University, China; Northeastern University, USA; NTT Research, USA)

Publisher's Version

The Meta-complexity of Secret Sharing
Benny Applebaum and Oded Nir
(Tel Aviv University, Israel)

Publisher's Version

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)
Lijie Chen, Ron D. Rothblum, and Roei Tell
(University of California at Berkeley, USA; Technion, Israel; University of Toronto, Canada)

Publisher's Version

A Zero-Knowledge PCP Theorem
Tom Gur, Jack O'Connor, and Nicholas Spooner
(University of Cambridge, UK; Cornell University, USA)

Publisher's Version

Session 6D

Testing Support Size More Efficiently Than Learning Histograms
Renato Ferreira Pinto Jr. and Nathaniel Harms
(University of Waterloo, Canada; EPFL, Switzerland)

Publisher's Version

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, and Sayantan Sen
(Indian Statistical Institute, Kolkata, India; Technion, Israel; University of Haifa, Israel; National University of Singapore, Singapore)

Publisher's Version

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, and Erik Waingarten
(Dartmouth College, USA; Columbia University, USA; University of Pennsylvania, USA; University of California at Santa Cruz, USA)

Publisher's Version

A Tolerant Independent Set Tester
Cameron Seth
(University of Waterloo, Canada)

Publisher's Version

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
Talya Eden, Reut Levi, Dana Ron, and Ronitt Rubinfeld
(Bar-Ilan University, Israel; Reichman University, Israel; Tel Aviv University, Israel; Massachusetts Institute of Technology, USA)

Publisher's Version Info

Stochastic Matching via In-n-Out Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld
(Northeastern University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Info

Session 7A

Characterizing and Testing Principal Minor Equivalence of Matrices
Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj
(IIT Kanpur, India; Indian Statistical Institute, Kolkata, India; IIT Bombay, India)

Publisher's Version

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
Abhibhav Garg, Rafael Oliveira, and Nitin Saxena
(University of Waterloo, Canada; IIT Kanpur, India)

Publisher's Version

Polynomial-Time PIT from (Almost) Necessary Assumptions
Robert Andrews, Deepanshu Kush, and Roei Tell
(University of Waterloo, Canada; University of Toronto, Canada)

Publisher's Version

Feasibly Constructive Proof of Schwartz–Zippel Lemma and the Complexity of Finding Hitting Sets
Albert Atserias and Iddo Tzameret
(Universitat Politecnica de Catalunya, Spain; Imperial College London, UK)

Publisher's Version

When Connectivity Is Hard, Random Walks Are Easy with Non-determinism
Dean Doron, Edward Pyne, Roei Tell, and R. Ryan Williams
(Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada)

Publisher's Version

Vanishing of Schubert Coefficients
Igor Pak and Colleen Robichaux
(University of California at Los Angeles, USA)

Publisher's Version

Session 7B

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
Niv Buchbinder and Moran Feldman
(Tel Aviv University, Israel; University of Haifa, Israel)

Publisher's Version

Better Approximation for Weighted 𝑘-Matroid Intersection
Neta Singer and Theophile Thiery
(EPFL, Switzerland)

Publisher's Version

Solving the Correlation Cluster LP in Sublinear Time
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang
(New York University, USA; Google Research, USA; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland)

Publisher's Version

Fully Dynamic 𝑘-Median with Near-Optimal Update Time and Recourse
Sayan Bhattacharya, Martín Costa, and Ermiya Farokhnejad
(University of Warwick, UK)

Publisher's Version

Dynamic Locality Sensitive Orderings in Doubling Metrics
An La and Hung Le
(University of Massachusetts at Amherst, USA)

Publisher's Version

Near-Optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
Sanjeev Khanna, Huan Li, and Aaron Putterman
(University of Pennsylvania, USA; Harvard University, USA)

Publisher's Version

Session 7C

Learning the Structure of Any Hamiltonian from Minimal Assumptions
Andrew Zhao
(Sandia National Laboratories, USA)

Publisher's Version

Learning the Closest Product State
Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, and Ewin Tang
(Massachusetts Institute of Technology, USA; Columbia University, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA)

Publisher's Version

Improved Bounds for Testing Low Stabilizer Complexity States
Saeed Mehraban and Mehrdad Tahmasbi
(Tufts University, USA; University of Illinois at Urbana-Champaign, USA)

Publisher's Version

Polynomial-Time Tolerant Testing Stabilizer States
Srinivasan Arunachalam and Arkopal Dutt
(IBM Quantum, USA)

Publisher's Version

Dimension Independent and Computationally Efficient Shadow Tomography
Pulkit Sinha
(University of Waterloo, Canada)

Publisher's Version

Tolerant Testing of Stabilizer States with a Polynomial Gap via a Generalized Uncertainty Relation
Zongbo Bao, Philippe van Dordrecht, and Jonas Helsen
(CWI, Netherlands; QuSoft, Netherlands; University of Amsterdam, Netherlands)

Publisher's Version

Testing and Learning Structured Quantum Hamiltonians
Srinivasan Arunachalam, Arkopal Dutt, and Francisco Escudero Gutiérrez
(IBM, USA; CWI, Netherlands)

Publisher's Version

Session 7D

On the Locality of the Lovász Local Lemma
Peter Davies-Peck
(Durham University, UK)

Publisher's Version

History-Independent Concurrent Hash Tables
Hagit Attiya, Michael A. Bender, Martín Farach-Colton, Rotem Oshman, and Noa Schiller
(Technion, Israel; Stony Brook University, USA; New York University, USA; Tel Aviv University, Israel)

Publisher's Version

Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, and Jukka Suomela
(Aalto University, Finland; University of Calgary, Canada; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; Gran Sasso Science Institute, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Université Paris-Saclay, France; Ecole Polytechnique, France; INSAIT, Bulgaria)

Publisher's Version

Faster Distributed Δ-Coloring via Ruling Subgraphs
Yann Bourreau, Sebastian Brandt, and Alexandre Nolin
(CISPA Helmholtz Center for Information Security, Germany)

Publisher's Version

Constant Degree Networks for Almost-Everywhere Reliable Transmission
Mitali Bafna and Dor Minzer
(Massachusetts Institute of Technology, USA)

Publisher's Version

Session 8A

Optimal Proof Systems for Complex Sets Are Hard to Find
Fabian Egidy and Christian Glaßer
(University of Würzburg, Germany)

Publisher's Version

Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap
Stefan Grosser and Marco Carmosino
(McGill University, Canada; IBM Research, USA)

Publisher's Version

Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin
Lijie Chen, Jiatu Li, and Jingxun Liang
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA)

Publisher's Version

Supercritical Tradeoffs for Monotone Circuits
Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov
(EPFL, Switzerland)

Publisher's Version

Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, and Shuo Pang
(Lund University, Sweden; Memorial University of Newfoundland, Canada; University of Copenhagen, Denmark)

Publisher's Version

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
Josh Alman and Jingxun Liang
(Columbia University, USA; Carnegie Mellon University, USA)

Publisher's Version

Session 8B

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang
(Nanjing University, China; Tsinghua University, China; TU Munich, Germany)

Publisher's Version

The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam
(Google, Switzerland; Sapienza University of Rome, Italy; Google, Spain; EPFL, Switzerland)

Publisher's Version

Tight Results for Online Convex Paging
Anupam Gupta, Amit Kumar, and Debmalya Panigrahi
(New York University, USA; IIT Delhi, India; Duke University, USA)

Publisher's Version

Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum
Enze Sun, Zhihao Gavin Tang, and Yifan Wang
(University of Hong Kong, China; Shanghai University of Finance and Economics, China; Georgia Institute of Technology, USA)

Publisher's Version

Single-Sample and Robust Online Resource Allocation
Rohan Ghuge, Sahil Singla, and Yifan Wang
(Georgia Institute of Technology, USA)

Publisher's Version

Adaptive Approximation Schemes for Matching Queues
Alireza AmaniHamedani, Ali Aouad, and Amin Saberi
(London Business School, UK; Massachusetts Institute of Technology, USA; Stanford University, USA)

Publisher's Version

Session 8C

Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li
(EPFL, Switzerland; University of Cambridge, UK; University of Texas at Austin, USA)

Publisher's Version

On the Computational Power of QAC0 with Barely Superlinear Ancillae
Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao
(Harvard University, USA; Nanjing University, China; Hefei National Laboratory, China)

Publisher's Version

Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers
Cambyse Rouzé, Daniel Stilck França, and Álvaro M. Alhambra
(Inria, France; IPP, France; University of Copenhagen, Denmark; Inria-ENS Lyon, France; Instituto de Física Teórica, Spain; CSIC, Spain)

Publisher's Version

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk
(Massachusetts Institute of Technology, USA; Harvard University, USA)

Publisher's Version

Permutation Superposition Oracles for Quantum Query Lower Bounds
Christian Majenz, Giulio Malavolta, and Michael Walter
(DTU, Denmark; Bocconi University, Italy; Ruhr University Bochum, Germany)

Publisher's Version

QMA vs QCMA and Pseudorandomness
Jiahui Liu, Saachi Mutreja, and Henry Yuen
(Fujitsu Research, USA; Columbia University, USA)

Publisher's Version

Session 8D

Tractable Agreement Protocols
Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth
(University of Pennsylvania, USA)

Publisher's Version

Share-Based Fairness for Arbitrary Entitlements
Moshe Babaioff and Uriel Feige
(Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel)

Publisher's Version

From Signaling to Interviews in Random Matching Markets
Maxwell Allman, Itai Ashlagi, Amin Saberi, and Sophie H. Yu
(Stanford University, USA; University of Pennsylvania, USA)

Publisher's Version

Metric Distortion of Small-Group Deliberation
Ashish Goel, Mohak Goyal, and Kamesh Munagala
(Stanford University, USA; Duke University, USA)

Publisher's Version

Constant-Factor EFX Exists for Chores
Jugal Garg, Aniket Murhekar, and John Qin
(University of Illinois at Urbana-Champaign, USA)

Publisher's Version

Six Candidates Suffice to Win a Voter Majority
Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang
(Stanford University, USA; Eindhoven University of Technology, Netherlands; McGill University, Canada; Rutgers University, USA)

Publisher's Version

Session 9A

Time and Space Efficient Deterministic Decoders
Joshua Cook and Dana Moshkovitz
(University of Texas at Austin, USA)

Publisher's Version

Redundancy Is All You Need
Joshua Brakensiek and Venkatesan Guruswami
(University of California at Berkeley, USA)

Publisher's Version

Strong XOR Lemma for Information Complexity
Pachara Sawettamalya and Huacheng Yu
(Princeton University, USA)

Publisher's Version

Ideal Pseudorandom Codes
Omar Alrabiah, Prabhanjan Ananth, Miranda Christ, Yevgeniy Dodis, and Sam Gunn
(University of California at Berkeley, USA; University of California at Santa Barbara, USA; Columbia University, USA; New York University, USA)

Publisher's Version

Improved PIR Schemes using Matching Vectors and Derivatives
Fatemeh Ghasemi, Swastik Kopparty, and Madhu Sudan
(University of Toronto, Canada; Harvard University, USA)

Publisher's Version

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
Joey Rivkin, Gregory Valiant, and Paul Valiant
(Stanford University, USA; Purdue University, USA)

Publisher's Version

Session 9B

Discrepancy Algorithms for the Binary Perceptron
Shuangping Li, Tselil Schramm, and Kangjie Zhou
(Stanford University, USA; Columbia University, USA)

Publisher's Version

Entangled Mean Estimation in High Dimensions
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, and Thanasis Pittas
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)

Publisher's Version

SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, and Stefan Tiegel
(University of Wisconsin-Madison, USA; Massachusetts Institute of Technology, USA; University of California at Berkeley, USA; ETH Zurich, Switzerland)

Publisher's Version

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, and Stefan Tiegel
(University of Wisconsin-Madison, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; ETH Zurich, Switzerland)

Publisher's Version

How Random CSPs Fool Hierarchies: II
Siu On Chan and Hiu Tsun Ng
(Unaffiliated, Hong Kong)

Publisher's Version

Coboundary Expansion of Coset Complexes
Tali Kaufman, Izhar Oppenheim, and Shmuel Weinberger
(Bar-Ilan University, Israel; Ben-Gurion University of the Negev, Israel; University of Chicago, USA)

Publisher's Version

Session 9C

On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse
Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas
(Yale University, USA)

Publisher's Version

Provably Learning a Multi-head Attention Layer
Sitan Chen and Yuanzhi Li
(Harvard University, USA; MBZUAI, United Arab Emirates)

Publisher's Version

Model Stealing for Any Low-Rank Language Model
Allen Liu and Ankur Moitra
(Massachusetts Institute of Technology, USA)

Publisher's Version

Omnipredicting Single-Index Models with Multi-index Models
Lunjia Hu, Kevin Tian, and Chutong Yang
(Harvard University, USA; University of Texas at Austin, USA)

Publisher's Version

Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
Gautam Chandrasekaran and Adam R. Klivans
(University of Texas at Austin, USA)

Publisher's Version

Oblivious Defense in ML Models: Backdoor Removal without Detection
Shafi Goldwasser, Jonathan Shafer, Neekon Vafa, and Vinod Vaikuntanathan
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Video

Session 9D

The FPᴺᴾ versus #P Dichotomy for #EO
Boning Meng, Juqiu Wang, and Mingji Xia
(Institute of Software at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China)

Publisher's Version

Locally Sampleable Uniform Symmetric Distributions
Daniel M. Kane, Anthony Ostuni, and Kewen Wu
(University of California at San Diego, USA; University of California at Berkeley, USA)

Publisher's Version

Uncloneable Quantum States Are Necessary as Proofs and Advice
Rohit Chatterjee, Srijita Kundu, and Supartha Podder
(National University of Singapore, Singapore; University of Waterloo, Canada; Stony Brook University, USA)

Publisher's Version

Learning Quantum States Prepared by Shallow Circuits in Polynomial Time
Zeph Landau and Yunchao Liu
(University of California at Berkeley, USA; Harvard University, USA)

Publisher's Version

The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
Karoliina Lehtinen and Aditya Prakash
(CNRS - Aix-Marseille Université, France; University of Warwick, UK)

Publisher's Version

Reachability in One-Dimensional Pushdown Vector Addition Systems Is Decidable
Clotilde Bizière and Wojciech Czerwiński
(University of Bordeaux, France; University of Warsaw, Poland)

Publisher's Version

Session 10A

Cryptographic Characterization of Quantum Advantage
Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa
(Kyoto University, Japan; NTT, Japan)

Publisher's Version

Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits
Damiano Abram, Giulio Malavolta, and Lawrence Roy
(Bocconi University, Italy; Aarhus University, Denmark)

Publisher's Version

Protecting Computations against Continuous Bounded-Communication Leakage
Yuval Ishai and Yifan Song
(Technion, Israel; Amazon Web Services, USA; Tsinghua University, China; Shanghai Qi Zhi Institute, China)

Publisher's Version

A New Approach for LPN-Based Pseudorandom Functions: Low-Depth and Key-Homomorphic
Youlong Ding, Aayush Jain, and Ilan Komargodski
(Hebrew University of Jerusalem, Israel; Carnegie Mellon University, USA; NTT Research, USA)

Publisher's Version

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev, Guy Bresler, Stefan Tiegel, and Vinod Vaikuntanathan
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)

Publisher's Version

Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders
Riddhi Ghosal, Isaac M. Hair, Aayush Jain, and Amit Sahai
(University of California at Los Angeles, USA; University of California at Santa Barbara, USA; Carnegie Mellon University, USA)

Publisher's Version

Session 10B

Disjoint Paths Problem with Group-Expressable Constraints
Chun-Hung Liu and Youngho Yoo
(Texas A&M University, USA)

Publisher's Version

Merge-Width and First-Order Model Checking
Jan Dreier and Szymon Toruńczyk
(TU Wien, Austria; University of Warsaw, Poland)

Publisher's Version

All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, and Zoe Xi
(Weizmann Institute of Science, Israel; Sofia University St. Kliment Ohridski, Bulgaria; Massachusetts Institute of Technology, USA)

Publisher's Version

Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi
(University of California at Santa Barbara, USA; University of Leeds, UK; IMSc, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel)

Publisher's Version

Subexponential Parameterized Algorithms for Hitting Subgraphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi
(University of California at Santa Barbara, USA; University of Leeds, UK; IMSc, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel)

Publisher's Version

Output-Sensitive Approximate Counting via a Measure-Bounded Hyperedge Oracle, or: How Asymmetry Helps Estimate 𝑘-Clique Counts Faster
Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams
(Technion, Israel; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 10C

Agnostic Smoothed Online Learning
Moïse Blanchard
(Columbia University, USA)

Publisher's Version

Breaking the T^(2/3) Barrier for Sequential Calibration
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, and Princewill Okoroafor
(Tel Aviv University, Israel; Massachusetts Institute of Technology, USA; Cornell University, USA)

Publisher's Version

Almost Optimal PAC Learning for 𝑘-Means
Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn
(Google Research, France; Google, Spain; Aarhus University, Denmark)

Publisher's Version

Adaptive and Oblivious Statistical Adversaries Are Equivalent
Guy Blanc and Gregory Valiant
(Stanford University, USA)

Publisher's Version

On Reductions and Representations of Learning Problems in Euclidean Spaces
Bogdan Chornomaz, Shay Moran, and Tom Waknine
(Technion, Israel; Google Research, Israel)

Publisher's Version

DNF Learning via Locally Mixing Random Walks
Josh Alman, Shivam Nadimpalli, Shyamal Patel, and Rocco A. Servedio
(Columbia University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 10D

Weak Recovery, Hypothesis Testing, and Mutual Information in Stochastic Block Models and Planted Factor Graphs
Elchanan Mossel, Allan Sly, and Youngtak Sohn
(Massachusetts Institute of Technology, USA; Princeton University, USA; Brown University, USA)

Publisher's Version

Matroid Products via Submodular Coupling
Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, Balázs Maga, and Tamás Schwarcz
(Eötvös Loránd University, Hungary; HUN-REN Alfréd Rényi Institute of Mathematics, Hungary; London School of Economics and Political Science, UK)

Publisher's Version

Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
Lin Chen, Yuchen Mao, and Guochuan Zhang
(Zhejiang University, China)

Publisher's Version

Smoothed Analysis for Graph Isomorphism
Michael Anastos, Matthew Kwan, and Benjamin Moore
(IST Austria, Austria)

Publisher's Version

Statistical Inference of a Ranked Community in a Directed Graph
Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, and Xifan Yu
(Johns Hopkins University, USA; Yale University, USA; University of California at Davis, USA)

Publisher's Version

Session 11A

Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity
Mitali Bafna, Karthik C. S., and Dor Minzer
(Massachusetts Institute of Technology, USA; Rutgers University, USA)

Publisher's Version

Treewidth Inapproximability and Tight ETH Lower Bound
Édouard Bonnet
(CNRS - ENS Lyon - Université Claude Bernard Lyon 1 - LIP, France)

Publisher's Version

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu
(University of California at Berkeley, USA; Nanjing University, China; Peking University, China)

Publisher's Version

A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
Karl Bringmann and Egor Gorbachev
(Saarland University, Germany; MPI-INF, Germany)

Publisher's Version

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
Egor Gorbachev and Tomasz Kociumaka
(Saarland University, Germany; MPI-INF, Germany)

Publisher's Version

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, and Christopher Ye
(ETH Zurich, Switzerland; Bocconi University, Italy; University of California at San Diego, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 11B

Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm
Kim-Manuel Klein and Janina Reuter
(University of Lübeck, Germany; University of Kiel, Germany)

Publisher's Version

Symmetric Perceptrons, Number Partitioning and Lattices
Neekon Vafa and Vinod Vaikuntanathan
(Massachusetts Institute of Technology, USA)

Publisher's Version

Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs
Li Chen, Andrei Graur, and Aaron Sidford
(Independent, USA; Stanford University, USA)

Publisher's Version

Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices
Adrian Vladu
(CNRS, France; IRIF, France)

Publisher's Version

Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
Ruichen Jiang, Aryan Mokhtari, and Francisco Patitucci
(University of Texas at Austin, USA)

Publisher's Version

Fast, Robust Approximate Message Passing
Misha Ivkov and Tselil Schramm
(Stanford University, USA)

Publisher's Version

Session 11C

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
Itai Boneh, Shiri Chechik, Shay Golan, Shay Mozes, and Oren Weimann
(Reichman University, Israel; University of Haifa, Israel; Tel Aviv University, Israel)

Publisher's Version

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Hsien-Chih Chang, Jonathan Conroy, Hung Le, Shay Solomon, and Cuong Than
(Dartmouth College, USA; University of Massachusetts at Amherst, USA; Tel Aviv University, Israel)

Publisher's Version

Covering Approximate Shortest Paths with DAGs
Sepehr Assadi, Gary Hoppenworth, and Nicole Wein
(University of Waterloo, Canada; University of Michigan, USA)

Publisher's Version

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
Jonathan Conroy and Arnold Filtser
(Dartmouth College, USA; Bar-Ilan University, Israel)

Publisher's Version

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA; Hebrew University of Jerusalem, Israel; ETH Zurich, Switzerland)

Publisher's Version

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, and Sorrachai Yingchareonthawornchai
(CWI, Netherlands; KTH Royal Institute of Technology, Sweden; MPI-INF, Germany; Saarland University, Germany; University of Birmingham, UK; ETH Zurich, Switzerland; Hebrew University of Jerusalem, Israel)

Publisher's Version

Session 11D

Approximation Algorithms for the Geometric Multimatching Problem
Shinwoo An, Eunjin Oh, and Jie Xue
(POSTECH, Republic of Korea; New York University Shanghai, China)

Publisher's Version

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
Siu-Wing Cheng, Haoqiang Huang, and Shuo Zhang
(Hong Kong University of Science and Technology, Hong Kong; Renmin University of China, China)

Publisher's Version

Sample-Optimal Private Regression in Polynomial Time
Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)

Publisher's Version

Privately Evaluating Untrusted Black-Box Functions
Ephraim Linder, Sofya Raskhodnikova, Adam Smith, and Thomas Steinke
(Boston University, USA; Google Research, USA)

Publisher's Version

On Differentially Private Linear Algebra
Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur
(Tel Aviv University, Israel; Google Research, Israel; Technion, Israel)

Publisher's Version

Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Xin Lyu and Kunal Talwar
(University of California at Berkeley, USA; Apple, USA)

Publisher's Version

proc time: 1.52