STOC 2025 Accepted Papers

---

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

Universal SNARGs for NP from Proofs of Completeness
Zhengzhong Jin (Northeastern); Yael Kalai (MIT and MSR); Alex Lombardi (Princeton); Surya Mathialagan (MIT)

Positive bias makes tensor-network contraction tractable
Jiaqing Jiang, Jielun Chen (Caltech); Norbert Schuch (University of Vienna); Dominik Hangleiter (UC Berkeley)

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

On approximability of the Permanent of PSD matrices
Farzam Ebrahimnejad (University of Washington); Ansh Nagda (UC Berkeley); Shayan Oveis Gharan (University of Washington)

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

Disjoint paths problem with group-expressable constraints
Chun-Hung Liu (Texas A&M Univeristy); Youngho Yoo (Texas A&M University)

The hypergraph removal process
Felix Joos, Marcus Kühn (Universität Heidelberg)

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

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

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

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

Learning the structure of any Hamiltonian from minimal assumptions
Andrew Zhao (Sandia National Laboratories)

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

Treewidth Inapproximability and Tight ETH Lower Bound
Édouard Bonnet (CNRS, ENS Lyon, LIP)

The state hidden subgroup problem and an efficient algorithm for locating unentanglement
Adam Bouland (Stanford University); Tudor Giurgica-Tiron (Stanford); John Wright (The University of California, Berkeley)

Share-Based Fairness for Arbitrary Entitlements
Moshe Babaioff (Hebrew University); Uriel Feige (Weizmann Institute)

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

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

Asymptotic tensor rank is characterized by polynomials
Matthias Christandl (University of Copenhagen); Koen Hoeberechts (University of Amsterdam); Harold Nieuwboer (University of Copenhagen); Peter Vrana (Budapest University of Technology and Economics); Jeroen Zuiddam (University of Amsterdam)

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

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

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

Multi-Parameter Mechanisms for Consumer Surplus Maximization
Tomer Ezra (Harvard University); Daniel Schoepflin (Rutgers University); Ariel Shaulker (Weizmann Institute)

Approximation Algorithms for Satisfiable CSPs via a Mixed Invariance Principle
Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT)

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

Constant-Cost Communication is not Reducible to k-Hamming Distance
Yuting Fang (Ohio State University); Mika Göös, Nathaniel Harms (EPFL); Pooya Hatami (The Ohio State University)

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

The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Duetting (Google); Federico Fusco (Sapienza University of Rome); Silvio Lattanzi (Google); Ashkan Norouzi-Fard (Google Zurich); Ola Svensson (EPFL); Morteza Zadimoghaddam (Google)

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

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

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

The FP^NP versus #P dichotomy for #EO
Boning Meng, Juqiu Wang (Institute of Software, Chinese Academy of Sciences); Mingji Xia (State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences. University of Chinese Academy of Sciences.)

Coboundary expansion of coset complexes
Izhar Oppenheim (Ben-Gurion University); Tali Kaufman (Bar Ilan University); Shmuel Weinberger (University of Chicago)

Rounding Large Independent Sets on Expanders
Mitali Bafna (MIT); Jun-Ting Hsieh (Carnegie Mellon University); Pravesh Kothari (Princeton University and IAS)

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

Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes
Louis Golowich (UC Berkeley); Ting-Chun Lin (UC San Diego)

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

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
Karl Bringmann, Egor Gorbachev (Saarland University and Max Planck Institute for Informatics)

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

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

Quantum-Computable One-Way Functions without One-Way Functions
William Kretschmer (Simons Institute); Luowen Qian (NTT Research, Inc.); Avishay Tal (UC Berkeley)

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

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

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

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
Simon Mackenzie (None); Abdallah Saffidine (unaffiliated)

Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable
Clotilde Bizière (Université de Bordeaux); Wojciech Czerwinski (University of Warsaw)

Lifting to bounded-depth and regular resolutions over parities via games
Yaroslav Alekseev (Technion – Israel Institute of Technology); Dmitry Itsykson (Ben-Gurion University of the Negev)

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

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

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

Hardness of 4-colouring G-colourable graphs
Sergey Avvakumov (Tel Aviv University); Marek Filakovský (Masaryk University); Jakub Opršal (University of Birmingham); Gianluca Tasinato, Uli Wagner (Institute of Science and Technology Austria (ISTA))

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

Approximation guarantees of Median Mechanism in ℝ^d
Nick Gravin, Jianhao Jia (Shanghai University of FInance and Economics, China)

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

From signaling to interviews in random matching markets
Maxwell Allman, Itai Ashlagi, Amin Saberi (Stanford University); Sophie H. Yu (University of Pennsylvania)

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

Approximately counting and sampling Hamiltonian motifs in sublinear time
Reut Levi (Reichman University); Talya Eden (Bar Ilan University); Dana Ron (Tel Aviv University); Ronitt Rubinfeld (MIT)

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

Entangled Mean Estimation in High Dimensions
Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Sihan Liu (UCSD); Thanasis Pittas (UW Madison)

Counting random k-SAT near the satisfiability threshold
Zongchen Chen, Aditya Lonkar (Georgia Institute of Technology); Chunyang Wang (Nanjing University); Kuan Yang (Shanghai Jiao Tong University); Yitong Yin (Nanjing University)

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

Fast, robust approximate message passing
Misha Ivkov, Tselil Schramm (Stanford)

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

Primes via Zeros: interactive proofs for testing primality of natural classes of ideals
Abhibhav Garg, Rafael Oliveira (University of Waterloo); Nitin Saxena (Department of Computer Science & Engg., Indian Institute of Technology Kanpur)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
Egor Gorbachev (Saarland University and Max Planck Institute for Informatics); Tomasz Kociumaka (INSAIT, Sofia University "St. Kliment Ohridski")

Single-copy stabilizer testing
Marcel Hinsche (Freie Universität Berlin and IBM Quantum Zurich); Jonas Helsen (Centrum Wiskunde & Informatica (CWI) and QuSoft, Amsterdam)

Constant Degree Networks for Almost-Everywhere Reliable Transmission
Mitali Bafna, Dor Minzer (MIT)

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

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

Smoothed analysis for graph isomorphism
Benjamin Moore, Michael Anastos, Matthew Kwan (Institute of Science and Technology Austria)

Provably learning a multi-head attention layer
Sitan Chen (Harvard University); Yuanzhi Li (Microsoft Research)

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

Fully Dynamic k-Median with Near-Optimal Update Time and Recourse
Sayan Bhattacharya, Martin Costa, Ermiya Farokhnejad (University of Warwick)

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)
Lijie Chen (Miller Institute for Basic Research in Science, UC Berkeley); Ron Rothblum (Technion); Roei Tell (University of Toronto)

Breaking the T^2/3 Barrier for Sequential Calibration
Yuval Dagan (Tel Aviv University); Constantinos Daskalakis (EECS, MIT); Maxwell Fishelson, Noah Golowich (MIT); Robert Kleinberg, Princewill Okoroafor (Cornell University)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao (Tsinghua University); Xiao Mao (Stanford University); Xinkai Shu (Max Planck Institute for Informatics); Longhui Yin (Tsinghua University)

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

Solving the Correlation Cluster LP in Nearly Linear Time
Nairen Cao (New York University); Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (Nanjing University); David Rasmussen Lolck (University of Copenhagen); Alantha Newman (Université Grenoble Alpes); Mikkel Thorup (University of Copenhagen); Lukas Vogl (Ecole Polytechnique Federale de Lausanne); Shuyi Yan (University of Copenhagen); Hanwen Zhang (University of Copenhagen, Denmark)

Optimal Proof Systems for Complex Sets are Hard to Find
Fabian Egidy, Christian Glaßer (Julius-Maximilians-Universität Würzburg)

SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
Ilias Diakonikolas (UW Madison); Sam Hopkins (MIT); Ankit Pensia (Simons Institute, UC Berkeley); Stefan Tiegel (ETH Zürich)

Disjoint connected dominating sets in pseudorandom graphs
Nemanja Draganic (University of Oxford); Michael Krivelevich (Tel Aviv University)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
Julia Chuzhoy, Ohad Trabelsi (Toyota Technological Institute at Chicago)

Good binary quantum codes with transversal CCZ gate
Quynh T Nguyen (Harvard University)

Hypercontractivity on HDX II: Symmetrization and q-Norms
Max Hopkins (Princeton University)

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

On the Computational Power of QAC⁰ with Barely Superlinear Ancillae
Anurag Anshu (Harvard University); Yangjing Dong, Fengning Ou, Penghui Yao (Nanjing University)

Parallel Repetition for 3-Player XOR Games
Amey Bhangale (UC Riverside); Mark Braverman (Princeton University); Subhash Khot (NYU); Yang Liu (IAS and CMU); Dor Minzer (MIT)

Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation
Sitan Chen, Weiyuan Gong (Harvard University); Qi Ye, Zhihan Zhang (Tsinghua University)

Subexponential Parameterized Algorithms for Hitting Subgraphs
Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (School of Computing, University of Leeds); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai); Meirav Zehavi (Ben-Gurion University)

Adaptive and oblivious statistical adversaries are equivalent
Guy Blanc, Gregory Valiant (Stanford University)

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

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

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

Quasi-Linear Size PCPs with Small Soundness from HDX
Mitali Bafna, Dor Minzer (MIT); Nikhil Vyas (Harvard); Zhiwei Yun (MIT)

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

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

Protecting Computations Against Continuous Bounded-Communication Leakage
Yuval Ishai (Technion); Yifan Song (IIIS, Tsinghua University and Shanghai Qi Zhi Institute)

Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation
Zongbo Bao (CWI & QuSoft); Philippe van Dordrecht (University of Amsterdam); Jonas Helsen (CWI & QuSoft)

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

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
Yuda Feng (Nanjing University); Yang Hu (Tsinghua University); Shi Li (Nanjing University); Ruilong Zhang (Technical University of Munich)

Quantum One-Time Programs, Revisited
Aparna Gupte, Jiahui Liu (MIT); Justin Raizes (CMU); Bhaskar Roberts (UC Berkeley); Vinod Vaikuntanathan (MIT)

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

List-Decoding Capacity Implies Capacity on the q-ary Symmetric Channel
Francisco Pernice (MIT); Oscar Sprumont (University of Washington); Mary Wootters (Stanford University)

Learning the closest product state
Ainesh Bakshi (MIT); John Bostanci (Columbia University); William Kretschmer (Simons Institute); Zeph Landau (UC Berkeley); Jerry Li (University of Washington); Allen Liu (MIT); Ryan O'Donnell (Carnegie Mellon University); Ewin Tang (UC Berkeley)

Linear Hashing Is Good
Michael Jaber, Vinayak M. Kumar, David Zuckerman (UT Austin)

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

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

Online Locality Meets Distributed Quantum Computing
Amirreza Akbari (Aalto University); Xavier Coiteux-Roy (School of Computation, Information and Technology, Technical University of Munich & Munich Center for Quantum Science and Technology, Munich, Germany); Francesco d'Amore (Bocconi University & BIDSA); François Le Gall (Nagoya University); Henrik Lievonen (Aalto University); Darya Melnyk (TU Berlin); Augusto Modanese (Aalto University); Shreyas Pai (IIT Madras); Marc-Olivier Renou (Inria, Universitée Paris-Saclay, CPHT, Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau); Václav Rozhoň (INSAIT); Jukka Suomela (Aalto University)

Redundancy is All You Need
Joshua Brakensiek, Venkatesan Guruswami (University of California, Berkeley)

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

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

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

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

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

Sample-Optimal Private Regression in Polynomial Time
Prashanti Anderson, Ainesh Bakshi, Mahbod Majid (MIT); Stefan Tiegel (ETH Zürich)

Better Approximation for Weighted k-Matroid Intersection
Neta Singer, Theophile Thiery (EPFL)

Model Stealing for Any Low-Rank Language Model
Allen Liu, Ankur Moitra (MIT)

Computing moment polytopes of tensors with applications in algebraic complexity and quantum information
Maxim van den Berg (University of Amsterdam and Ruhr-Universität Bochum); Matthias Christandl (University of Copenhagen); Vladimir Lysikov (Ruhr-Universität Bochum); Harold Nieuwboer (University of Copenhagen); Michael Walter (Ruhr-Universität Bochum); Jeroen Zuiddam (University of Amsterdam)

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

Omnipredicting Single-Index Models with Multi-Index Models
Lunjia Hu (Stanford University); Kevin Tian (UT Austin); Chutong Yang (UNIVERSITY OF TEXAS AT AUSTIN)

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

Simulating Time With Square-Root Space
Ryan Williams (MIT)

Uncloneable quantum states are necessary as proofs and advice
Rohit Chatterjee (National University of Singapore); Srijita Kundu (University of Waterloo); Supartha Podder (Stony Brook University)

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

Improved bounds for testing low stabilizer complexity states
Saeed Mehraban (Tufts University); Mehrdad Tahmasbi (UIUC)

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

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

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

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

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

Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates
Louis Golowich, Venkatesan Guruswami (UC Berkeley)

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

Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses
Brice Huang, Sidhanth Mohanty, Amit Rajaraman (MIT); David X Wu (UC Berkeley)

A bound on the quantum value of all compiled nonlocal games
Alexander Kulpe (Ruhr University Bochum); Giulio Malavolta (Bocconi University); Connor Paddock (U Ottawa); Simon Schmidt, Michael Walter (Ruhr University Bochum)

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

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

All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud (Weizmann Institute of Science and INSAIT); Nick Fischer (INSAIT); Ce Jin (MIT); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Zoe Xi (MIT)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Jun-Ting Hsieh (Carnegie Mellon University); Ting-Chun Lin (UCSD); Sidhanth Mohanty (MIT); Ryan O'Donnell (Carnegie Mellon University); Rachel Yun Zhang (MIT)

Faster Rates for No-Regret Learning in General Games via Cautious Optimism
Ashkan Soleymani (MIT); Georgios Piliouras (Google DeepMind); Gabriele Farina (MIT)

Locally Sampleable Uniform Symmetric Distributions
Daniel M. Kane, Anthony Ostuni (UC San Diego); Kewen Wu (UC Berkeley)

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

Oblivious Defense in ML Models: Backdoor Removal without Detection
Shafi Goldwasser (UC Berkeley and MIT); Jonathan Shafer, Neekon Vafa, Vinod Vaikuntanathan (MIT)

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

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

Pauli measurements are not optimal for single-copy tomography
Jayadev Acharya, Abhilash Dharmavarapu (Cornell University); Yuhan Liu (Rice University); Nengkun Yu (Stony Brook University)

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

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

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

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

Dimension Independent and Computationally Efficient Shadow Tomography
Pulkit Sinha (Institute for Quantum Computing, School of Computer Science, University of Waterloo)

How to Construct Random Unitaries
Fermi Ma (Simons Institute, UC Berkeley); Hsin-Yuan Huang (Google, Caltech)

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

A sharp version of Talagrand's selector process conjecture and an application to rounding fractional covers
Huy Tuan Pham (Institute for Advanced Study)

Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity
Mitali Bafna (MIT); Karthik C. S. (Rutgers University); Dor Minzer (MIT)

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

Merge-width and First-Order Model Checking
Jan Dreier (TU Wien); Szymon Torunczyk (University of Warsaw)

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

Minimum degree edge-disjoint Hamilton cycles in random directed graphs
Asaf Ferber (University of California, Irvine); Adva Mond (King's College London)

DNF Learning via Locally Mixing Random Walks
Josh Alman (Columbia University); Shivam Nadimpalli (MIT); Shyamal Patel, Rocco A. Servedio (Columbia University)

Symmetric Perceptrons, Number Partitioning and Lattices
Neekon Vafa, Vinod Vaikuntanathan (MIT)

Classical Commitments to Quantum States
Sam Gunn (Berkeley); Yael Kalai, Anand Natarajan, Agi Villanyi (MIT)

Vizing's Theorem in Near-Linear Time
Sepehr Assadi (University of Waterloo); Soheil Behnezhad (Northeastern University); Sayan Bhattacharya, Martin Costa (University of Warwick); Shay Solomon (Tel Aviv University); Tianyi Zhang (ETH Zurich)

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

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

Efficient thermalization and universal quantum computing with quantum Gibbs samplers
Cambyse Rouze (INRIA Saclay, IPP); Alvaro Alhambra (Instituto de Física Teórica - CSIC); Daniel Stilck França (University of Copenhagen)

Vanishing of Schubert Coefficients
Igor Pak, Colleen Robichaux (UCLA)

Fully dynamic biconnectivity in Õ(log² n) time
Jacob Holm (University of Copenhagen); Wojciech Nadara (Technical University of Denmark and University of Warsaw); Eva Rotenberg (Technical University of Denmark); Marek Sokołowski (Max Planck Institute for Informatics)

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

Leakage-resilient extractors against number-on-forehead protocols
Eshan Chattopadhyay (Cornell University); Jesse Goodman (UT Austin)

The Jacobi Factoring Circuit: Quantum Factoring in Near-Linear Gates and Sublinear Space
Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan (MIT); Katherine Van Kirk (Harvard)

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

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

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

Polynomial-time tolerant testing stabilizer states
Srinivasan Arunachalam, Arkopal Dutt (IBM Quantum)

Optimal Static Dictionary with Worst-Case Constant Query Time
Yang Hu (Tsinghua University); Jingxun Liang (CMU); Huacheng Yu (Princeton University); Junkai Zhang (Tsinghua University); Renfei Zhou (CMU)

Stochastic Matching via In-n-Out Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari (Northeastern University); Ronitt Rubinfeld (MIT)

Statistical inference of a ranked community in a directed graph
Dmitriy Kunisky (Johns Hopkins University); Daniel A. Spielman (Yale University); Alexander S. Wein (University of California, Davis); Xifan Yu (Yale University)

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

On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
Joshua Grochow (University of Colorado Boulder); Youming Qiao ( University of Technology Sydney)

History-Independent Concurrent Hash Tables
Hagit Attiya (Technion); Michael Bender (Stony Brook University); Martin Farach-Colton (New York University); Rotem Oshman (Tel-Aviv University); Noa Schiller (Tel Aviv University)

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev (Massachusetts Institute of Technology); Guy Bresler (MIT); Stefan Tiegel (ETH Zürich); Vinod Vaikuntanathan (MIT CSAIL)

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

On the complexity of isomorphism problems for tensors, groups, and polynomials V: over commutative rings
Joshua Grochow (University of Colorado Boulder); Youming Qiao (University of Technology Sydney); Katherine E. Stange (University of Colorado Boulder); Xiaorui Sun (University of Illinois Chicago)

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

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

Testing and learning structured quantum Hamiltonians
Srinivasan Arunachalam, Arkopal Dutt (IBM); Francisco (CWI Amsterdam)

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

On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM
Dominik Kempa (Stony Brook University, USA); Tomasz Kociumaka (INSAIT, Sofia University “St. Kliment Ohridski”)

Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs
Elchanan Mossel (MIT); Allan Sly (Princeton); Youngtak Sohn (Brown)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
Ilias Diakonikolas (UW Madison); Sam Hopkins (MIT); Ankit Pensia (Simons Institute, UC Berkeley); Stefan Tiegel (ETH Zürich)

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

Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Xin Lyu (UC berkeley); Kunal Talwar (Apple)

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

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

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

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

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

How Random CSPs Fool Hierarchies: II
Siu On Chan, Hiu Tsun Ng

Explicit Codes approaching Generalized Singleton Bound using Expanders
Fernando Granha Jeronimo (UIUC); Tushant Mittal (Stanford University); Shashank Srivastava (DIMACS and IAS); Madhur Tulsiani (Toyota Technological Institute at Chicago, USA)

When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism
Dean Doron (Ben Gurion University); Edward Pyne (MIT); Roei Tell (University of Toronto); Ryan Williams (MIT)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Chaitanya Nalam, Thatchaphol Saranurak (University of Michigan); Sorrachai Yingchareonthawornchai (The Hebrew University of Jerusalem and ETH Zurich)

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

Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy k-XOR Over Expanders
Riddhi Ghosal (UCLA); Isaac M Hair (UCSB); Aayush Jain (CMU); Amit Sahai (UCLA)

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

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

Ideal Pseudorandom Codes
Omar Alrabiah (University of California, Berkeley); Prabhanjan Ananth (University of California, Santa Barbara); Miranda Christ (Columbia University); Yevgeniy Dodis (NYU); Sam Gunn (UC Berkeley)

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

Learning quantum states prepared by shallow circuits in polynomial time
Zeph Landau (UC Berkeley); Yunchao Liu (Harvard University)

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

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

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate k-clique counts faster
Keren Censor-Hillel, Tomer Even (Technion); Virginia Vassilevska Williams (Massachusetts Institute of Technology)

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

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad (KTH Royal Institute of Technology & CWI Amsterdam); Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Sagnik Mukhopadhyay (University of Birmingham); Sorrachai Yingchareonthawornchai (The Hebrew University of Jerusalem and ETH Zurich)

Adaptive Approximation Schemes for Matching Queues
Alireza Amanihamedani (London Business School); Ali Aouad (Massachusetts Institute of Technology); Amin Saberi (Stanford University)

Quantum fault tolerance with constant-space and logarithmic-time overheads
Quynh T Nguyen (Harvard University); Christopher A Pattison (California Institute of Technology)

Quantum advantage from soft decoders
Andre Chailloux (INRIA); Jean-Pierre Tillich (Inria)

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

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