STOC 2025 – Author Index

A B C D E F G H I J K L M N O P Q R S T V W X Y Z

	Abboud, Amir	STOC '25: "All-Pairs Shortest Paths with ..." 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; INSAIT, Israel; INSAIT, Bulgaria; Massachusetts Institute of Technology, USA) Article Search
	Abram, Damiano	STOC '25: "Succinct Oblivious Tensor ..." 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) Article Search
	Acharya, Jayadev	STOC '25: "Pauli Measurements Are Not ..." 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) Article Search
	Akbari, Amirreza	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search
	Alekseev, Yaroslav	STOC '25: "Lifting to Bounded-Depth and ..." 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) Article Search
	Alhambra, Alvaro	STOC '25: "Efficient Thermalization and ..." Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers Cambyse Rouze, Alvaro Alhambra, and Daniel Stilck França (Inria, France; IPP, France; Instituto de Física Teórica, Spain; CSIC, Spain; University of Copenhagen, Denmark) Article Search
	Allman, Maxwell	STOC '25: "From Signaling to Interviews ..." 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) Article Search
	Alman, Josh	STOC '25: "DNF Learning via Locally Mixing ..." 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) Article Search STOC '25: "Low Rank Matrix Rigidity: ..." Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification Josh Alman and Jingxun Liang (Columbia University, USA; Carnegie Mellon University, USA) Article Search
	Alrabiah, Omar	STOC '25: "Ideal Pseudorandom Codes ..." 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) Article Search
	Amanihamedani, Alireza	STOC '25: "Adaptive Approximation Schemes ..." 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) Article Search
	Ameli, Afrouz Jabal	STOC '25: "A 5/4-Approximation for Two-Edge ..." 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) Article Search
	An, Shinwoo	STOC '25: "Approximation Algorithms for ..." Approximation Algorithms for the Geometric Multimatching Problem Shinwoo An, Eunjin Oh, and Jie Xue (POSTECH, South Korea; New York University Shanghai, China) Article Search
	Anagnostides, Ioannis	STOC '25: "Computational Lower Bounds ..." 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) Article Search
	Ananth, Prabhanjan	STOC '25: "Ideal Pseudorandom Codes ..." 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) Article Search
	Anastos, Michael	STOC '25: "Smoothed Analysis for Graph ..." Smoothed Analysis for Graph Isomorphism Benjamin Moore, Michael Anastos, and Matthew Kwan (IST Austria, Austria) There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “na'ive refinement”, “na'ive vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph. Article Search
	Anderson, Prashanti	STOC '25: "Sample-Optimal Private Regression ..." Sample-Optimal Private Regression in Polynomial Time Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel (Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland) Article Search
	Andoni, Alexandr	STOC '25: "A Framework for Building Data ..." A Framework for Building Data Structures from Communication Protocols Alexandr Andoni, Shunhua Jiang, and Omri Weinstein (Columbia University, USA; Hebrew University of Jerusalem, Israel) Article Search
	Andrews, Robert	STOC '25: "Polynomial-Time PIT from (Almost) ..." Polynomial-Time PIT from (Almost) Necessary Assumptions Robert Andrews, Deepanshu Kush, and Roei Tell (University of Waterloo, Canada; University of Toronto, Canada) Article Search
	Anshu, Anurag	STOC '25: "On the Computational Power ..." 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) Article Search
	Aouad, Ali	STOC '25: "Adaptive Approximation Schemes ..." 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) Article Search
	Applebaum, Benny	STOC '25: "The Meta-complexity of Secret ..." The Meta-complexity of Secret Sharing Benny Applebaum and Oded Nir (Tel Aviv University, Israel) A secret-sharing scheme allows the distribution of a secret s among n parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about s. The collection of authorized/unauthorized sets is defined by a monotone function f: {0,1}n → {0,1}. It is known that any monotone function can be realized by a secret-sharing scheme; thus, the smallest achievable total share size, S(f), serves as a natural complexity measure. In this paper, we initiate the study of the following meta-complexity question: Given a monotone function f, is it possible to efficiently distinguish between cases where the secret-sharing complexity of f is small versus large? We examine this question across several computational models, yielding the following main results. (Hardness for formulas and circuits): Given a monotone formula f of size L, it is coNP-hard to distinguish between “cheap” functions, where the maximum share size is 1 bit and the total share size is O(L0.01), and “expensive” functions, where the maximum share size is Ω(√L) and the total share size is Ω(L/logL). This latter bound nearly matches known secret-sharing constructions yielding a total share size of L bits. For monotone circuits, we strengthen the bound on the expensive case to a maximum share size of Ω(L/logL) and a total share size of Ω(L2/logL). These results rule out the existence of instance-optimal compilers that map a formula f to a secret-sharing scheme with complexity polynomially related to S(f). (Hardness for truth tables): Under cryptographic assumptions, either (1) every n-bit slice function can be realized by a poly(n)-size secret-sharing scheme, or (2) given a truth-table representation of f of size N = 2n, it is computationally infeasible to distinguish in time poly(N) between cases where S(f) = poly(n) and S(f) = nω(1). Option (1) would be considered a breakthrough result, as the best-known construction for slices has a sub-exponential complexity of 2Õ(√n) (Liu, Vaikuntanathan, and Wee; Eurocrypt 2018). Our proof introduces a new worst-case-to-average-case reduction for slices, which may be of independent interest. (Hardness for graphs): We examine the simple case where f is given as a 2-DNF, represented by a graph G whose edges correspond to 2-terms, and ask whether it is possible to distinguish between cases where the share size is constant and those where the share size is large, say Ω(logn). We establish several connections between this question and questions in communication complexity. For instance, we show that graphs admitting constant-cost secret sharing form a subclass of graphs with constant randomized communication complexity and constant-size adjacency sketches (Harms, Wild, and Zamaraev; STOC 2022). We leverage these connections to establish new lower bounds for specific graph families, derive a combinatorial characterization of graphs with constant-size linear secret-sharing schemes, and show that a natural class of myopic algorithms fails to distinguish cheap graphs from expensive ones. Article Search
	Arunachalam, Srinivasan	STOC '25: "Polynomial-Time Tolerant Testing ..." Polynomial-Time Tolerant Testing Stabilizer States Srinivasan Arunachalam and Arkopal Dutt (IBM Quantum, n.n.) Article Search STOC '25: "Testing and Learning Structured ..." Testing and Learning Structured Quantum Hamiltonians Srinivasan Arunachalam, Arkopal Dutt, and Francisco Escudero Gutierrez (IBM, n.n.; CWI, Netherlands) Article Search
	Ashlagi, Itai	STOC '25: "From Signaling to Interviews ..." 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) Article Search
	Assadi, Sepehr	STOC '25: "Correlation Clustering and ..." 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) Article Search STOC '25: "Vizing’s Theorem in Near-Linear ..." Vizing’s Theorem in Near-Linear Time Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, and Tianyi Zhang (University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland) Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem. Preprint Video STOC '25: "Covering Approximate Shortest ..." Covering Approximate Shortest Paths with DAGs Sepehr Assadi, Gary Hoppenworth, and Nicole Wein (University of Waterloo, Canada; University of Michigan, USA) Article Search
	Atserias, Albert	STOC '25: "Feasibly Constructive Proof ..." 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) Article Search
	Attiya, Hagit	STOC '25: "History-Independent Concurrent ..." History-Independent Concurrent Hash Tables Hagit Attiya, Michael A. Bender, Martin Farach-Colton, Rotem Oshman, and Noa Schiller (Technion, Israel; Stony Brook University, USA; New York University, USA; Tel Aviv University, Israel) Article Search
	Avvakumov, Sergey	STOC '25: "Hardness of 4-Colouring 𝐺-Colourable ..." 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) Article Search
	Azarmehr, Amir	STOC '25: "Stochastic Matching via In-n-Out ..." 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) Article Search
	Babaioff, Moshe	STOC '25: "Share-Based Fairness for Arbitrary ..." Share-Based Fairness for Arbitrary Entitlements Moshe Babaioff and Uriel Feige (Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel) Article Search
	Bafna, Mitali	STOC '25: "Quasi-Linear Size PCPs with ..." 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) Article Search STOC '25: "Near Optimal Constant Inapproximability ..." 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) Article Search STOC '25: "Rounding Large Independent ..." 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; Institute for Advanced Study at Princeton, USA) We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has its second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost 3-colorable or are promised to contain an independent set of size (1/2−є)n. Our second result above can be refined to require only a weaker vertex expansion property with an efficient certificate. In a surprising contrast to our algorithmic result, we observe that the analogous task of finding a linear-sized independent set in almost 4-colorable one-sided expanders (even when the second eigenvalue is on(1)) is NP-hard, assuming the Unique Games Conjecture. All prior algorithms that beat the worst-case guarantees for this problem rely on bottom eigenspace enumeration techniques (following the classical spectral methods of Alon and Kahale) and require two-sided expansion, meaning a bounded number of negative eigenvalues of magnitude Ω(1). Such techniques naturally extend to almost k-colorable graphs for any constant k, in contrast to analogous guarantees on one-sided expanders, which are Unique Games-hard to achieve for k ≥ 4. Our rounding scheme builds on the method of simulating multiple samples from a pseudo-distribution introduced in Bafna et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs - every large independent set has a larger-than-expected intersection with some member of a small list - and its formalization in the low-degree sum-of-squares proof system. Preprint STOC '25: "Constant Degree Networks for ..." Constant Degree Networks for Almost-Everywhere Reliable Transmission Mitali Bafna and Dor Minzer (Massachusetts Institute of Technology, USA) Article Search
	Bakshi, Ainesh	STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search STOC '25: "Sample-Optimal Private Regression ..." Sample-Optimal Private Regression in Polynomial Time Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel (Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland) Article Search
	Ball, Marshall	STOC '25: "Extractors for Samplable Distributions ..." 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) Article Search
	Balliu, Alkida	STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Bandeira, Afonso S.	STOC '25: "Tensor Concentration Inequalities: ..." 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) Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓp injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p=2 [39,45,59]. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes. Article Search STOC '25: "Matrix Chaos Inequalities ..." 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) Article Search
	Bangachev, Kiril	STOC '25: "Near-Optimal Time-Sparsity ..." 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) Article Search STOC '25: "Sandwiching Random Geometric ..." 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) Article Search
	Bao, Zongbo	STOC '25: "Tolerant Testing of Stabilizer ..." 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) Article Search
	Batziou, Eleni	STOC '25: "Monotone Contractions ..." Monotone Contractions Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani (University of Liverpool, UK; University of Illinois at Urbana-Champaign, USA) Article Search
	Behnezhad, Soheil	STOC '25: "Vizing’s Theorem in Near-Linear ..." Vizing’s Theorem in Near-Linear Time Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, and Tianyi Zhang (University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland) Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem. Preprint Video STOC '25: "Stochastic Matching via In-n-Out ..." 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) Article Search
	Bender, Michael A.	STOC '25: "Optimal Non-oblivious Open ..." Optimal Non-oblivious Open Addressing Michael A. Bender, William Kuszmaul, and Renfei Zhou (Stony Brook University, USA; Carnegie Mellon University, USA) Article Search STOC '25: "History-Independent Concurrent ..." History-Independent Concurrent Hash Tables Hagit Attiya, Michael A. Bender, Martin Farach-Colton, Rotem Oshman, and Noa Schiller (Technion, Israel; Stony Brook University, USA; New York University, USA; Tel Aviv University, Israel) Article Search
	Bérczi, Kristóf	STOC '25: "Matroid Products via Submodular ..." 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) Article Search
	Bernstein, Aaron	STOC '25: "Deterministic Dynamic Maximal ..." 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) Article Search
	Bhangale, Amey	STOC '25: "Parallel Repetition for 3-Player ..." 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; Institute for Advanced Study at Princeton, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search STOC '25: "Approximation Algorithms for ..." Approximation Algorithms for Satisfiable CSPs via a Mixed Invariance Principle Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) Article Search
	Bhattacharya, Sayan	STOC '25: "Vizing’s Theorem in Near-Linear ..." Vizing’s Theorem in Near-Linear Time Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, and Tianyi Zhang (University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland) Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem. Preprint Video STOC '25: "Deterministic Dynamic Maximal ..." 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) Article Search STOC '25: "Fully Dynamic 𝑘-Median ..." Fully Dynamic 𝑘-Median with Near-Optimal Update Time and Recourse Sayan Bhattacharya, Martin Costa, and Ermiya Farokhnejad (University of Warwick, UK) In metric k-clustering, we are given as input a set of n points in a general metric space, and we have to pick k centers and cluster the input points around these chosen centers, so as to minimize an appropriate objective function. In recent years, significant effort has been devoted to the study of metric k-clustering problems in a dynamic setting, where the input keeps changing via updates (point insertions/deletions), and we have to maintain a good clustering throughout these updates [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21; Bateni, Esfandiari, Fichtenberger, Henzinger, Jayaram, Mirrokni and Weise, SODA’23; Lacki, Haeupler, Grunau, Rozhon and Jayaram, SODA’24; Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24; Forster and Skarlatos, SODA’25]. The performance of such a dynamic algorithm is measured in terms of three parameters: (i) Approximation ratio, which signifies the quality of the maintained solution, (ii) Recourse, which signifies how stable the maintained solution is, and (iii) Update time, which signifies the efficiency of the algorithm. We consider a textbook metric k-clustering problem, metric k-median, where the objective is the sum of the distances of the points to their nearest centers. We design the first dynamic algorithm for this problem with near-optimal guarantees across all three performance measures (up to a constant factor in approximation ratio, and polylogarithmic factors in recourse and update time). Specifically, we obtain a O(1)-approximation algorithm for dynamic metric k-median with Õ(1) recourse and Õ(k) update time. Prior to our work, the state-of-the-art here was the recent result of [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], who obtained O(є−1)-approximation ratio with Õ(kє) recourse and Õ(k1+є) update time. We achieve our results by carefully synthesizing the concept of robust centers introduced in [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21] along with the randomized local search subroutine from [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], in addition to several key technical insights of our own. Preprint
	Bizière, Clotilde	STOC '25: "Reachability in One-Dimensional ..." 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) Article Search
	Blanc, Guy	STOC '25: "Adaptive and Oblivious Statistical ..." Adaptive and Oblivious Statistical Adversaries Are Equivalent Guy Blanc and Gregory Valiant (Stanford University, USA) Article Search
	Blanchard, Moïse	STOC '25: "Agnostic Smoothed Online Learning ..." Agnostic Smoothed Online Learning Moïse Blanchard (Columbia University, USA) Article Search
	Blikstad, Joakim	STOC '25: "Global vs. s-t Vertex Connectivity ..." Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, and Sorrachai Yingchareonthawornchai (KTH Royal Institute of Technology, Sweden; CWI, Netherlands; MPI-INF, Germany; Saarland University, Germany; University of Birmingham, UK; Hebrew University of Jerusalem, Israel; ETH Zurich, Switzerland) Article Search
	Boneh, Itai	STOC '25: "Õptimal Fault-Tolerant Labeling ..." Õ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) Article Search
	Bonnet, Édouard	STOC '25: "Treewidth Inapproximability ..." Treewidth Inapproximability and Tight ETH Lower Bound Édouard Bonnet (CNRS - ENS Lyon - LIP, France) Article Search
	Bostanci, John	STOC '25: "A General Quantum Duality ..." 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) Article Search STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search
	Bouland, Adam	STOC '25: "The State Hidden Subgroup ..." The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement Adam Bouland, Tudor Giurgica-Tiron, and John Wright (Stanford University, USA; University of California at Berkeley, USA) Article Search
	Bourreau, Yann	STOC '25: "Faster Distributed 𝛥-Coloring ..." Faster Distributed 𝛥-Coloring via Ruling Subgraphs Yann Bourreau, Sebastian Brandt, and Alexandre Nolin (CISPA Helmholtz Center for Information Security, Germany) Article Search
	Brakensiek, Joshua	STOC '25: "Redundancy Is All You Need ..." Redundancy Is All You Need Joshua Brakensiek and Venkatesan Guruswami (University of California at Berkeley, USA) The seminal work of Benczúr and Karger demonstrated cut sparsifiers of near-linear size, with several applications throughout theoretical computer science. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linear codes over Abelian groups. A decade ago, Kogan and Krauthgamer asked about the sparsifiability of arbitrary constraint satisfaction problems (CSPs). For this question, a trivial lower bound is the size of a non-redundant CSP instance, which admits, for each constraint, an assignment satisfying only that constraint (so that no constraint can be dropped by the sparsifier). For instance, for graph cuts, spanning trees are non-redundant instances. Our main result is that redundant clauses are sufficient for sparsification: for any CSP predicate R, every unweighted instance of (R) has a sparsifier of size at most its non-redundancy (up to polylog factors). For weighted instances, we similarly pin down the sparsifiability to the so-called chain length of the predicate. These results precisely determine the extent to which any CSP can be sparsified. A key technical ingredient in our work is a novel application of the entropy method from Gilmer’s recent breakthrough on the union-closed sets conjecture. As an immediate consequence of our main theorem, a number of results in the non-redundancy literature immediately extend to CSP sparsification. We also contribute new techniques for understanding the non-redundancy of CSP predicates. In particular, we give an explicit family of predicates whose non-redundancy roughly corresponds to the structure of matching vector families in coding theory. By adapting methods from the matching vector codes literature, we are able to construct an explicit predicate whose non-redundancy lies between Ω(n1.5) and Oє(n1.6), the first example with a provably non-integral exponent. Article Search
	Brandt, Sebastian	STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search STOC '25: "Faster Distributed 𝛥-Coloring ..." Faster Distributed 𝛥-Coloring via Ruling Subgraphs Yann Bourreau, Sebastian Brandt, and Alexandre Nolin (CISPA Helmholtz Center for Information Security, Germany) Article Search
	Braverman, Mark	STOC '25: "Parallel Repetition for 3-Player ..." 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; Institute for Advanced Study at Princeton, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search STOC '25: "Optimality of Frequency Moment ..." Optimality of Frequency Moment Estimation Mark Braverman and Or Zamir (Princeton University, USA; Tel Aviv University, Israel) Estimating the second frequency moment of a stream up to (1±ε) multiplicative error requires at most O(logn / ε2) bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least Ω(logn + 1/ε2) space is needed. We prove a tight lower bound of Ω(log(n ε2 ) / ε2) for all ε = Ω(1/√n). Note that when ε>n−1/2 + c, where c>0, our lower bound matches the classic upper bound of AMS. For smaller values of ε we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound. Our lower bound holds also for the more general problem of p-th frequency moment estimation for the range of p∈ (1,2], giving a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments. Article Search
	Bresler, Guy	STOC '25: "Near-Optimal Time-Sparsity ..." 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) Article Search STOC '25: "Sandwiching Random Geometric ..." 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) Article Search
	Bringmann, Karl	STOC '25: "A Fine-Grained Classification ..." A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends Karl Bringmann and Egor Gorbachev (Saarland University, Germany; MPI-INF, Germany) Article Search
	Buchbinder, Niv	STOC '25: "Extending the Extension: Deterministic ..." Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization Niv Buchbinder and Moran Feldman (Tel Aviv University, Israel; University of Haifa, Israel) Maximization of submodular functions under various constraints is a fundamental problem that has been extensively studied. A powerful technique that has emerged and has been shown to be extremely effective for such problems is the following. First, a continuous relaxation of the problem is obtained by relaxing the (discrete) set of feasible solutions to a convex body, and extending the discrete submodular function f to a continuous function F known as the multilinear extension. Then, two algorithmic steps are implemented. The first step approximately solves the relaxation by finding a fractional solution within the convex body that approximately maximizes F; and the second step rounds this fractional solution to a feasible integral solution. While this “fractionally solve and then round” approach has been a key technique for resolving many questions in the field, the main drawback of algorithms based on it is that evaluating the multilinear extension may require a number of value oracle queries to f that is exponential in the size of f’s ground set. The only known way to tackle this issue is to approximate F via sampling, which makes all algorithms based on this approach inherently randomized and quite slow. In this work, we introduce a new tool, that we refer to as the extended multilinear extension, designed to derandomize submodular maximization algorithms that are based on the successful “solve fractionally and then round” approach. We demonstrate the effectiveness of this new tool on the fundamental problem of maximizing a submodular function subject to a matroid constraint, and show that it allows for a deterministic implementation of both the fractionally solving step and the rounding step of the above approach. As a bonus, we also get a randomized algorithm for the problem with an improved query complexity. Article Search
	Calvo, Miguel Bosch	STOC '25: "A 5/4-Approximation for Two-Edge ..." 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) Article Search
	Cao, Nairen	STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Carmosino, Marco	STOC '25: "Student-Teacher Constructive ..." Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap Stefan Grosser and Marco Carmosino (McGill University, Canada; IBM Research, USA) Article Search
	Cen, Ruoxu	STOC '25: "Network Unreliability in Almost-Linear ..." Network Unreliability in Almost-Linear Time Debmalya Panigrahi, Ruoxu Cen, and Jason Li (Duke University, USA; Carnegie Mellon University, USA) Article Search
	Censor-Hillel, Keren	STOC '25: "Output-Sensitive Approximate ..." 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) Article Search
	Chailloux, Andre	STOC '25: "Quantum Advantage from Soft ..." Quantum Advantage from Soft Decoders Andre Chailloux and Jean-Pierre Tillich (Inria, France) Article Search
	Chakrabarty, Deeparnab	STOC '25: "Monotonicity Testing of High-Dimensional ..." 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) Article Search
	Chakraborty, Sourav	STOC '25: "Testing vs Estimation for ..." 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) Article Search
	Chan, Siu On	STOC '25: "How Random CSPs Fool Hierarchies: ..." How Random CSPs Fool Hierarchies: II Siu On Chan and Hiu Tsun Ng (Unaffiliated, Hong Kong) Article Search
	Chandrasekaran, Gautam	STOC '25: "Learning the Sherrington-Kirkpatrick ..." Learning the Sherrington-Kirkpatrick Model Even at Low Temperature Gautam Chandrasekaran and Adam R. Klivans (University of Texas at Austin, USA) Article Search
	Chang, Alan	STOC '25: "Optimal Rounding for Sparsest ..." Optimal Rounding for Sparsest Cut Alan Chang, Assaf Naor, and Kevin Ren (Washington University in St. Louis, USA; Princeton University, USA) We prove that the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n≥ 2 is Θ(√logn). We achieve this by establishing the following geometric/structural result. If (M,d) is an n-point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x,y∈ M with d(x,y)≥ τ, the probability that both x∈ Z and d(y,Z)≥ βτ/√1+log(|B(y,κ β τ)|/|B(y,β τ)|) is Ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora–Rao–Vazirani rounding technique. Article Search
	Chang, Hsien-Chih	STOC '25: "Light Tree Covers, Routing, ..." 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) Article Search
	Charikar, Moses	STOC '25: "Six Candidates Suffice to ..." 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) Article Search
	Chatterjee, Abhranil	STOC '25: "Characterizing and Testing ..." Characterizing and Testing Principal Minor Equivalence of Matrices Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj (Indian Statistical Institute, Kolkata, India; Chennai Mathematical Institute, India; IIT Bombay, India) Article Search
	Chatterjee, Rohit	STOC '25: "Uncloneable Quantum States ..." 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) Article Search
	Chattopadhyay, Eshan	STOC '25: "Leakage-Resilient Extractors ..." Leakage-Resilient Extractors against Number-on-Forehead Protocols Eshan Chattopadhyay and Jesse Goodman (Cornell University, USA; University of Texas at Austin, USA) Article Search
	Chechik, Shiri	STOC '25: "Õptimal Fault-Tolerant Labeling ..." Õ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) Article Search
	Chen, Jielun	STOC '25: "Positive Bias Makes Tensor-Network ..." 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) Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d≳ n, a small positive mean value ≳ 1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #-, like for the zero-mean case. The mean value 1/d matches the phase transition point observed in previous work. Our proof makes use of Barvinok’s method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least -. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is -. This result compares to Arad and Landau’s result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is -. Our work thus identifies new parameter regimes in terms of the positivity of the tensor entries in which tensor networks can be (nearly) efficiently contracted. Preprint
	Chen, Li	STOC '25: "Accelerated Optimization of ..." Accelerated Optimization of Approximate Multi-commodity Flows on Directed Graphs Li Chen, Andrei Graur, and Aaron Sidford (Independent, USA; Stanford University, USA) Article Search
	Chen, Lijie	STOC '25: "Maximum Circuit Lower Bounds ..." 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) Article Search STOC '25: "Fiat-Shamir in the Plain Model ..." 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) Article Search
	Chen, Lin	STOC '25: "Long Arithmetic Progressions ..." Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses Lin Chen, Yuchen Mao, and Guochuan Zhang (Zhejiang University, China) Article Search
	Chen, Liyan	STOC '25: "Unambiguous SNARGs for P from ..." 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) Article Search STOC '25: "Succinct Non-interactive Arguments ..." Succinct Non-interactive Arguments of Proximity Liyan Chen, Zhengzhong Jin, and Daniel Wichs (Tsinghua University, China; Northeastern University, USA; NTT Research, USA) Article Search
	Chen, Sitan	STOC '25: "Stabilizer Bootstrapping: ..." 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) Article Search STOC '25: "Provably Learning a Multi-head ..." Provably Learning a Multi-head Attention Layer Sitan Chen and Yuanzhi Li (Harvard University, USA; Microsoft Research, n.n.) Article Search
	Chen, Xi	STOC '25: "Monotonicity Testing of High-Dimensional ..." 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) Article Search
	Chen, Xiaoyu	STOC '25: "Rapid Mixing at the Uniqueness ..." Rapid Mixing at the Uniqueness Threshold Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang (Nanjing University, China; Georgia Institute of Technology, USA) Article Search
	Chen, Yeyuan	STOC '25: "Explicit Folded Reed-Solomon ..." 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) Article Search
	Chen, Zongchen	STOC '25: "Rapid Mixing at the Uniqueness ..." Rapid Mixing at the Uniqueness Threshold Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang (Nanjing University, China; Georgia Institute of Technology, USA) Article Search STOC '25: "Counting random 𝑘-SAT near ..." 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) Article Search
	Cheng, Siu-Wing	STOC '25: "Constant Approximation of ..." 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, China; Renmin University of China, China) Article Search
	Chornomaz, Bogdan	STOC '25: "On Reductions and Representations ..." On Reductions and Representations of Learning Problems in Euclidean Spaces Bogdan Chornomaz, Shay Moran, and Tom Waknine (Technion, Israel) Article Search
	Christ, Miranda	STOC '25: "Ideal Pseudorandom Codes ..." 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) Article Search
	Christandl, Matthias	STOC '25: "Computing Moment Polytopes ..." 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 (University of Amsterdam, Netherlands; Ruhr University Bochum, Germany; University of Copenhagen, Denmark) Article Search STOC '25: "Asymptotic Tensor Rank Is ..." Asymptotic Tensor Rank Is Characterized by Polynomials Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Peter Vrana, and Jeroen Zuiddam (University of Copenhagen, Denmark; University of Amsterdam, Netherlands; Budapest University of Technology and Economics, Hungary) Article Search
	Chuzhoy, Julia	STOC '25: "Breaking the 𝑂(𝑚𝑛)-Time ..." Breaking the 𝑂(𝑚𝑛)-Time Barrier for Vertex-Weighted Global Minimum Cut Julia Chuzhoy and Ohad Trabelsi (Toyota Technological Institute at Chicago, USA) Article Search
	Cohen-Addad, Vincent	STOC '25: "A (2+ε)-Approximation Algorithm ..." 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) Article Search STOC '25: "Almost Optimal PAC Learning ..." Almost Optimal PAC Learning for 𝑘-Means Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn (Google Research, France; Google, USA; Aarhus University, Denmark) Article Search STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Coiteux-Roy, Xavier	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Collina, Natalie	STOC '25: "Tractable Agreement Protocols ..." Tractable Agreement Protocols Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth (University of Pennsylvania, USA) Article Search
	Conroy, Jonathan	STOC '25: "How to Protect Yourself from ..." 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) Article Search STOC '25: "Light Tree Covers, Routing, ..." 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) Article Search
	Cook, James	STOC '25: "The Structure of Catalytic ..." The Structure of Catalytic Space: Capturing Randomness and Time via Compression James Cook, Jiatu Li, Ian Mertz, and Edward Pyne (University of Toronto, Canada; Massachusetts Institute of Technology, USA; University of Warwick, UK) In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexity-theoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open. We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows. 1: We unconditionally derandomize catalytic logspace: CBPL = CL. 2: We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in CL ∩ P can be solved in polynomial time-bounded CL. 3: We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytime-bounded, zero-error randomized CL. Our results center around the compress–or–random framework. For the second result, we introduce a simple yet novel compress–or–compute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress–or–compress–or–random algorithm that combines runtime compression with a second compress–or–random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction. Article Search
	Cook, Joshua	STOC '25: "Time and Space Efficient Deterministic ..." Time and Space Efficient Deterministic Decoders Joshua Cook and Dana Moshkovitz (University of Texas at Austin, USA) Article Search
	Costa, Martin	STOC '25: "Vizing’s Theorem in Near-Linear ..." Vizing’s Theorem in Near-Linear Time Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, and Tianyi Zhang (University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland) Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem. Preprint Video STOC '25: "Fully Dynamic 𝑘-Median ..." Fully Dynamic 𝑘-Median with Near-Optimal Update Time and Recourse Sayan Bhattacharya, Martin Costa, and Ermiya Farokhnejad (University of Warwick, UK) In metric k-clustering, we are given as input a set of n points in a general metric space, and we have to pick k centers and cluster the input points around these chosen centers, so as to minimize an appropriate objective function. In recent years, significant effort has been devoted to the study of metric k-clustering problems in a dynamic setting, where the input keeps changing via updates (point insertions/deletions), and we have to maintain a good clustering throughout these updates [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21; Bateni, Esfandiari, Fichtenberger, Henzinger, Jayaram, Mirrokni and Weise, SODA’23; Lacki, Haeupler, Grunau, Rozhon and Jayaram, SODA’24; Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24; Forster and Skarlatos, SODA’25]. The performance of such a dynamic algorithm is measured in terms of three parameters: (i) Approximation ratio, which signifies the quality of the maintained solution, (ii) Recourse, which signifies how stable the maintained solution is, and (iii) Update time, which signifies the efficiency of the algorithm. We consider a textbook metric k-clustering problem, metric k-median, where the objective is the sum of the distances of the points to their nearest centers. We design the first dynamic algorithm for this problem with near-optimal guarantees across all three performance measures (up to a constant factor in approximation ratio, and polylogarithmic factors in recourse and update time). Specifically, we obtain a O(1)-approximation algorithm for dynamic metric k-median with Õ(1) recourse and Õ(k) update time. Prior to our work, the state-of-the-art here was the recent result of [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], who obtained O(є−1)-approximation ratio with Õ(kє) recourse and Õ(k1+є) update time. We achieve our results by carefully synthesizing the concept of robust centers introduced in [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21] along with the randomized local search subroutine from [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], in addition to several key technical insights of our own. Preprint
	Czerwiński, Wojciech	STOC '25: "Reachability in One-Dimensional ..." 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) Article Search
	Dagan, Yuval	STOC '25: "Breaking the T2/3 ..." Breaking the T2/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) Article Search
	Dai, Samuel	STOC '25: "Locality vs Quantum Codes ..." Locality vs Quantum Codes Samuel Dai and Ray Li (Northeastern University, USA; Santa Clara University, USA) Article Search
	D'Amore, Francesco	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Daskalakis, Constantinos	STOC '25: "Efficient Learning and Computation ..." 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) Article Search STOC '25: "Breaking the T2/3 ..." Breaking the T2/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) Article Search
	Davies-Peck, Peter	STOC '25: "On the Locality of the Lovász ..." On the Locality of the Lovász Local Lemma Peter Davies-Peck (Durham University, UK) The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of n ‘bad events’, each occurring with probability at most p and dependent on a set of underlying random variables, can be avoided. It is a central tool of the probabilistic method, since it can be used to show that combinatorial objects satisfying some desirable properties must exist. While the original proof was existential, subsequent work has shown algorithms for the Lovász Local Lemma: that is, in circumstances in which the lemma proves the existence of some object, these algorithms can constructively find such an object. One main strand of these algorithms, which began with Moser and Tardos’s well-known result (JACM 2010), involves iteratively resampling the dependent variables of satisfied bad events until none remain satisfied. In this paper, we present a novel analysis that can be applied to resampling-style Lovász Local Lemma algorithms. This analysis shows that an output assignment for the dependent variables of most events can be determined only from O(loglog1/p n)-radius local neighborhoods, and that the events whose variables may still require resampling can be identified from these neighborhoods. This allows us to improve randomized complexities for the constructive Lovász Local Lemma (with polynomial criterion) in several parallel and distributed models. In particular, we obtain: A LOCAL algorithm with O(loglog1/p n) node-averaged complexity (while matching the O(log1/p n) worst-case complexity of Chung, Pettie, and Su). An algorithm for the LCA and VOLUME models requiring dO(loglog1/p n) probes per query. An O(logloglog1/p n)-round algorithm for CONGESTED CLIQUE, linear space MPC, and Heterogenous MPC. Article Search
	De Rezende, Susanna F.	STOC '25: "Truly Supercritical Trade-Offs ..." 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) Article Search
	Dharmavarapu, Abhilash	STOC '25: "Pauli Measurements Are Not ..." 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) Article Search
	Diakonikolas, Ilias	STOC '25: "SoS Certificates for Sparse ..." SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More Ilias Diakonikolas, Sam 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) Article Search STOC '25: "Entangled Mean Estimation ..." 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) Article Search STOC '25: "SoS Certifiability of Subgaussian ..." SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications Ilias Diakonikolas, Sam 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) Article Search
	Ding, Youlong	STOC '25: "A New Approach for LPN-Based ..." 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) Article Search
	Dodis, Yevgeniy	STOC '25: "Ideal Pseudorandom Codes ..." 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) Article Search
	Dong, Yangjing	STOC '25: "On the Computational Power ..." 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) Article Search
	Doron, Dean	STOC '25: "When Connectivity Is Hard, ..." When Connectivity Is Hard, Random Walks Are Easy with Non-determinism Dean Doron, Edward Pyne, Roei Tell, and Ryan Williams (Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada) Two fundamental problems on directed graphs are to decide s-t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s-t connectivity running in polynomial time and no(1) space, and no known algorithm for estimating the n-step random walk matrix running in non-deterministic logspace. We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms A1 and A2 such that for every graph G, either: A1(G) outputs the transitive closure of G in polynomial time and polylogarithmic space. A2(G) outputs an approximation of the n-step random walk matrix of G in non-deterministic logspace. As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch’s theorem can be non-trivially sped up, or randomized space can be almost completely derandomized. We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron–Pyne–Tell STOC 2024, Li–Pyne–Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron–Tell CCC 2024). To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel–Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen–Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting. Article Search
	Draganic, Nemanja	STOC '25: "Disjoint Connected Dominating ..." Disjoint Connected Dominating Sets in Pseudorandom Graphs Nemanja Draganic and Michael Krivelevich (University of Oxford, UK; Tel Aviv University, Israel) Article Search
	Dreier, Jan	STOC '25: "Merge-Width and First-Order ..." Merge-Width and First-Order Model Checking Jan Dreier and Szymon Toruńczyk (TU Wien, Austria; University of Warsaw, Poland) Article Search
	Duan, Ran	STOC '25: "Breaking the Sorting Barrier ..." 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) Article Search
	Duetting, Paul	STOC '25: "The Cost of Consistency: Submodular ..." The Cost of Consistency: Submodular Maximization with Constant Recourse Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam (Google, Switzerland; Sapienza University of Rome, Italy; Google, USA; EPFL, Switzerland) Article Search
	Dutt, Arkopal	STOC '25: "Polynomial-Time Tolerant Testing ..." Polynomial-Time Tolerant Testing Stabilizer States Srinivasan Arunachalam and Arkopal Dutt (IBM Quantum, n.n.) Article Search STOC '25: "Testing and Learning Structured ..." Testing and Learning Structured Quantum Hamiltonians Srinivasan Arunachalam, Arkopal Dutt, and Francisco Escudero Gutierrez (IBM, n.n.; CWI, Netherlands) Article Search
	Ebrahimnejad, Farzam	STOC '25: "On Approximability of the ..." 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) We study the complexity of approximating the permanent of a positive semidefinite matrix A∈ ℂn× n. 1. We design a new approximation algorithm for per(A) with approximation ratio e−(0.9999 + γ)n, exponentially improving upon the current best bound of e−(1+γ−o(1))n (Anari-Gurvits-Oveis Gharan-Saberi 2017, Yuan-Parrilo 2022). Here, γ ≈ 0.577 is Euler’s constant. 2. We prove that it is NP-hard to approximate per(A) within a factor e−(γ−)n for any >0. This is the first exponential hardness of approximation for this problem. Along the way, we prove optimal hardness of approximation results for the ||·||2→ q “norm” problem of a matrix for all −1 < q < 2. Article Search
	Eden, Talya	STOC '25: "Approximately Counting and ..." 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) Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In the sublinear-time regime, the relaxed problem of approximate counting has been explored within two prominent query frameworks: the standard model, which permits degree, neighbor, and pair queries, and the strictly more powerful augmented model, which additionally allows for uniform edge sampling. Currently, in the standard model, (optimal) results have been established only for approximately counting edges, stars, and cliques, all of which have a radius of one. This contrasts sharply with the state of affairs in the augmented model, where algorithmic results (some of which are optimal) are known for any input motif, leading to a disparity which we term the “scope gap” between the two models. In this work, we make significant progress in bridging this gap. Our approach draws inspiration from recent advancements in the augmented model and utilizes a framework centered on counting by uniform sampling, thus allowing us to establish new results in the standard model and simplify on previous results. In particular, our first, and main, contribution is a new algorithm in the standard model for approximately counting any Hamiltonian motif in sublinear time, where the complexity of the algorithm is the sum of two terms. One term equals the complexity of the known algorithms by Assadi, Kapralov, and Khanna (ITCS 2019) and Fichtenberger and Peng (ICALP 2020) in the (strictly stronger) augmented model and the other is an additional, necessary, additive overhead. Our second contribution is a variant of our algorithm that enables nearly uniform sampling of these motifs, a capability previously limited in the standard model to edges and cliques. Our third contribution is to introduce even simpler algorithms for stars and cliques by exploiting their radius-one property. As a result, we simplify all previously known algorithms in the standard model for stars (Gonen, Ron, Shavitt (SODA 2010)), triangles (Eden, Levi, Ron Seshadhri (FOCS 2015)) and cliques (Eden, Ron, Seshadri (STOC 2018)). Article Search Info
	Egidy, Fabian	STOC '25: "Optimal Proof Systems for ..." Optimal Proof Systems for Complex Sets Are Hard to Find Fabian Egidy and Christian Glaßer (Julius-Maximilians-Universität Würzburg, Germany) Article Search
	Equi, Massimo	STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Even, Tomer	STOC '25: "Output-Sensitive Approximate ..." 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) Article Search
	Ezra, Tomer	STOC '25: "Multi-parameter Mechanisms ..." 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) We consider the problem of designing auctions that maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way that maximizes the total buyer utility. The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller’s objective is welfare maximization or revenue maximization . However, in the case of consumer surplus maximization the picture is less clear – using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms that maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with tight approximation guarantees against the total social welfare. Along the way, we resolve an open question posed by Hartline and Roughgarden ’08 for the two bidder single item setting. Article Search
	Fang, Yuting	STOC '25: "Constant-Cost Communication ..." Constant-Cost Communication Is Not Reducible to 𝑘-Hamming Distance Yuting Fang, Mika Göös, Nathaniel Harms, and Pooya Hatami (Ohio State University, USA; EPFL, Switzerland) Article Search
	Farach-Colton, Martin	STOC '25: "History-Independent Concurrent ..." History-Independent Concurrent Hash Tables Hagit Attiya, Michael A. Bender, Martin Farach-Colton, Rotem Oshman, and Noa Schiller (Technion, Israel; Stony Brook University, USA; New York University, USA; Tel Aviv University, Israel) Article Search
	Farina, Gabriele	STOC '25: "Faster Rates for No-Regret ..." 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, USA) Article Search STOC '25: "Efficient Learning and Computation ..." 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) Article Search
	Farokhnejad, Ermiya	STOC '25: "Fully Dynamic 𝑘-Median ..." Fully Dynamic 𝑘-Median with Near-Optimal Update Time and Recourse Sayan Bhattacharya, Martin Costa, and Ermiya Farokhnejad (University of Warwick, UK) In metric k-clustering, we are given as input a set of n points in a general metric space, and we have to pick k centers and cluster the input points around these chosen centers, so as to minimize an appropriate objective function. In recent years, significant effort has been devoted to the study of metric k-clustering problems in a dynamic setting, where the input keeps changing via updates (point insertions/deletions), and we have to maintain a good clustering throughout these updates [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21; Bateni, Esfandiari, Fichtenberger, Henzinger, Jayaram, Mirrokni and Weise, SODA’23; Lacki, Haeupler, Grunau, Rozhon and Jayaram, SODA’24; Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24; Forster and Skarlatos, SODA’25]. The performance of such a dynamic algorithm is measured in terms of three parameters: (i) Approximation ratio, which signifies the quality of the maintained solution, (ii) Recourse, which signifies how stable the maintained solution is, and (iii) Update time, which signifies the efficiency of the algorithm. We consider a textbook metric k-clustering problem, metric k-median, where the objective is the sum of the distances of the points to their nearest centers. We design the first dynamic algorithm for this problem with near-optimal guarantees across all three performance measures (up to a constant factor in approximation ratio, and polylogarithmic factors in recourse and update time). Specifically, we obtain a O(1)-approximation algorithm for dynamic metric k-median with Õ(1) recourse and Õ(k) update time. Prior to our work, the state-of-the-art here was the recent result of [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], who obtained O(є−1)-approximation ratio with Õ(kє) recourse and Õ(k1+є) update time. We achieve our results by carefully synthesizing the concept of robust centers introduced in [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21] along with the randomized local search subroutine from [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], in addition to several key technical insights of our own. Preprint
	Fearnley, John	STOC '25: "Monotone Contractions ..." Monotone Contractions Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani (University of Liverpool, UK; University of Illinois at Urbana-Champaign, USA) Article Search
	Feige, Uriel	STOC '25: "Share-Based Fairness for Arbitrary ..." Share-Based Fairness for Arbitrary Entitlements Moshe Babaioff and Uriel Feige (Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel) Article Search
	Feldman, Moran	STOC '25: "Extending the Extension: Deterministic ..." Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization Niv Buchbinder and Moran Feldman (Tel Aviv University, Israel; University of Haifa, Israel) Maximization of submodular functions under various constraints is a fundamental problem that has been extensively studied. A powerful technique that has emerged and has been shown to be extremely effective for such problems is the following. First, a continuous relaxation of the problem is obtained by relaxing the (discrete) set of feasible solutions to a convex body, and extending the discrete submodular function f to a continuous function F known as the multilinear extension. Then, two algorithmic steps are implemented. The first step approximately solves the relaxation by finding a fractional solution within the convex body that approximately maximizes F; and the second step rounds this fractional solution to a feasible integral solution. While this “fractionally solve and then round” approach has been a key technique for resolving many questions in the field, the main drawback of algorithms based on it is that evaluating the multilinear extension may require a number of value oracle queries to f that is exponential in the size of f’s ground set. The only known way to tackle this issue is to approximate F via sampling, which makes all algorithms based on this approach inherently randomized and quite slow. In this work, we introduce a new tool, that we refer to as the extended multilinear extension, designed to derandomize submodular maximization algorithms that are based on the successful “solve fractionally and then round” approach. We demonstrate the effectiveness of this new tool on the fundamental problem of maximizing a submodular function subject to a matroid constraint, and show that it allows for a deterministic implementation of both the fractionally solving step and the rounding step of the above approach. As a bonus, we also get a randomized algorithm for the problem with an improved query complexity. Article Search
	Feng, Yuda	STOC '25: "Constant Approximation for ..." 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) Article Search
	Ferber, Asaf	STOC '25: "Minimum Degree Edge-Disjoint ..." 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) Article Search
	Filakovský, Marek	STOC '25: "Hardness of 4-Colouring 𝐺-Colourable ..." 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) Article Search
	Filtser, Arnold	STOC '25: "How to Protect Yourself from ..." 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) Article Search
	Fischer, Eldar	STOC '25: "Testing vs Estimation for ..." 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) Article Search
	Fischer, Nick	STOC '25: "All-Pairs Shortest Paths with ..." 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; INSAIT, Israel; INSAIT, Bulgaria; Massachusetts Institute of Technology, USA) Article Search
	Fishelson, Maxwell	STOC '25: "Efficient Learning and Computation ..." 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) Article Search STOC '25: "Breaking the T2/3 ..." Breaking the T2/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) Article Search
	Fleming, Noah	STOC '25: "Truly Supercritical Trade-Offs ..." 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) Article Search
	França, Daniel Stilck	STOC '25: "Efficient Thermalization and ..." Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers Cambyse Rouze, Alvaro Alhambra, and Daniel Stilck França (Inria, France; IPP, France; Instituto de Física Teórica, Spain; CSIC, Spain; University of Copenhagen, Denmark) Article Search
	Freitag, Cody	STOC '25: "Unambiguous SNARGs for P from ..." 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) Article Search
	Fusco, Federico	STOC '25: "The Cost of Consistency: Submodular ..." The Cost of Consistency: Submodular Maximization with Constant Recourse Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam (Google, Switzerland; Sapienza University of Rome, Italy; Google, USA; EPFL, Switzerland) Article Search
	Gaitonde, Jason	STOC '25: "Bypassing the Noisy Parity ..." 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) Article Search
	Garg, Abhibhav	STOC '25: "Primes via Zeros: Interactive ..." 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) Article Search
	Garg, Jugal	STOC '25: "Constant-Factor EFX Exists ..." Constant-Factor EFX Exists for Chores Jugal Garg, Aniket Murhekar, and John Qin (University of Illinois at Urbana-Champaign, USA) Article Search
	Garg, Mohit	STOC '25: "A 5/4-Approximation for Two-Edge ..." 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) Article Search
	Gehér, Boglárka	STOC '25: "Matroid Products via Submodular ..." 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) Article Search
	Ghafari, Alma	STOC '25: "Stochastic Matching via In-n-Out ..." 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) Article Search
	Gharan, Shayan Oveis	STOC '25: "On Approximability of the ..." 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) We study the complexity of approximating the permanent of a positive semidefinite matrix A∈ ℂn× n. 1. We design a new approximation algorithm for per(A) with approximation ratio e−(0.9999 + γ)n, exponentially improving upon the current best bound of e−(1+γ−o(1))n (Anari-Gurvits-Oveis Gharan-Saberi 2017, Yuan-Parrilo 2022). Here, γ ≈ 0.577 is Euler’s constant. 2. We prove that it is NP-hard to approximate per(A) within a factor e−(γ−)n for any >0. This is the first exponential hardness of approximation for this problem. Along the way, we prove optimal hardness of approximation results for the ||·||2→ q “norm” problem of a matrix for all −1 < q < 2. Article Search
	Ghasemi, Fatemeh	STOC '25: "Improved PIR Schemes using ..." Improved PIR Schemes using Matching Vectors and Derivatives Fatemeh Ghasemi, Swastik Kopparty, and Madhu Sudan (University of Toronto, Canada; Harvard University, USA) Article Search
	Ghosal, Riddhi	STOC '25: "Using the Planted Clique Conjecture ..." Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-XOR 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) Article Search
	Ghosh, Arijit	STOC '25: "Testing vs Estimation for ..." 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) Article Search
	Ghosh, Sumanta	STOC '25: "Characterizing and Testing ..." Characterizing and Testing Principal Minor Equivalence of Matrices Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj (Indian Statistical Institute, Kolkata, India; Chennai Mathematical Institute, India; IIT Bombay, India) Article Search
	Ghuge, Rohan	STOC '25: "Single-Sample and Robust Online ..." Single-Sample and Robust Online Resource Allocation Rohan Ghuge, Sahil Singla, and Yifan Wang (Georgia Institute of Technology, USA) Article Search
	Giurgica-Tiron, Tudor	STOC '25: "The State Hidden Subgroup ..." The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement Adam Bouland, Tudor Giurgica-Tiron, and John Wright (Stanford University, USA; University of California at Berkeley, USA) Article Search
	Glaßer, Christian	STOC '25: "Optimal Proof Systems for ..." Optimal Proof Systems for Complex Sets Are Hard to Find Fabian Egidy and Christian Glaßer (Julius-Maximilians-Universität Würzburg, Germany) Article Search
	Goel, Ashish	STOC '25: "Metric Distortion of Small-Group ..." Metric Distortion of Small-Group Deliberation Ashish Goel, Mohak Goyal, and Kamesh Munagala (Stanford University, USA; Duke University, USA) We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most k, and these outcomes are aggregated by a social choice rule to find the winning alternative. We ground these models in the metric distortion framework, where the voters and alternatives are embedded in a latent metric space, with closer alternative being more desirable for a voter. We posit that the outcome of a small-group interaction optimally uses the voters’ collective knowledge of the metric, either deterministically or probabilistically. We characterize the distortion of our deliberation models for small k, showing that groups of size k=3 suffice to drive the distortion bound below the deterministic metric distortion lower bound of 3, and groups of size 4 suffice to break the randomized lower bound of 2.11. We also show nearly tight asymptotic distortion bounds in the group size, showing that for any constant є > 0, achieving a distortion of 1+є needs group size that only depends on 1/є, and not the number of alternatives. We obtain these results via formulating a basic optimization problem in small deviations of the sum of i.i.d. random variables, which we solve to global optimality via non-convex optimization. The resulting bounds may be of independent interest in probability theory. Article Search
	Goel, Surbhi	STOC '25: "Tractable Agreement Protocols ..." Tractable Agreement Protocols Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth (University of Pennsylvania, USA) Article Search
	Golan, Shay	STOC '25: "Õptimal Fault-Tolerant Labeling ..." Õ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) Article Search
	Goldwasser, Shafi	STOC '25: "Oblivious Defense in ML Models: ..." 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) Article Search
	Golowich, Louis	STOC '25: "Asymptotically Good Quantum ..." Asymptotically Good Quantum Codes with Transversal Non-clifford Gates Louis Golowich and Venkatesan Guruswami (University of California at Berkeley, USA) Article Search STOC '25: "Quantum LDPC Codes with Transversal ..." 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) Article Search
	Golowich, Noah	STOC '25: "Breaking the T2/3 ..." Breaking the T2/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) Article Search
	Gong, Weiyuan	STOC '25: "Stabilizer Bootstrapping: ..." 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) Article Search
	Goodman, Jesse	STOC '25: "Leakage-Resilient Extractors ..." Leakage-Resilient Extractors against Number-on-Forehead Protocols Eshan Chattopadhyay and Jesse Goodman (Cornell University, USA; University of Texas at Austin, USA) Article Search
	Göös, Mika	STOC '25: "Supercritical Tradeoffs for ..." Supercritical Tradeoffs for Monotone Circuits Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov (EPFL, Switzerland) Article Search STOC '25: "Constant-Cost Communication ..." Constant-Cost Communication Is Not Reducible to 𝑘-Hamming Distance Yuting Fang, Mika Göös, Nathaniel Harms, and Pooya Hatami (Ohio State University, USA; EPFL, Switzerland) Article Search STOC '25: "Quantum Communication Advantage ..." Quantum Communication Advantage in TFNP Siddhartha Jain, Mika Göös, Tom Gur, and Jiawei Li (University of Texas at Austin, USA; EPFL, Switzerland; University of Cambridge, UK) Article Search
	Gopi, Sivakanth	STOC '25: "Tensor Concentration Inequalities: ..." 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) Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓp injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p=2 [39,45,59]. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes. Article Search
	Gorbachev, Egor	STOC '25: "A Fine-Grained Classification ..." A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends Karl Bringmann and Egor Gorbachev (Saarland University, Germany; MPI-INF, Germany) Article Search STOC '25: "Bounded Edit Distance: Optimal ..." Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights Egor Gorbachev and Tomasz Kociumaka (Saarland University, Germany; MPI-INF, Germany; IMPI-INF, Germany) Article Search
	Gordon, Spencer	STOC '25: "Monotone Contractions ..." Monotone Contractions Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani (University of Liverpool, UK; University of Illinois at Urbana-Champaign, USA) Article Search
	Goyal, Mohak	STOC '25: "Metric Distortion of Small-Group ..." Metric Distortion of Small-Group Deliberation Ashish Goel, Mohak Goyal, and Kamesh Munagala (Stanford University, USA; Duke University, USA) We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most k, and these outcomes are aggregated by a social choice rule to find the winning alternative. We ground these models in the metric distortion framework, where the voters and alternatives are embedded in a latent metric space, with closer alternative being more desirable for a voter. We posit that the outcome of a small-group interaction optimally uses the voters’ collective knowledge of the metric, either deterministically or probabilistically. We characterize the distortion of our deliberation models for small k, showing that groups of size k=3 suffice to drive the distortion bound below the deterministic metric distortion lower bound of 3, and groups of size 4 suffice to break the randomized lower bound of 2.11. We also show nearly tight asymptotic distortion bounds in the group size, showing that for any constant є > 0, achieving a distortion of 1+є needs group size that only depends on 1/є, and not the number of alternatives. We obtain these results via formulating a basic optimization problem in small deviations of the sum of i.i.d. random variables, which we solve to global optimality via non-convex optimization. The resulting bounds may be of independent interest in probability theory. Article Search
	Grandoni, Fabrizio	STOC '25: "A 5/4-Approximation for Two-Edge ..." 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) Article Search STOC '25: "A (2+ε)-Approximation Algorithm ..." 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) Article Search
	Graur, Andrei	STOC '25: "Accelerated Optimization of ..." Accelerated Optimization of Approximate Multi-commodity Flows on Directed Graphs Li Chen, Andrei Graur, and Aaron Sidford (Independent, USA; Stanford University, USA) Article Search
	Gravin, Nikolai	STOC '25: "Approximation Guarantees of ..." Approximation Guarantees of Median Mechanism in ℝᵈ Nikolai Gravin and Jianhao Jia (Shanghai University of Finance and Economics, China) Article Search
	Gribelyuk, Elena	STOC '25: "Lifting Linear Sketches: Optimal ..." 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) Article Search
	Grochow, Joshua	STOC '25: "On the Complexity of Isomorphism ..." On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications Joshua Grochow and Youming Qiao (University of Colorado Boulder, USA; University of Technology Sydney, Australia) Article Search STOC '25: "On the Complexity of Isomorphism ..." On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings Joshua 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) Article Search
	Grosser, Stefan	STOC '25: "Student-Teacher Constructive ..." Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap Stefan Grosser and Marco Carmosino (McGill University, Canada; IBM Research, USA) Article Search
	Gunn, Sam	STOC '25: "Classical Commitments to Quantum ..." Classical Commitments to Quantum States Sam Gunn, Yael Kalai, Anand Natarajan, and Agi Villanyi (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search STOC '25: "Ideal Pseudorandom Codes ..." 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) Article Search
	Gupta, Anupam	STOC '25: "Tight Results for Online Convex ..." Tight Results for Online Convex Paging Anupam Gupta, Amit Kumar, and Debmalya Panigrahi (New York University, USA; IIT Delhi, India; Duke University, USA) Article Search
	Gupta, Varun	STOC '25: "Tractable Agreement Protocols ..." Tractable Agreement Protocols Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth (University of Pennsylvania, USA) Article Search
	Gupte, Aparna	STOC '25: "Quantum One-Time Programs, ..." Quantum One-Time Programs, Revisited Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, and Vinod Vaikuntanathan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; University of California at Berkeley, USA) Article Search
	Gur, Tom	STOC '25: "A Zero-Knowledge PCP Theorem ..." A Zero-Knowledge PCP Theorem Tom Gur, Jack O'Connor, and Nicholas Spooner (University of Cambridge, UK; Cornell University, USA) Article Search STOC '25: "Quantum Communication Advantage ..." Quantum Communication Advantage in TFNP Siddhartha Jain, Mika Göös, Tom Gur, and Jiawei Li (University of Texas at Austin, USA; EPFL, Switzerland; University of Cambridge, UK) Article Search
	Gurjar, Rohit	STOC '25: "Characterizing and Testing ..." Characterizing and Testing Principal Minor Equivalence of Matrices Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj (Indian Statistical Institute, Kolkata, India; Chennai Mathematical Institute, India; IIT Bombay, India) Article Search
	Guruswami, Venkatesan	STOC '25: "Redundancy Is All You Need ..." Redundancy Is All You Need Joshua Brakensiek and Venkatesan Guruswami (University of California at Berkeley, USA) The seminal work of Benczúr and Karger demonstrated cut sparsifiers of near-linear size, with several applications throughout theoretical computer science. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linear codes over Abelian groups. A decade ago, Kogan and Krauthgamer asked about the sparsifiability of arbitrary constraint satisfaction problems (CSPs). For this question, a trivial lower bound is the size of a non-redundant CSP instance, which admits, for each constraint, an assignment satisfying only that constraint (so that no constraint can be dropped by the sparsifier). For instance, for graph cuts, spanning trees are non-redundant instances. Our main result is that redundant clauses are sufficient for sparsification: for any CSP predicate R, every unweighted instance of (R) has a sparsifier of size at most its non-redundancy (up to polylog factors). For weighted instances, we similarly pin down the sparsifiability to the so-called chain length of the predicate. These results precisely determine the extent to which any CSP can be sparsified. A key technical ingredient in our work is a novel application of the entropy method from Gilmer’s recent breakthrough on the union-closed sets conjecture. As an immediate consequence of our main theorem, a number of results in the non-redundancy literature immediately extend to CSP sparsification. We also contribute new techniques for understanding the non-redundancy of CSP predicates. In particular, we give an explicit family of predicates whose non-redundancy roughly corresponds to the structure of matching vector families in coding theory. By adapting methods from the matching vector codes literature, we are able to construct an explicit predicate whose non-redundancy lies between Ω(n1.5) and Oє(n1.6), the first example with a provably non-integral exponent. Article Search STOC '25: "Asymptotically Good Quantum ..." Asymptotically Good Quantum Codes with Transversal Non-clifford Gates Louis Golowich and Venkatesan Guruswami (University of California at Berkeley, USA) Article Search STOC '25: "Almost Optimal Time Lower ..." 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) The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f:ℕ→ℕ, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1−o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1−o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing. Article Search
	Gutierrez, Francisco Escudero	STOC '25: "Testing and Learning Structured ..." Testing and Learning Structured Quantum Hamiltonians Srinivasan Arunachalam, Arkopal Dutt, and Francisco Escudero Gutierrez (IBM, n.n.; CWI, Netherlands) Article Search
	Hair, Isaac M.	STOC '25: "Using the Planted Clique Conjecture ..." Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-XOR 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) Article Search
	Hangleiter, Dominik	STOC '25: "Positive Bias Makes Tensor-Network ..." 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) Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d≳ n, a small positive mean value ≳ 1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #-, like for the zero-mean case. The mean value 1/d matches the phase transition point observed in previous work. Our proof makes use of Barvinok’s method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least -. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is -. This result compares to Arad and Landau’s result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is -. Our work thus identifies new parameter regimes in terms of the positivity of the tensor entries in which tensor networks can be (nearly) efficiently contracted. Preprint
	Harms, Nathaniel	STOC '25: "Constant-Cost Communication ..." Constant-Cost Communication Is Not Reducible to 𝑘-Hamming Distance Yuting Fang, Mika Göös, Nathaniel Harms, and Pooya Hatami (Ohio State University, USA; EPFL, Switzerland) Article Search STOC '25: "Testing Support Size More ..." Testing Support Size More Efficiently Than Learning Histograms Renato Ferreira Pinto Jr. and Nathaniel Harms (University of Waterloo, Canada; EPFL, Switzerland) Article Search
	Hatami, Pooya	STOC '25: "Constant-Cost Communication ..." Constant-Cost Communication Is Not Reducible to 𝑘-Hamming Distance Yuting Fang, Mika Göös, Nathaniel Harms, and Pooya Hatami (Ohio State University, USA; EPFL, Switzerland) Article Search
	Helsen, Jonas	STOC '25: "Tolerant Testing of Stabilizer ..." 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) Article Search STOC '25: "Single-Copy Stabilizer Testing ..." Single-Copy Stabilizer Testing Marcel Hinsche and Jonas Helsen (Freie Universität Berlin, Germany; IBM Quantum Zurich, Switzerland; CWI, Netherlands; QuSoft, Netherlands) Article Search
	Hinsche, Marcel	STOC '25: "Single-Copy Stabilizer Testing ..." Single-Copy Stabilizer Testing Marcel Hinsche and Jonas Helsen (Freie Universität Berlin, Germany; IBM Quantum Zurich, Switzerland; CWI, Netherlands; QuSoft, Netherlands) Article Search
	Hirahara, Shuichi	STOC '25: "Error-Correction of Matrix ..." Error-Correction of Matrix Multiplication Algorithms Shuichi Hirahara and Nobutaka Shimizu (National Institute of Informatics, Japan; Institute of Science Tokyo, Japan) Article Search
	Hoeberechts, Koen	STOC '25: "Asymptotic Tensor Rank Is ..." Asymptotic Tensor Rank Is Characterized by Polynomials Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Peter Vrana, and Jeroen Zuiddam (University of Copenhagen, Denmark; University of Amsterdam, Netherlands; Budapest University of Technology and Economics, Hungary) Article Search
	Holm, Jacob	STOC '25: "Fully Dynamic Biconnectivity ..." Fully Dynamic Biconnectivity in Õ(log² 𝑛) Time Jacob Holm, Wojciech Nadara, Eva Rotenberg, and Marek Sokołowski (University of Copenhagen, Denmark; DTU, Denmark; University of Warsaw, Poland; MPI-INF, Germany) Article Search
	Hommelsheim, Felix	STOC '25: "A 5/4-Approximation for Two-Edge ..." 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) Article Search
	Hopkins, Max	STOC '25: "Hypercontractivity on HDX ..." Hypercontractivity on HDX II: Symmetrization and 𝑞-Norms Max Hopkins (Princeton University, USA) Article Search
	Hopkins, Sam	STOC '25: "SoS Certificates for Sparse ..." SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More Ilias Diakonikolas, Sam 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) Article Search STOC '25: "SoS Certifiability of Subgaussian ..." SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications Ilias Diakonikolas, Sam 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) Article Search
	Hoppenworth, Gary	STOC '25: "Covering Approximate Shortest ..." Covering Approximate Shortest Paths with DAGs Sepehr Assadi, Gary Hoppenworth, and Nicole Wein (University of Waterloo, Canada; University of Michigan, USA) Article Search
	Hsieh, Jun-Ting	STOC '25: "Explicit Two-Sided Vertex ..." 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) Article Search STOC '25: "Rounding Large Independent ..." 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; Institute for Advanced Study at Princeton, USA) We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has its second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost 3-colorable or are promised to contain an independent set of size (1/2−є)n. Our second result above can be refined to require only a weaker vertex expansion property with an efficient certificate. In a surprising contrast to our algorithmic result, we observe that the analogous task of finding a linear-sized independent set in almost 4-colorable one-sided expanders (even when the second eigenvalue is on(1)) is NP-hard, assuming the Unique Games Conjecture. All prior algorithms that beat the worst-case guarantees for this problem rely on bottom eigenspace enumeration techniques (following the classical spectral methods of Alon and Kahale) and require two-sided expansion, meaning a bounded number of negative eigenvalues of magnitude Ω(1). Such techniques naturally extend to almost k-colorable graphs for any constant k, in contrast to analogous guarantees on one-sided expanders, which are Unique Games-hard to achieve for k ≥ 4. Our rounding scheme builds on the method of simulating multiple samples from a pseudo-distribution introduced in Bafna et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs - every large independent set has a larger-than-expected intersection with some member of a small list - and its formalization in the low-degree sum-of-squares proof system. Preprint
	Hu, Lunjia	STOC '25: "Omnipredicting Single-Index ..." Omnipredicting Single-Index Models with Multi-index Models Lunjia Hu, Kevin Tian, and Chutong Yang (Harvard University, USA; University of Texas at Austin, USA) Article Search
	Hu, Yang	STOC '25: "Constant Approximation for ..." 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) Article Search STOC '25: "Optimal Static Dictionary ..." 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) Article Search
	Huang, Brice	STOC '25: "Weak Poincaré Inequalities, ..." 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) Article Search
	Huang, Haoqiang	STOC '25: "Constant Approximation of ..." 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, China; Renmin University of China, China) Article Search
	Huang, Hsin-Yuan	STOC '25: "How to Construct Random Unitaries ..." 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) Article Search
	Huang, Lingxiao	STOC '25: "Near-Optimal Dimension Reduction ..." 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) Article Search
	Huang, Zengfeng	STOC '25: "Simple and Optimal Algorithms ..." 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) Article Search
	Imolay, András	STOC '25: "Matroid Products via Submodular ..." 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) Article Search
	Ishai, Yuval	STOC '25: "Protecting Computations against ..." 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) We consider the question of protecting a general computation device, modeled by a stateful Boolean circuit, against leakage of partial information about its internal wires. Goyal et al. (FOCS 2016) obtained a solution for the case of bounded-communication leakage, where the wires are partitioned into two parts and the leakage can be any function computed using t bits of communication between the parts. However, this solution suffers from two major limitations: (1) it only applies to a one-shot (stateless) computation, mapping an encoded input to an encoded output, and (2) the leakage-resilient circuit consumes fresh random bits, whose number scales linearly with the circuit complexity of the computed function. In this work, we eliminate the first limitation and make progress on the second. Concretely: - We present the first construction of stateful circuits that offer information-theoretic protection against continuous bounded-communication leakage. As an application, we extend a two-party “malware-resilient” protocol of Goyal et al. to the continuous-leakage case. - For simple types of bounded-communication leakage, which leak t parities or t disjunctions of circuit wires or their negations, we obtain a deterministic variant that does not require any fresh randomness beyond the randomness in the initial state. Here we get computational security based on a subexponentially secure one-way function. This is the first deterministic leakage-resilient circuit construction for any nontrivial class of global leakage. Article Search
	Itsykson, Dmitry	STOC '25: "Lifting to Bounded-Depth and ..." 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) Article Search
	Ivkov, Misha	STOC '25: "Fast, Robust Approximate Message ..." Fast, Robust Approximate Message Passing Misha Ivkov and Tselil Schramm (Stanford University, USA) Article Search
	Jaber, Michael	STOC '25: "Linear Hashing Is Good ..." Linear Hashing Is Good Michael Jaber, Vinayak M. Kumar, and David Zuckerman (University of Texas at Austin, USA) Article Search
	Jain, Aayush	STOC '25: "A New Approach for LPN-Based ..." 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) Article Search STOC '25: "Using the Planted Clique Conjecture ..." Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-XOR 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) Article Search
	Jain, Siddhartha	STOC '25: "Quantum Communication Advantage ..." Quantum Communication Advantage in TFNP Siddhartha Jain, Mika Göös, Tom Gur, and Jiawei Li (University of Texas at Austin, USA; EPFL, Switzerland; University of Cambridge, UK) Article Search
	Janett, Duri Andrea	STOC '25: "Truly Supercritical Trade-Offs ..." 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) Article Search
	Jeronimo, Fernando Granha	STOC '25: "Explicit Codes Approaching ..." 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; DIMACS, USA; Institute for Advanced Study at Princeton, USA; Toyota Technological Institute at Chicago, USA) Article Search
	Jia, Jianhao	STOC '25: "Approximation Guarantees of ..." Approximation Guarantees of Median Mechanism in ℝᵈ Nikolai Gravin and Jianhao Jia (Shanghai University of Finance and Economics, China) Article Search
	Jiang, Haotian	STOC '25: "Tensor Concentration Inequalities: ..." 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) Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓp injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p=2 [39,45,59]. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes. Article Search
	Jiang, Jiaqing	STOC '25: "Positive Bias Makes Tensor-Network ..." 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) Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d≳ n, a small positive mean value ≳ 1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #-, like for the zero-mean case. The mean value 1/d matches the phase transition point observed in previous work. Our proof makes use of Barvinok’s method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least -. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is -. This result compares to Arad and Landau’s result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is -. Our work thus identifies new parameter regimes in terms of the positivity of the tensor entries in which tensor networks can be (nearly) efficiently contracted. Preprint
	Jiang, Ruichen	STOC '25: "Improved Complexity for Smooth ..." Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods Ruichen Jiang, Aryan Mokhtari, and Francisco Patitucci Perez (University of Texas at Austin, USA) Article Search
	Jiang, Shaofeng H.-C.	STOC '25: "Near-Optimal Dimension Reduction ..." 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) Article Search
	Jiang, Shunhua	STOC '25: "A Framework for Building Data ..." A Framework for Building Data Structures from Communication Protocols Alexandr Andoni, Shunhua Jiang, and Omri Weinstein (Columbia University, USA; Hebrew University of Jerusalem, Israel) Article Search
	Jiang, Yonggang	STOC '25: "Deterministic Vertex Connectivity ..." 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) Article Search STOC '25: "Global vs. s-t Vertex Connectivity ..." Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, and Sorrachai Yingchareonthawornchai (KTH Royal Institute of Technology, Sweden; CWI, Netherlands; MPI-INF, Germany; Saarland University, Germany; University of Birmingham, UK; Hebrew University of Jerusalem, Israel; ETH Zurich, Switzerland) Article Search
	Jin, Ce	STOC '25: "All-Pairs Shortest Paths with ..." 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; INSAIT, Israel; INSAIT, Bulgaria; Massachusetts Institute of Technology, USA) Article Search
	Jin, Zhengzhong	STOC '25: "Universal SNARGs for NP from ..." Universal SNARGs for NP from Proofs of Completeness Zhengzhong Jin, Yael Kalai, Alex Lombardi, and Surya Mathialagan (Northeastern University, USA; Massachusetts Institute of Technology, USA; MSR, USA; Princeton University, USA) Article Search STOC '25: "Unambiguous SNARGs for P from ..." 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) Article Search STOC '25: "Succinct Non-interactive Arguments ..." Succinct Non-interactive Arguments of Proximity Liyan Chen, Zhengzhong Jin, and Daniel Wichs (Tsinghua University, China; Northeastern University, USA; NTT Research, USA) Article Search
	Joos, Felix	STOC '25: "The Hypergraph Removal Process ..." The Hypergraph Removal Process Felix Joos and Marcus Kühn (University of Heidelberg, Germany) Article Search
	Kahanamoku-Meyer, Gregory D.	STOC '25: "The Jacobi Factoring Circuit: ..." The Jacobi Factoring Circuit: Quantum Factoring in Near-Linear Gates and Sublinear Space Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk (Massachusetts Institute of Technology, USA; Harvard University, USA) Article Search
	Kalai, Yael	STOC '25: "Universal SNARGs for NP from ..." Universal SNARGs for NP from Proofs of Completeness Zhengzhong Jin, Yael Kalai, Alex Lombardi, and Surya Mathialagan (Northeastern University, USA; Massachusetts Institute of Technology, USA; MSR, USA; Princeton University, USA) Article Search STOC '25: "Classical Commitments to Quantum ..." Classical Commitments to Quantum States Sam Gunn, Yael Kalai, Anand Natarajan, and Agi Villanyi (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search
	Kalavasis, Alkis	STOC '25: "Computational Lower Bounds ..." 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) Article Search STOC '25: "On the Limits of Language ..." On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas (Yale University, USA) Article Search
	Kane, Daniel M.	STOC '25: "Locally Sampleable Uniform ..." 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) We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let f∶{0,1}m→{0,1}n be a Boolean function where each output bit of f depends only on O(1) input bits. Assume the output distribution of f on uniform input bits is close to a uniform distribution D with a symmetric support. We show that D is essentially one of the following six possibilities: (1) point distribution on 0n, (2) point distribution on 1n, (3) uniform over {0n,1n}, (4) uniform over strings with even Hamming weights, (5) uniform over strings with odd Hamming weights, and (6) uniform over all strings. This confirms a conjecture of Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). This is an extended abstract. The full paper can be found at https://arxiv.org/abs/2411.08183v1. An updated version with a stronger result can be found at https://arxiv.org/abs/2411.08183. Preprint STOC '25: "Entangled Mean Estimation ..." 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) Article Search
	Kaplan, Haim	STOC '25: "On Differentially Private ..." On Differentially Private Linear Algebra Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur (Tel Aviv University, Israel; Google Research, Israel; Google Research, n.n.; Technion, Israel) Article Search
	Kaufman, Tali	STOC '25: "Coboundary Expansion of Coset ..." Coboundary Expansion of Coset Complexes Izhar Oppenheim, Tali Kaufman, and Shmuel Weinberger (Ben-Gurion University of the Negev, Israel; Bar-Ilan University, Israel; University of Chicago, USA) Coboundary expansion is a high dimensional generalization of the Cheeger constant to simplicial complexes. Originally, this notion was motivated by the fact that it implies topological expansion, but nowadays a significant part of the motivation stems from its deep connection to problems in theoretical computer science such as list agreement expansion and agreement expansion in the low soundness regime. In this paper, we prove coboundary expansion with non-Abelian coefficients for the coset complex construction of Kaufman and Oppenheim. Our proof uses a novel global argument, as opposed to the local-to-global arguments that are used to prove cosystolic expansion. Article Search
	Kempa, Dominik	STOC '25: "On the Hardness Hierarchy ..." On the Hardness Hierarchy for the O(𝑛 √log 𝑛) Complexity in the Word RAM Dominik Kempa and Tomasz Kociumaka (Stony Brook University, USA; IMPI-INF, Germany) Article Search
	Khanna, Sanjeev	STOC '25: "Correlation Clustering and ..." 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) Article Search STOC '25: "Efficient Algorithms and New ..." Efficient Algorithms and New Characterizations for CSP Sparsification Sanjeev Khanna, Aaron Putterman, and Madhu Sudan (University of Pennsylvania, USA; Harvard University, USA) Article Search STOC '25: "Near-Optimal Linear Sketches ..." 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) Article Search
	Khot, Subhash	STOC '25: "Parallel Repetition for 3-Player ..." 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; Institute for Advanced Study at Princeton, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search STOC '25: "Approximation Algorithms for ..." Approximation Algorithms for Satisfiable CSPs via a Mixed Invariance Principle Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) Article Search
	Khurana, Dakshita	STOC '25: "Founding Quantum Cryptography ..." 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) Article Search
	Kiss, Peter	STOC '25: "Deterministic Dynamic Maximal ..." 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) Article Search
	Klein, Kim-Manuel	STOC '25: "Faster Lattice Basis Computation ..." 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) Article Search
	Kleinberg, Robert	STOC '25: "Breaking the T2/3 ..." Breaking the T2/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) Article Search
	Klivans, Adam R.	STOC '25: "Learning the Sherrington-Kirkpatrick ..." Learning the Sherrington-Kirkpatrick Model Even at Low Temperature Gautam Chandrasekaran and Adam R. Klivans (University of Texas at Austin, USA) Article Search
	Kociumaka, Tomasz	STOC '25: "On the Hardness Hierarchy ..." On the Hardness Hierarchy for the O(𝑛 √log 𝑛) Complexity in the Word RAM Dominik Kempa and Tomasz Kociumaka (Stony Brook University, USA; IMPI-INF, Germany) Article Search STOC '25: "Bounded Edit Distance: Optimal ..." Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights Egor Gorbachev and Tomasz Kociumaka (Saarland University, Germany; MPI-INF, Germany; IMPI-INF, Germany) Article Search
	Koh, Zhuan Khye	STOC '25: "Approximating the Held–Karp ..." 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) Article Search
	Komargodski, Ilan	STOC '25: "A New Approach for LPN-Based ..." 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) Article Search
	Kook, Yunbum	STOC '25: "Sampling and Integration of ..." Sampling and Integration of Logconcave Functions by Algorithmic Diffusion Yunbum Kook and Santosh S. Vempala (Georgia Institute of Technology, USA) Article Search
	Kopparty, Swastik	STOC '25: "Improved PIR Schemes using ..." Improved PIR Schemes using Matching Vectors and Derivatives Fatemeh Ghasemi, Swastik Kopparty, and Madhu Sudan (University of Toronto, Canada; Harvard University, USA) Article Search STOC '25: "High Rate Multivariate Polynomial ..." High Rate Multivariate Polynomial Evaluation Codes Mrinal Kumar, Harry Sha, and Swastik Kopparty (TIFR, USA; University of Toronto, Canada) Article Search
	Korhonen, Tuukka	STOC '25: "Linear-Time Algorithms for ..." Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More Tuukka Korhonen (University of Copenhagen, Denmark) We present kO(k2) m time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size <k into parts that are “well-connected” with respect to cuts or separators of size <k; here, m is the total number of vertices and edges of the graph. As an application of our results, we obtain for every fixed k a linear-time algorithm for computing the k-edge-connected components of a given graph, solving a long-standing open problem. More generally, we obtain a kO(k2) m time algorithm for computing a k-Gomory-Hu tree of a given graph, which is a structure representing pairwise minimum cuts of size <k. Our main technical result, from which the other results follow, is a kO(k2) m time algorithm for computing a k-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size <k that captures the existence of separators of size <k between subsets of its bags. A k-lean tree decomposition is also an unbreakable tree decomposition with optimal unbreakability parameters for the adhesion size bound k. As further applications, we obtain kO(k2) m time algorithms for k-vertex connectivity and for element connectivity k-Gomory-Hu tree. All of our algorithms are deterministic. Our techniques are inspired by the tenth paper of the Graph Minors series of Robertson and Seymour and by Bodlaender’s parameterized linear-time algorithm for treewidth. Article Search
	Kothari, Pravesh K.	STOC '25: "Rounding Large Independent ..." 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; Institute for Advanced Study at Princeton, USA) We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has its second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost 3-colorable or are promised to contain an independent set of size (1/2−є)n. Our second result above can be refined to require only a weaker vertex expansion property with an efficient certificate. In a surprising contrast to our algorithmic result, we observe that the analogous task of finding a linear-sized independent set in almost 4-colorable one-sided expanders (even when the second eigenvalue is on(1)) is NP-hard, assuming the Unique Games Conjecture. All prior algorithms that beat the worst-case guarantees for this problem rely on bottom eigenspace enumeration techniques (following the classical spectral methods of Alon and Kahale) and require two-sided expansion, meaning a bounded number of negative eigenvalues of magnitude Ω(1). Such techniques naturally extend to almost k-colorable graphs for any constant k, in contrast to analogous guarantees on one-sided expanders, which are Unique Games-hard to achieve for k ≥ 4. Our rounding scheme builds on the method of simulating multiple samples from a pseudo-distribution introduced in Bafna et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs - every large independent set has a larger-than-expected intersection with some member of a small list - and its formalization in the low-degree sum-of-squares proof system. Preprint
	Krauthgamer, Robert	STOC '25: "Near-Optimal Dimension Reduction ..." 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) Article Search
	Kretschmer, William	STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search STOC '25: "Quantum-Computable One-Way ..." 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) Article Search
	Krivelevich, Michael	STOC '25: "Disjoint Connected Dominating ..." Disjoint Connected Dominating Sets in Pseudorandom Graphs Nemanja Draganic and Michael Krivelevich (University of Oxford, UK; Tel Aviv University, Israel) Article Search
	Kühn, Marcus	STOC '25: "The Hypergraph Removal Process ..." The Hypergraph Removal Process Felix Joos and Marcus Kühn (University of Heidelberg, Germany) Article Search
	Kulpe, Alexander	STOC '25: "A Bound on the Quantum Value ..." 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) Article Search
	Kumar, Amit	STOC '25: "Tight Results for Online Convex ..." Tight Results for Online Convex Paging Anupam Gupta, Amit Kumar, and Debmalya Panigrahi (New York University, USA; IIT Delhi, India; Duke University, USA) Article Search
	Kumar, Mrinal	STOC '25: "High Rate Multivariate Polynomial ..." High Rate Multivariate Polynomial Evaluation Codes Mrinal Kumar, Harry Sha, and Swastik Kopparty (TIFR, USA; University of Toronto, Canada) Article Search
	Kumar, Vinayak M.	STOC '25: "Linear Hashing Is Good ..." Linear Hashing Is Good Michael Jaber, Vinayak M. Kumar, and David Zuckerman (University of Texas at Austin, USA) Article Search
	Kundu, Srijita	STOC '25: "Uncloneable Quantum States ..." 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) Article Search
	Kunisky, Dmitriy	STOC '25: "Statistical Inference of a ..." 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) Article Search
	Kush, Deepanshu	STOC '25: "Polynomial-Time PIT from (Almost) ..." Polynomial-Time PIT from (Almost) Necessary Assumptions Robert Andrews, Deepanshu Kush, and Roei Tell (University of Waterloo, Canada; University of Toronto, Canada) Article Search
	Kuszmaul, William	STOC '25: "Optimal Non-oblivious Open ..." Optimal Non-oblivious Open Addressing Michael A. Bender, William Kuszmaul, and Renfei Zhou (Stony Brook University, USA; Carnegie Mellon University, USA) Article Search
	Kwan, Matthew	STOC '25: "Smoothed Analysis for Graph ..." Smoothed Analysis for Graph Isomorphism Benjamin Moore, Michael Anastos, and Matthew Kwan (IST Austria, Austria) There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “na'ive refinement”, “na'ive vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph. Article Search
	La, An	STOC '25: "Dynamic Locality Sensitive ..." Dynamic Locality Sensitive Orderings in Doubling Metrics An La and Hung Le (University of Massachusetts at Amherst, USA) Article Search
	Landau, Zeph	STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search STOC '25: "Learning Quantum States Prepared ..." Learning Quantum States Prepared by Shallow Circuits in Polynomial Time Zeph Landau and Yunchao Liu (University of California at Berkeley, USA; Harvard University, USA) Article Search
	Lassota, Alexandra	STOC '25: "Six Candidates Suffice to ..." 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) Article Search
	Lattanzi, Silvio	STOC '25: "The Cost of Consistency: Submodular ..." The Cost of Consistency: Submodular Maximization with Constant Recourse Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam (Google, Switzerland; Sapienza University of Rome, Italy; Google, USA; EPFL, Switzerland) Article Search STOC '25: "Almost Optimal PAC Learning ..." Almost Optimal PAC Learning for 𝑘-Means Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn (Google Research, France; Google, USA; Aarhus University, Denmark) Article Search
	Le, Hung	STOC '25: "Dynamic Locality Sensitive ..." Dynamic Locality Sensitive Orderings in Doubling Metrics An La and Hung Le (University of Massachusetts at Amherst, USA) Article Search STOC '25: "Light Tree Covers, Routing, ..." 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) Article Search
	Lee, Euiwoong	STOC '25: "A (2+ε)-Approximation Algorithm ..." 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) Article Search STOC '25: "Asymptotically Optimal Hardness ..." Asymptotically Optimal Hardness for 𝑘-Set Packing and 𝑘-Matroid Intersection Euiwoong Lee, Ola Svensson, and Theophile Thiery (University of Michigan, USA; EPFL, Switzerland) Article Search STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Le Gall, François	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Lehtinen, Karoliina	STOC '25: "The 2-Token Theorem: Recognising ..." The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently Karoliina Lehtinen and Aditya Prakash (CNRS - Aix-Marseille Université - LIS, France; University of Warwick, UK) Article Search
	Levi, Amit	STOC '25: "Testing vs Estimation for ..." 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) Article Search
	Levi, Reut	STOC '25: "Approximately Counting and ..." 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) Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In the sublinear-time regime, the relaxed problem of approximate counting has been explored within two prominent query frameworks: the standard model, which permits degree, neighbor, and pair queries, and the strictly more powerful augmented model, which additionally allows for uniform edge sampling. Currently, in the standard model, (optimal) results have been established only for approximately counting edges, stars, and cliques, all of which have a radius of one. This contrasts sharply with the state of affairs in the augmented model, where algorithmic results (some of which are optimal) are known for any input motif, leading to a disparity which we term the “scope gap” between the two models. In this work, we make significant progress in bridging this gap. Our approach draws inspiration from recent advancements in the augmented model and utilizes a framework centered on counting by uniform sampling, thus allowing us to establish new results in the standard model and simplify on previous results. In particular, our first, and main, contribution is a new algorithm in the standard model for approximately counting any Hamiltonian motif in sublinear time, where the complexity of the algorithm is the sum of two terms. One term equals the complexity of the known algorithms by Assadi, Kapralov, and Khanna (ITCS 2019) and Fichtenberger and Peng (ICALP 2020) in the (strictly stronger) augmented model and the other is an additional, necessary, additive overhead. Our second contribution is a variant of our algorithm that enables nearly uniform sampling of these motifs, a capability previously limited in the standard model to edges and cliques. Our third contribution is to introduce even simpler algorithms for stars and cliques by exploiting their radius-one property. As a result, we simplify all previously known algorithms in the standard model for stars (Gonen, Ron, Shavitt (SODA 2010)), triangles (Eden, Levi, Ron Seshadhri (FOCS 2015)) and cliques (Eden, Ron, Seshadri (STOC 2018)). Article Search Info
	Li, Huan	STOC '25: "Near-Optimal Linear Sketches ..." 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) Article Search
	Li, Jason	STOC '25: "Network Unreliability in Almost-Linear ..." Network Unreliability in Almost-Linear Time Debmalya Panigrahi, Ruoxu Cen, and Jason Li (Duke University, USA; Carnegie Mellon University, USA) Article Search
	Li, Jerry	STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search
	Li, Jiatu	STOC '25: "The Structure of Catalytic ..." The Structure of Catalytic Space: Capturing Randomness and Time via Compression James Cook, Jiatu Li, Ian Mertz, and Edward Pyne (University of Toronto, Canada; Massachusetts Institute of Technology, USA; University of Warwick, UK) In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexity-theoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open. We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows. 1: We unconditionally derandomize catalytic logspace: CBPL = CL. 2: We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in CL ∩ P can be solved in polynomial time-bounded CL. 3: We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytime-bounded, zero-error randomized CL. Our results center around the compress–or–random framework. For the second result, we introduce a simple yet novel compress–or–compute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress–or–compress–or–random algorithm that combines runtime compression with a second compress–or–random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction. Article Search STOC '25: "Maximum Circuit Lower Bounds ..." 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) Article Search
	Li, Jiawei	STOC '25: "Quantum Communication Advantage ..." Quantum Communication Advantage in TFNP Siddhartha Jain, Mika Göös, Tom Gur, and Jiawei Li (University of Texas at Austin, USA; EPFL, Switzerland; University of Cambridge, UK) Article Search
	Li, Ray	STOC '25: "Locality vs Quantum Codes ..." Locality vs Quantum Codes Samuel Dai and Ray Li (Northeastern University, USA; Santa Clara University, USA) Article Search
	Li, Shi	STOC '25: "Constant Approximation for ..." 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) Article Search STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Li, Shuangping	STOC '25: "Discrepancy Algorithms for ..." Discrepancy Algorithms for the Binary Perceptron Shuangping Li, Tselil Schramm, and Kangjie Zhou (Stanford University, USA; Columbia University, USA) Article Search
	Li, Yuanzhi	STOC '25: "Provably Learning a Multi-head ..." Provably Learning a Multi-head Attention Layer Sitan Chen and Yuanzhi Li (Harvard University, USA; Microsoft Research, n.n.) Article Search
	Liang, Jingxun	STOC '25: "Maximum Circuit Lower Bounds ..." 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) Article Search STOC '25: "Optimal Static Dictionary ..." 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) Article Search STOC '25: "Low Rank Matrix Rigidity: ..." Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification Josh Alman and Jingxun Liang (Columbia University, USA; Carnegie Mellon University, USA) Article Search
	Lievonen, Henrik	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Lin, Bingkai	STOC '25: "Almost Optimal Time Lower ..." 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) The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f:ℕ→ℕ, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1−o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1−o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing. Article Search
	Lin, Honghao	STOC '25: "Lifting Linear Sketches: Optimal ..." 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) Article Search
	Lin, Ting-Chun	STOC '25: "Explicit Two-Sided Vertex ..." 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) Article Search STOC '25: "Quantum LDPC Codes with Transversal ..." 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) Article Search
	Linder, Ephraim	STOC '25: "Privately Evaluating Untrusted ..." Privately Evaluating Untrusted Black-Box Functions Ephraim Linder, Sofya Raskhodnikova, Adam Smith, and Thomas Steinke (Boston University, USA; Google Research, n.n.) Article Search
	Lindermayr, Alexander	STOC '25: "A 5/4-Approximation for Two-Edge ..." 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) Article Search
	Liu, Allen	STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search STOC '25: "Model Stealing for Any Low-Rank ..." Model Stealing for Any Low-Rank Language Model Allen Liu and Ankur Moitra (Massachusetts Institute of Technology, USA) Article Search
	Liu, Chun-Hung	STOC '25: "Disjoint Paths Problem with ..." Disjoint Paths Problem with Group-Expressable Constraints Chun-Hung Liu and Youngho Yoo (Texas A&M University, USA) We study an extension of the k-Disjoint Paths Problem where, in addition to finding k disjoint paths joining k given pairs of vertices in a graph, we ask that those paths satisfy certain constraints expressable by abelian groups. We give an O(n8) time algorithm to solve this problem under the assumption that the constraint can be expressed as avoiding a bounded number of group elements; moreover, our O(n8) algorithm allows any bounded number of such constraints to be combined. Examples of group-expressable constraints include: (1) paths of length ℓ modulo m for any fixed integers ℓ and m with m ≥ 2, (2) paths passing through a bounded number of prescribed sets of edges and/or vertices, and (3) paths that are long detours (si-ti-paths with length at least (si,ti)+ℓ for any fixed integer ℓ). The k=1 case of the problem with modularity constraints solves a problem in [Arkin, Papadimitriou, and Yannakakis, J. ACM, (1991)] that has remained open for over 30 years. Our work also implies a polynomial time algorithm for testing the existence of a subgraph isomorphic to a subdivision of a fixed graph, where each path of the subdivision between branch vertices satisfies any combination of a bounded number of group-expressable constraints. This in particular gives a unified polynomial time algorithm for testing the existence of k disjoint cycles with such constraints. For example, we can test in polynomial time the existence of k disjoint cycles in surface-embedded graphs such that each cycle is non-homologous to 0 and is at least ℓ longer than the minimum length of such a cycle. In addition, our work implies similar results addressing edge-disjointness. Article Search
	Liu, Jiahui	STOC '25: "Quantum One-Time Programs, ..." Quantum One-Time Programs, Revisited Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, and Vinod Vaikuntanathan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; University of California at Berkeley, USA) Article Search STOC '25: "QMA vs QCMA and Pseudorandomness ..." QMA vs QCMA and Pseudorandomness Jiahui Liu, Saachi Mutreja, and Henry Yuen (Fujitsu Research, n.n.; Columbia University, USA) Article Search
	Liu, Jingcheng	STOC '25: "Phase Transitions via Complex ..." Phase Transitions via Complex Extensions of Markov Chains Jingcheng Liu, Chunyang Wang, Yitong Yin, and Yixiao Yu (Nanjing University, China) Article Search
	Liu, Sihan	STOC '25: "Entangled Mean Estimation ..." 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) Article Search
	Liu, Yang	STOC '25: "Parallel Repetition for 3-Player ..." 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; Institute for Advanced Study at Princeton, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search
	Liu, Yuhan	STOC '25: "Pauli Measurements Are Not ..." 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) Article Search
	Liu, Yunchao	STOC '25: "Learning Quantum States Prepared ..." Learning Quantum States Prepared by Shallow Circuits in Polynomial Time Zeph Landau and Yunchao Liu (University of California at Berkeley, USA; Harvard University, USA) Article Search
	Lokshtanov, Daniel	STOC '25: "Subexponential Parameterized ..." 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) Article Search STOC '25: "Efficiently Finding and Counting ..." 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) Article Search
	Lolck, David Rasmussen	STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Lombardi, Alex	STOC '25: "Universal SNARGs for NP from ..." Universal SNARGs for NP from Proofs of Completeness Zhengzhong Jin, Yael Kalai, Alex Lombardi, and Surya Mathialagan (Northeastern University, USA; Massachusetts Institute of Technology, USA; MSR, USA; Princeton University, USA) Article Search
	Lonkar, Aditya	STOC '25: "Counting random 𝑘-SAT near ..." 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) Article Search
	Lovász, László	STOC '25: "Matroid Products via Submodular ..." 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) Article Search
	Lucca, Kevin	STOC '25: "Tensor Concentration Inequalities: ..." 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) Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓp injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p=2 [39,45,59]. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes. Article Search STOC '25: "Matrix Chaos Inequalities ..." 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) Article Search
	Lysikov, Vladimir	STOC '25: "Computing Moment Polytopes ..." 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 (University of Amsterdam, Netherlands; Ruhr University Bochum, Germany; University of Copenhagen, Denmark) Article Search
	Lyu, Xin	STOC '25: "Fingerprinting Codes Meet ..." 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) Article Search
	Ma, Fermi	STOC '25: "How to Construct Random Unitaries ..." 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) Article Search
	Mackenzie, Simon	STOC '25: "Refuting the Direct Sum Conjecture ..." Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity Simon Mackenzie and Abdallah Saffidine (Unaffiliated, Australia) Article Search
	Maga, Balázs	STOC '25: "Matroid Products via Submodular ..." 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) Article Search
	Majenz, Christian	STOC '25: "Permutation Superposition ..." Permutation Superposition Oracles for Quantum Query Lower Bounds Christian Majenz, Giulio Malavolta, and Michael Walter (DTU, Denmark; Bocconi University, Italy; Ruhr University Bochum, Germany) Article Search
	Majid, Mahbod	STOC '25: "Sample-Optimal Private Regression ..." Sample-Optimal Private Regression in Polynomial Time Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel (Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland) Article Search
	Malavolta, Giulio	STOC '25: "A Bound on the Quantum Value ..." 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) Article Search STOC '25: "Permutation Superposition ..." Permutation Superposition Oracles for Quantum Query Lower Bounds Christian Majenz, Giulio Malavolta, and Michael Walter (DTU, Denmark; Bocconi University, Italy; Ruhr University Bochum, Germany) Article Search STOC '25: "Succinct Oblivious Tensor ..." 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) Article Search
	Mansour, Yishay	STOC '25: "On Differentially Private ..." On Differentially Private Linear Algebra Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur (Tel Aviv University, Israel; Google Research, Israel; Google Research, n.n.; Technion, Israel) Article Search
	Mao, Jiayi	STOC '25: "Breaking the Sorting Barrier ..." 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) Article Search
	Mao, Xiao	STOC '25: "Breaking the Sorting Barrier ..." 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) Article Search
	Mao, Yuchen	STOC '25: "Long Arithmetic Progressions ..." Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses Lin Chen, Yuchen Mao, and Guochuan Zhang (Zhejiang University, China) Article Search
	Mathialagan, Surya	STOC '25: "Universal SNARGs for NP from ..." Universal SNARGs for NP from Proofs of Completeness Zhengzhong Jin, Yael Kalai, Alex Lombardi, and Surya Mathialagan (Northeastern University, USA; Massachusetts Institute of Technology, USA; MSR, USA; Princeton University, USA) Article Search
	Maystre, Gilbert	STOC '25: "Supercritical Tradeoffs for ..." Supercritical Tradeoffs for Monotone Circuits Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov (EPFL, Switzerland) Article Search
	Mehraban, Saeed	STOC '25: "Improved Bounds for Testing ..." Improved Bounds for Testing Low Stabilizer Complexity States Saeed Mehraban and Mehrdad Tahmasbi (Tufts University, USA; University of Illinois at Urbana-Champaign, USA) Article Search
	Mehrotra, Anay	STOC '25: "On the Limits of Language ..." On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas (Yale University, USA) Article Search
	Mehta, Ruta	STOC '25: "Monotone Contractions ..." Monotone Contractions Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani (University of Liverpool, UK; University of Illinois at Urbana-Champaign, USA) Article Search
	Melnyk, Darya	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search
	Meng, Boning	STOC '25: "The FPᴺᴾ versus #P Dichotomy ..." 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) Article Search
	Mertz, Ian	STOC '25: "The Structure of Catalytic ..." The Structure of Catalytic Space: Capturing Randomness and Time via Compression James Cook, Jiatu Li, Ian Mertz, and Edward Pyne (University of Toronto, Canada; Massachusetts Institute of Technology, USA; University of Warwick, UK) In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexity-theoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open. We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows. 1: We unconditionally derandomize catalytic logspace: CBPL = CL. 2: We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in CL ∩ P can be solved in polynomial time-bounded CL. 3: We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytime-bounded, zero-error randomized CL. Our results center around the compress–or–random framework. For the second result, we introduce a simple yet novel compress–or–compute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress–or–compress–or–random algorithm that combines runtime compression with a second compress–or–random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction. Article Search
	Minzer, Dor	STOC '25: "Parallel Repetition for 3-Player ..." 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; Institute for Advanced Study at Princeton, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) Article Search STOC '25: "Quasi-Linear Size PCPs with ..." 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) Article Search STOC '25: "Near Optimal Constant Inapproximability ..." 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) Article Search STOC '25: "Approximation Algorithms for ..." Approximation Algorithms for Satisfiable CSPs via a Mixed Invariance Principle Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) Article Search STOC '25: "Constant Degree Networks for ..." Constant Degree Networks for Almost-Everywhere Reliable Transmission Mitali Bafna and Dor Minzer (Massachusetts Institute of Technology, USA) Article Search
	Mishra, Gopinath	STOC '25: "Testing vs Estimation for ..." 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) Article Search
	Mittal, Tushant	STOC '25: "Explicit Codes Approaching ..." 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; DIMACS, USA; Institute for Advanced Study at Princeton, USA; Toyota Technological Institute at Chicago, USA) Article Search
	Modanese, Augusto	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Mohanty, Sidhanth	STOC '25: "Weak Poincaré Inequalities, ..." 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) Article Search STOC '25: "Explicit Two-Sided Vertex ..." 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) Article Search
	Moitra, Ankur	STOC '25: "Model Stealing for Any Low-Rank ..." Model Stealing for Any Low-Rank Language Model Allen Liu and Ankur Moitra (Massachusetts Institute of Technology, USA) Article Search STOC '25: "Bypassing the Noisy Parity ..." 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) Article Search
	Mokhtari, Aryan	STOC '25: "Improved Complexity for Smooth ..." Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods Ruichen Jiang, Aryan Mokhtari, and Francisco Patitucci Perez (University of Texas at Austin, USA) Article Search
	Mond, Adva	STOC '25: "Minimum Degree Edge-Disjoint ..." 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) Article Search
	Moore, Benjamin	STOC '25: "Smoothed Analysis for Graph ..." Smoothed Analysis for Graph Isomorphism Benjamin Moore, Michael Anastos, and Matthew Kwan (IST Austria, Austria) There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “na'ive refinement”, “na'ive vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph. Article Search
	Moran, Shay	STOC '25: "On Reductions and Representations ..." On Reductions and Representations of Learning Problems in Euclidean Spaces Bogdan Chornomaz, Shay Moran, and Tom Waknine (Technion, Israel) Article Search STOC '25: "On Differentially Private ..." On Differentially Private Linear Algebra Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur (Tel Aviv University, Israel; Google Research, Israel; Google Research, n.n.; Technion, Israel) Article Search
	Morimae, Tomoyuki	STOC '25: "Cryptographic Characterization ..." Cryptographic Characterization of Quantum Advantage Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa (Kyoto University, Japan; NTT, Japan) Article Search
	Moshkovitz, Dana	STOC '25: "Time and Space Efficient Deterministic ..." Time and Space Efficient Deterministic Decoders Joshua Cook and Dana Moshkovitz (University of Texas at Austin, USA) Article Search
	Mossel, Elchanan	STOC '25: "Bypassing the Noisy Parity ..." 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) Article Search STOC '25: "Weak Recovery, Hypothesis ..." 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) Article Search
	Mozes, Shay	STOC '25: "Õptimal Fault-Tolerant Labeling ..." Õ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) Article Search
	Mukhopadhyay, Sagnik	STOC '25: "Global vs. s-t Vertex Connectivity ..." Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, and Sorrachai Yingchareonthawornchai (KTH Royal Institute of Technology, Sweden; CWI, Netherlands; MPI-INF, Germany; Saarland University, Germany; University of Birmingham, UK; Hebrew University of Jerusalem, Israel; ETH Zurich, Switzerland) Article Search
	Munagala, Kamesh	STOC '25: "Metric Distortion of Small-Group ..." Metric Distortion of Small-Group Deliberation Ashish Goel, Mohak Goyal, and Kamesh Munagala (Stanford University, USA; Duke University, USA) We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most k, and these outcomes are aggregated by a social choice rule to find the winning alternative. We ground these models in the metric distortion framework, where the voters and alternatives are embedded in a latent metric space, with closer alternative being more desirable for a voter. We posit that the outcome of a small-group interaction optimally uses the voters’ collective knowledge of the metric, either deterministically or probabilistically. We characterize the distortion of our deliberation models for small k, showing that groups of size k=3 suffice to drive the distortion bound below the deterministic metric distortion lower bound of 3, and groups of size 4 suffice to break the randomized lower bound of 2.11. We also show nearly tight asymptotic distortion bounds in the group size, showing that for any constant є > 0, achieving a distortion of 1+є needs group size that only depends on 1/є, and not the number of alternatives. We obtain these results via formulating a basic optimization problem in small deviations of the sum of i.i.d. random variables, which we solve to global optimality via non-convex optimization. The resulting bounds may be of independent interest in probability theory. Article Search
	Murhekar, Aniket	STOC '25: "Constant-Factor EFX Exists ..." Constant-Factor EFX Exists for Chores Jugal Garg, Aniket Murhekar, and John Qin (University of Illinois at Urbana-Champaign, USA) Article Search
	Mutreja, Saachi	STOC '25: "QMA vs QCMA and Pseudorandomness ..." QMA vs QCMA and Pseudorandomness Jiahui Liu, Saachi Mutreja, and Henry Yuen (Fujitsu Research, n.n.; Columbia University, USA) Article Search
	Nadara, Wojciech	STOC '25: "Fully Dynamic Biconnectivity ..." Fully Dynamic Biconnectivity in Õ(log² 𝑛) Time Jacob Holm, Wojciech Nadara, Eva Rotenberg, and Marek Sokołowski (University of Copenhagen, Denmark; DTU, Denmark; University of Warsaw, Poland; MPI-INF, Germany) Article Search
	Nadimpalli, Shivam	STOC '25: "DNF Learning via Locally Mixing ..." 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) Article Search
	Nagda, Ansh	STOC '25: "On Approximability of the ..." 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) We study the complexity of approximating the permanent of a positive semidefinite matrix A∈ ℂn× n. 1. We design a new approximation algorithm for per(A) with approximation ratio e−(0.9999 + γ)n, exponentially improving upon the current best bound of e−(1+γ−o(1))n (Anari-Gurvits-Oveis Gharan-Saberi 2017, Yuan-Parrilo 2022). Here, γ ≈ 0.577 is Euler’s constant. 2. We prove that it is NP-hard to approximate per(A) within a factor e−(γ−)n for any >0. This is the first exponential hardness of approximation for this problem. Along the way, we prove optimal hardness of approximation results for the ||·||2→ q “norm” problem of a matrix for all −1 < q < 2. Article Search
	Nalam, Chaitanya	STOC '25: "Deterministic Vertex Connectivity ..." 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) Article Search
	Naor, Assaf	STOC '25: "Optimal Rounding for Sparsest ..." Optimal Rounding for Sparsest Cut Alan Chang, Assaf Naor, and Kevin Ren (Washington University in St. Louis, USA; Princeton University, USA) We prove that the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n≥ 2 is Θ(√logn). We achieve this by establishing the following geometric/structural result. If (M,d) is an n-point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x,y∈ M with d(x,y)≥ τ, the probability that both x∈ Z and d(y,Z)≥ βτ/√1+log(|B(y,κ β τ)|/|B(y,β τ)|) is Ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora–Rao–Vazirani rounding technique. Article Search
	Natarajan, Anand	STOC '25: "Classical Commitments to Quantum ..." Classical Commitments to Quantum States Sam Gunn, Yael Kalai, Anand Natarajan, and Agi Villanyi (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search
	Nehoran, Barak	STOC '25: "A General Quantum Duality ..." 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) Article Search
	Newman, Alantha	STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Ng, Hiu Tsun	STOC '25: "How Random CSPs Fool Hierarchies: ..." How Random CSPs Fool Hierarchies: II Siu On Chan and Hiu Tsun Ng (Unaffiliated, Hong Kong) Article Search
	Nguyen, Quynh T.	STOC '25: "Quantum Fault Tolerance with ..." 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) Article Search STOC '25: "Good Binary Quantum Codes ..." Good Binary Quantum Codes with Transversal CCZ Gate Quynh T. Nguyen (Harvard University, USA) Article Search
	Nieuwboer, Harold	STOC '25: "Computing Moment Polytopes ..." 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 (University of Amsterdam, Netherlands; Ruhr University Bochum, Germany; University of Copenhagen, Denmark) Article Search STOC '25: "Asymptotic Tensor Rank Is ..." Asymptotic Tensor Rank Is Characterized by Polynomials Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Peter Vrana, and Jeroen Zuiddam (University of Copenhagen, Denmark; University of Amsterdam, Netherlands; Budapest University of Technology and Economics, Hungary) Article Search
	Nir, Oded	STOC '25: "The Meta-complexity of Secret ..." The Meta-complexity of Secret Sharing Benny Applebaum and Oded Nir (Tel Aviv University, Israel) A secret-sharing scheme allows the distribution of a secret s among n parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about s. The collection of authorized/unauthorized sets is defined by a monotone function f: {0,1}n → {0,1}. It is known that any monotone function can be realized by a secret-sharing scheme; thus, the smallest achievable total share size, S(f), serves as a natural complexity measure. In this paper, we initiate the study of the following meta-complexity question: Given a monotone function f, is it possible to efficiently distinguish between cases where the secret-sharing complexity of f is small versus large? We examine this question across several computational models, yielding the following main results. (Hardness for formulas and circuits): Given a monotone formula f of size L, it is coNP-hard to distinguish between “cheap” functions, where the maximum share size is 1 bit and the total share size is O(L0.01), and “expensive” functions, where the maximum share size is Ω(√L) and the total share size is Ω(L/logL). This latter bound nearly matches known secret-sharing constructions yielding a total share size of L bits. For monotone circuits, we strengthen the bound on the expensive case to a maximum share size of Ω(L/logL) and a total share size of Ω(L2/logL). These results rule out the existence of instance-optimal compilers that map a formula f to a secret-sharing scheme with complexity polynomially related to S(f). (Hardness for truth tables): Under cryptographic assumptions, either (1) every n-bit slice function can be realized by a poly(n)-size secret-sharing scheme, or (2) given a truth-table representation of f of size N = 2n, it is computationally infeasible to distinguish in time poly(N) between cases where S(f) = poly(n) and S(f) = nω(1). Option (1) would be considered a breakthrough result, as the best-known construction for slices has a sub-exponential complexity of 2Õ(√n) (Liu, Vaikuntanathan, and Wee; Eurocrypt 2018). Our proof introduces a new worst-case-to-average-case reduction for slices, which may be of independent interest. (Hardness for graphs): We examine the simple case where f is given as a 2-DNF, represented by a graph G whose edges correspond to 2-terms, and ask whether it is possible to distinguish between cases where the share size is constant and those where the share size is large, say Ω(logn). We establish several connections between this question and questions in communication complexity. For instance, we show that graphs admitting constant-cost secret sharing form a subclass of graphs with constant randomized communication complexity and constant-size adjacency sketches (Harms, Wild, and Zamaraev; STOC 2022). We leverage these connections to establish new lower bounds for specific graph families, derive a combinatorial characterization of graphs with constant-size linear secret-sharing schemes, and show that a natural class of myopic algorithms fails to distinguish cheap graphs from expensive ones. Article Search
	Nizic-Nikolac, Petar	STOC '25: "Matrix Chaos Inequalities ..." 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) Article Search
	Nogler, Jakob	STOC '25: "Faster Weighted and Unweighted ..." 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) Article Search
	Nolin, Alexandre	STOC '25: "Faster Distributed 𝛥-Coloring ..." Faster Distributed 𝛥-Coloring via Ruling Subgraphs Yann Bourreau, Sebastian Brandt, and Alexandre Nolin (CISPA Helmholtz Center for Information Security, Germany) Article Search
	Nordström, Jakob	STOC '25: "Truly Supercritical Trade-Offs ..." 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) Article Search
	Norouzi-Fard, Ashkan	STOC '25: "The Cost of Consistency: Submodular ..." The Cost of Consistency: Submodular Maximization with Constant Recourse Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam (Google, Switzerland; Sapienza University of Rome, Italy; Google, USA; EPFL, Switzerland) Article Search
	O'Connor, Jack	STOC '25: "A Zero-Knowledge PCP Theorem ..." A Zero-Knowledge PCP Theorem Tom Gur, Jack O'Connor, and Nicholas Spooner (University of Cambridge, UK; Cornell University, USA) Article Search
	O'Donnell, Ryan	STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search STOC '25: "Explicit Two-Sided Vertex ..." 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) Article Search
	Oh, Eunjin	STOC '25: "Approximation Algorithms for ..." Approximation Algorithms for the Geometric Multimatching Problem Shinwoo An, Eunjin Oh, and Jie Xue (POSTECH, South Korea; New York University Shanghai, China) Article Search
	Okoroafor, Princewill	STOC '25: "Breaking the T2/3 ..." Breaking the T2/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) Article Search
	Oliveira, Rafael	STOC '25: "Primes via Zeros: Interactive ..." 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) Article Search
	Olivetti, Dennis	STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Oppenheim, Izhar	STOC '25: "Coboundary Expansion of Coset ..." Coboundary Expansion of Coset Complexes Izhar Oppenheim, Tali Kaufman, and Shmuel Weinberger (Ben-Gurion University of the Negev, Israel; Bar-Ilan University, Israel; University of Chicago, USA) Coboundary expansion is a high dimensional generalization of the Cheeger constant to simplicial complexes. Originally, this notion was motivated by the fact that it implies topological expansion, but nowadays a significant part of the motivation stems from its deep connection to problems in theoretical computer science such as list agreement expansion and agreement expansion in the low soundness regime. In this paper, we prove coboundary expansion with non-Abelian coefficients for the coset complex construction of Kaufman and Oppenheim. Our proof uses a novel global argument, as opposed to the local-to-global arguments that are used to prove cosystolic expansion. Article Search
	Opršal, Jakub	STOC '25: "Hardness of 4-Colouring 𝐺-Colourable ..." 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) Article Search
	Oshman, Rotem	STOC '25: "History-Independent Concurrent ..." History-Independent Concurrent Hash Tables Hagit Attiya, Michael A. Bender, Martin Farach-Colton, Rotem Oshman, and Noa Schiller (Technion, Israel; Stony Brook University, USA; New York University, USA; Tel Aviv University, Israel) Article Search
	Ostuni, Anthony	STOC '25: "Locally Sampleable Uniform ..." 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) We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let f∶{0,1}m→{0,1}n be a Boolean function where each output bit of f depends only on O(1) input bits. Assume the output distribution of f on uniform input bits is close to a uniform distribution D with a symmetric support. We show that D is essentially one of the following six possibilities: (1) point distribution on 0n, (2) point distribution on 1n, (3) uniform over {0n,1n}, (4) uniform over strings with even Hamming weights, (5) uniform over strings with odd Hamming weights, and (6) uniform over all strings. This confirms a conjecture of Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). This is an extended abstract. The full paper can be found at https://arxiv.org/abs/2411.08183v1. An updated version with a stronger result can be found at https://arxiv.org/abs/2411.08183. Preprint
	Ou, Fengning	STOC '25: "On the Computational Power ..." 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) Article Search
	Paddock, Connor	STOC '25: "A Bound on the Quantum Value ..." 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) Article Search
	Pai, Shreyas	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search
	Pak, Igor	STOC '25: "Vanishing of Schubert Coefficients ..." Vanishing of Schubert Coefficients Igor Pak and Colleen Robichaux (University of California at Los Angeles, USA) Article Search
	Pang, Shuo	STOC '25: "Truly Supercritical Trade-Offs ..." 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) Article Search
	Panigrahi, Debmalya	STOC '25: "Tight Results for Online Convex ..." Tight Results for Online Convex Paging Anupam Gupta, Amit Kumar, and Debmalya Panigrahi (New York University, USA; IIT Delhi, India; Duke University, USA) Article Search STOC '25: "Network Unreliability in Almost-Linear ..." Network Unreliability in Almost-Linear Time Debmalya Panigrahi, Ruoxu Cen, and Jason Li (Duke University, USA; Carnegie Mellon University, USA) Article Search
	Panolan, Fahad	STOC '25: "Subexponential Parameterized ..." 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) Article Search STOC '25: "Efficiently Finding and Counting ..." 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) Article Search
	Patel, Shyamal	STOC '25: "DNF Learning via Locally Mixing ..." 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) Article Search
	Pattison, Christopher A.	STOC '25: "Quantum Fault Tolerance with ..." 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) Article Search
	Pensia, Ankit	STOC '25: "SoS Certificates for Sparse ..." SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More Ilias Diakonikolas, Sam 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) Article Search STOC '25: "SoS Certifiability of Subgaussian ..." SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications Ilias Diakonikolas, Sam 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) Article Search
	Perez, Francisco Patitucci	STOC '25: "Improved Complexity for Smooth ..." Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods Ruichen Jiang, Aryan Mokhtari, and Francisco Patitucci Perez (University of Texas at Austin, USA) Article Search
	Pernice, Francisco	STOC '25: "List-Decoding Capacity Implies ..." 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) Article Search
	Pham, Huy Tuan	STOC '25: "A Sharp Version of Talagrand’s ..." 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) Article Search
	Piliouras, Georgios	STOC '25: "Faster Rates for No-Regret ..." 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, USA) Article Search
	Pinto Jr., Renato Ferreira	STOC '25: "Testing Support Size More ..." Testing Support Size More Efficiently Than Learning Histograms Renato Ferreira Pinto Jr. and Nathaniel Harms (University of Waterloo, Canada; EPFL, Switzerland) Article Search
	Pipis, Charilaos	STOC '25: "Efficient Learning and Computation ..." 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) Article Search
	Pittas, Thanasis	STOC '25: "Entangled Mean Estimation ..." 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) Article Search
	Podder, Supartha	STOC '25: "Uncloneable Quantum States ..." 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) Article Search
	Polak, Adam	STOC '25: "Faster Weighted and Unweighted ..." 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) Article Search
	Potechin, Aaron	STOC '25: "Sum-of-Squares Lower Bounds ..." Sum-of-Squares Lower Bounds for Coloring Random Graphs Aaron Potechin and Jeff Xu (University of Chicago, USA; Carnegie Mellon University, USA) Article Search
	Prakash, Aditya	STOC '25: "The 2-Token Theorem: Recognising ..." The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently Karoliina Lehtinen and Aditya Prakash (CNRS - Aix-Marseille Université - LIS, France; University of Warwick, UK) Article Search
	Putterman, Aaron	STOC '25: "Correlation Clustering and ..." 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) Article Search STOC '25: "Efficient Algorithms and New ..." Efficient Algorithms and New Characterizations for CSP Sparsification Sanjeev Khanna, Aaron Putterman, and Madhu Sudan (University of Pennsylvania, USA; Harvard University, USA) Article Search STOC '25: "Near-Optimal Linear Sketches ..." 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) Article Search
	Pyne, Edward	STOC '25: "The Structure of Catalytic ..." The Structure of Catalytic Space: Capturing Randomness and Time via Compression James Cook, Jiatu Li, Ian Mertz, and Edward Pyne (University of Toronto, Canada; Massachusetts Institute of Technology, USA; University of Warwick, UK) In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexity-theoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open. We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows. 1: We unconditionally derandomize catalytic logspace: CBPL = CL. 2: We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in CL ∩ P can be solved in polynomial time-bounded CL. 3: We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytime-bounded, zero-error randomized CL. Our results center around the compress–or–random framework. For the second result, we introduce a simple yet novel compress–or–compute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress–or–compress–or–random algorithm that combines runtime compression with a second compress–or–random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction. Article Search STOC '25: "When Connectivity Is Hard, ..." When Connectivity Is Hard, Random Walks Are Easy with Non-determinism Dean Doron, Edward Pyne, Roei Tell, and Ryan Williams (Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada) Two fundamental problems on directed graphs are to decide s-t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s-t connectivity running in polynomial time and no(1) space, and no known algorithm for estimating the n-step random walk matrix running in non-deterministic logspace. We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms A1 and A2 such that for every graph G, either: A1(G) outputs the transitive closure of G in polynomial time and polylogarithmic space. A2(G) outputs an approximation of the n-step random walk matrix of G in non-deterministic logspace. As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch’s theorem can be non-trivially sped up, or randomized space can be almost completely derandomized. We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron–Pyne–Tell STOC 2024, Li–Pyne–Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron–Tell CCC 2024). To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel–Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen–Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting. Article Search
	Qian, Luowen	STOC '25: "Quantum-Computable One-Way ..." 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) Article Search
	Qiao, Youming	STOC '25: "On the Complexity of Isomorphism ..." On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications Joshua Grochow and Youming Qiao (University of Colorado Boulder, USA; University of Technology Sydney, Australia) Article Search STOC '25: "On the Complexity of Isomorphism ..." On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings Joshua 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) Article Search
	Qin, John	STOC '25: "Constant-Factor EFX Exists ..." Constant-Factor EFX Exists for Chores Jugal Garg, Aniket Murhekar, and John Qin (University of Illinois at Urbana-Champaign, USA) Article Search
	Ragavan, Seyoon	STOC '25: "The Jacobi Factoring Circuit: ..." The Jacobi Factoring Circuit: Quantum Factoring in Near-Linear Gates and Sublinear Space Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk (Massachusetts Institute of Technology, USA; Harvard University, USA) Article Search
	Raizes, Justin	STOC '25: "Quantum One-Time Programs, ..." Quantum One-Time Programs, Revisited Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, and Vinod Vaikuntanathan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; University of California at Berkeley, USA) Article Search
	Raj, Roshan	STOC '25: "Characterizing and Testing ..." Characterizing and Testing Principal Minor Equivalence of Matrices Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj (Indian Statistical Institute, Kolkata, India; Chennai Mathematical Institute, India; IIT Bombay, India) Article Search
	Rajaraman, Amit	STOC '25: "Weak Poincaré Inequalities, ..." 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) Article Search
	Ramakrishnan, Prasanna	STOC '25: "Six Candidates Suffice to ..." 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) Article Search
	Raskhodnikova, Sofya	STOC '25: "Privately Evaluating Untrusted ..." Privately Evaluating Untrusted Black-Box Functions Ephraim Linder, Sofya Raskhodnikova, Adam Smith, and Thomas Steinke (Boston University, USA; Google Research, n.n.) Article Search
	Ren, Kevin	STOC '25: "Optimal Rounding for Sparsest ..." Optimal Rounding for Sparsest Cut Alan Chang, Assaf Naor, and Kevin Ren (Washington University in St. Louis, USA; Princeton University, USA) We prove that the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n≥ 2 is Θ(√logn). We achieve this by establishing the following geometric/structural result. If (M,d) is an n-point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x,y∈ M with d(x,y)≥ τ, the probability that both x∈ Z and d(y,Z)≥ βτ/√1+log(|B(y,κ β τ)|/|B(y,β τ)|) is Ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora–Rao–Vazirani rounding technique. Article Search
	Ren, Xuandi	STOC '25: "Almost Optimal Time Lower ..." 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) The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f:ℕ→ℕ, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1−o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1−o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing. Article Search
	Renou, Marc-Olivier	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Reuter, Janina	STOC '25: "Faster Lattice Basis Computation ..." 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) Article Search
	Risse, Kilian	STOC '25: "Supercritical Tradeoffs for ..." Supercritical Tradeoffs for Monotone Circuits Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov (EPFL, Switzerland) Article Search
	Ristic, Simeon	STOC '25: "Monotonicity Testing of High-Dimensional ..." 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) Article Search
	Rivkin, Joey	STOC '25: "A Generalized Trace Reconstruction ..." A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities Joey Rivkin, Paul Valiant, and Gregory Valiant (Stanford University, USA; Purdue University, USA) Article Search
	Roberts, Bhaskar	STOC '25: "Quantum One-Time Programs, ..." Quantum One-Time Programs, Revisited Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, and Vinod Vaikuntanathan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; University of California at Berkeley, USA) Article Search
	Robichaux, Colleen	STOC '25: "Vanishing of Schubert Coefficients ..." Vanishing of Schubert Coefficients Igor Pak and Colleen Robichaux (University of California at Los Angeles, USA) Article Search
	Ron, Dana	STOC '25: "Approximately Counting and ..." 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) Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In the sublinear-time regime, the relaxed problem of approximate counting has been explored within two prominent query frameworks: the standard model, which permits degree, neighbor, and pair queries, and the strictly more powerful augmented model, which additionally allows for uniform edge sampling. Currently, in the standard model, (optimal) results have been established only for approximately counting edges, stars, and cliques, all of which have a radius of one. This contrasts sharply with the state of affairs in the augmented model, where algorithmic results (some of which are optimal) are known for any input motif, leading to a disparity which we term the “scope gap” between the two models. In this work, we make significant progress in bridging this gap. Our approach draws inspiration from recent advancements in the augmented model and utilizes a framework centered on counting by uniform sampling, thus allowing us to establish new results in the standard model and simplify on previous results. In particular, our first, and main, contribution is a new algorithm in the standard model for approximately counting any Hamiltonian motif in sublinear time, where the complexity of the algorithm is the sum of two terms. One term equals the complexity of the known algorithms by Assadi, Kapralov, and Khanna (ITCS 2019) and Fichtenberger and Peng (ICALP 2020) in the (strictly stronger) augmented model and the other is an additional, necessary, additive overhead. Our second contribution is a variant of our algorithm that enables nearly uniform sampling of these motifs, a capability previously limited in the standard model to edges and cliques. Our third contribution is to introduce even simpler algorithms for stars and cliques by exploiting their radius-one property. As a result, we simplify all previously known algorithms in the standard model for stars (Gonen, Ron, Shavitt (SODA 2010)), triangles (Eden, Levi, Ron Seshadhri (FOCS 2015)) and cliques (Eden, Ron, Seshadri (STOC 2018)). Article Search Info
	Rotenberg, Eva	STOC '25: "Fully Dynamic Biconnectivity ..." Fully Dynamic Biconnectivity in Õ(log² 𝑛) Time Jacob Holm, Wojciech Nadara, Eva Rotenberg, and Marek Sokołowski (University of Copenhagen, Denmark; DTU, Denmark; University of Warsaw, Poland; MPI-INF, Germany) Article Search
	Roth, Aaron	STOC '25: "Tractable Agreement Protocols ..." Tractable Agreement Protocols Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth (University of Pennsylvania, USA) Article Search
	Rothblum, Ron D.	STOC '25: "Fiat-Shamir in the Plain Model ..." 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) Article Search
	Rothvoss, Thomas	STOC '25: "Tensor Concentration Inequalities: ..." 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) Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓp injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p=2 [39,45,59]. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes. Article Search
	Rouze, Cambyse	STOC '25: "Efficient Thermalization and ..." Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers Cambyse Rouze, Alvaro Alhambra, and Daniel Stilck França (Inria, France; IPP, France; Instituto de Física Teórica, Spain; CSIC, Spain; University of Copenhagen, Denmark) Article Search
	Roy, Lawrence	STOC '25: "Succinct Oblivious Tensor ..." 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) Article Search
	Rozhoň, Václav	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search
	Rubinfeld, Ronitt	STOC '25: "Stochastic Matching via In-n-Out ..." 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) Article Search STOC '25: "Approximately Counting and ..." 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) Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In the sublinear-time regime, the relaxed problem of approximate counting has been explored within two prominent query frameworks: the standard model, which permits degree, neighbor, and pair queries, and the strictly more powerful augmented model, which additionally allows for uniform edge sampling. Currently, in the standard model, (optimal) results have been established only for approximately counting edges, stars, and cliques, all of which have a radius of one. This contrasts sharply with the state of affairs in the augmented model, where algorithmic results (some of which are optimal) are known for any input motif, leading to a disparity which we term the “scope gap” between the two models. In this work, we make significant progress in bridging this gap. Our approach draws inspiration from recent advancements in the augmented model and utilizes a framework centered on counting by uniform sampling, thus allowing us to establish new results in the standard model and simplify on previous results. In particular, our first, and main, contribution is a new algorithm in the standard model for approximately counting any Hamiltonian motif in sublinear time, where the complexity of the algorithm is the sum of two terms. One term equals the complexity of the known algorithms by Assadi, Kapralov, and Khanna (ITCS 2019) and Fichtenberger and Peng (ICALP 2020) in the (strictly stronger) augmented model and the other is an additional, necessary, additive overhead. Our second contribution is a variant of our algorithm that enables nearly uniform sampling of these motifs, a capability previously limited in the standard model to edges and cliques. Our third contribution is to introduce even simpler algorithms for stars and cliques by exploiting their radius-one property. As a result, we simplify all previously known algorithms in the standard model for stars (Gonen, Ron, Shavitt (SODA 2010)), triangles (Eden, Levi, Ron Seshadhri (FOCS 2015)) and cliques (Eden, Ron, Seshadri (STOC 2018)). Article Search Info
	S., Karthik C.	STOC '25: "Near Optimal Constant Inapproximability ..." 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) Article Search
	Saberi, Amin	STOC '25: "Adaptive Approximation Schemes ..." 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) Article Search STOC '25: "From Signaling to Interviews ..." 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) Article Search
	Saffidine, Abdallah	STOC '25: "Refuting the Direct Sum Conjecture ..." Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity Simon Mackenzie and Abdallah Saffidine (Unaffiliated, Australia) Article Search
	Saha, Barna	STOC '25: "Faster Weighted and Unweighted ..." 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) Article Search
	Sahai, Amit	STOC '25: "Using the Planted Clique Conjecture ..." Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-XOR 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) Article Search
	Sandholm, Tuomas	STOC '25: "Computational Lower Bounds ..." 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) Article Search
	Saranurak, Thatchaphol	STOC '25: "Deterministic Vertex Connectivity ..." 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) Article Search STOC '25: "Deterministic Dynamic Maximal ..." 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) Article Search
	Saurabh, Saket	STOC '25: "Subexponential Parameterized ..." 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) Article Search STOC '25: "Efficiently Finding and Counting ..." 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) Article Search
	Savani, Rahul	STOC '25: "Monotone Contractions ..." Monotone Contractions Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani (University of Liverpool, UK; University of Illinois at Urbana-Champaign, USA) Article Search
	Sawettamalya, Pachara	STOC '25: "Strong XOR Lemma for Information ..." Strong XOR Lemma for Information Complexity Pachara Sawettamalya and Huacheng Yu (Princeton University, USA) For any {0,1}-valued function f, its n-folded XOR is the function f⊕ n where f⊕ n(X1, …, Xn) = f(X1) ⊕ ⋯ ⊕ f(Xn). Given a procedure for computing the function f, one can apply a “naive” approach to compute f⊕ n by computing each f(Xi) independently, followed by XORing the outputs. This approach uses n times the resources required for computing f. In this paper, we prove a strong XOR lemma for information complexity in the two-player randomized communication model: if computing f with an error probability of O(n−1) requires revealing I bits of information about the players’ inputs, then computing f⊕ n with a constant error requires revealing Ω(n) · (I − 1 − on(1)) bits of information about the players’ inputs. Our result demonstrates that the naive protocol for computing f⊕ n is both information-theoretically optimal and asymptotically tight in error trade-offs. Preprint
	Saxena, Nitin	STOC '25: "Primes via Zeros: Interactive ..." 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) Article Search
	Schiller, Noa	STOC '25: "History-Independent Concurrent ..." History-Independent Concurrent Hash Tables Hagit Attiya, Michael A. Bender, Martin Farach-Colton, Rotem Oshman, and Noa Schiller (Technion, Israel; Stony Brook University, USA; New York University, USA; Tel Aviv University, Israel) Article Search
	Schmidt, Simon	STOC '25: "A Bound on the Quantum Value ..." 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) Article Search
	Schneider, Jon	STOC '25: "Efficient Learning and Computation ..." 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) Article Search
	Schoepflin, Daniel	STOC '25: "Multi-parameter Mechanisms ..." 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) We consider the problem of designing auctions that maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way that maximizes the total buyer utility. The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller’s objective is welfare maximization or revenue maximization . However, in the case of consumer surplus maximization the picture is less clear – using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms that maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with tight approximation guarantees against the total social welfare. Along the way, we resolve an open question posed by Hartline and Roughgarden ’08 for the two bidder single item setting. Article Search
	Schramm, Tselil	STOC '25: "Discrepancy Algorithms for ..." Discrepancy Algorithms for the Binary Perceptron Shuangping Li, Tselil Schramm, and Kangjie Zhou (Stanford University, USA; Columbia University, USA) Article Search STOC '25: "Fast, Robust Approximate Message ..." Fast, Robust Approximate Message Passing Misha Ivkov and Tselil Schramm (Stanford University, USA) Article Search
	Schuch, Norbert	STOC '25: "Positive Bias Makes Tensor-Network ..." 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) Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d≳ n, a small positive mean value ≳ 1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #-, like for the zero-mean case. The mean value 1/d matches the phase transition point observed in previous work. Our proof makes use of Barvinok’s method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least -. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is -. This result compares to Arad and Landau’s result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is -. Our work thus identifies new parameter regimes in terms of the positivity of the tensor entries in which tensor networks can be (nearly) efficiently contracted. Preprint
	Schwarcz, Tamás	STOC '25: "Matroid Products via Submodular ..." 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) Article Search
	Schwiegelshohn, Chris	STOC '25: "A (2+ε)-Approximation Algorithm ..." 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) Article Search STOC '25: "Almost Optimal PAC Learning ..." Almost Optimal PAC Learning for 𝑘-Means Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn (Google Research, France; Google, USA; Aarhus University, Denmark) Article Search
	Sen, Sayantan	STOC '25: "Testing vs Estimation for ..." 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) Article Search
	Servedio, Rocco A.	STOC '25: "DNF Learning via Locally Mixing ..." 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) Article Search
	Seshadhri, C.	STOC '25: "Monotonicity Testing of High-Dimensional ..." 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) Article Search
	Seth, Cameron	STOC '25: "A Tolerant Independent Set ..." A Tolerant Independent Set Tester Cameron Seth (University of Waterloo, Canada) Article Search
	Sha, Harry	STOC '25: "High Rate Multivariate Polynomial ..." High Rate Multivariate Polynomial Evaluation Codes Mrinal Kumar, Harry Sha, and Swastik Kopparty (TIFR, USA; University of Toronto, Canada) Article Search
	Shafer, Jonathan	STOC '25: "Oblivious Defense in ML Models: ..." 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) Article Search
	Shaltiel, Ronen	STOC '25: "Extractors for Samplable Distributions ..." 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) Article Search
	Shaulker, Ariel	STOC '25: "Multi-parameter Mechanisms ..." 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) We consider the problem of designing auctions that maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way that maximizes the total buyer utility. The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller’s objective is welfare maximization or revenue maximization . However, in the case of consumer surplus maximization the picture is less clear – using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms that maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with tight approximation guarantees against the total social welfare. Along the way, we resolve an open question posed by Hartline and Roughgarden ’08 for the two bidder single item setting. Article Search
	Shimizu, Nobutaka	STOC '25: "Error-Correction of Matrix ..." Error-Correction of Matrix Multiplication Algorithms Shuichi Hirahara and Nobutaka Shimizu (National Institute of Informatics, Japan; Institute of Science Tokyo, Japan) Article Search
	Shirakawa, Yuki	STOC '25: "Cryptographic Characterization ..." Cryptographic Characterization of Quantum Advantage Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa (Kyoto University, Japan; NTT, Japan) Article Search
	Shu, Xinkai	STOC '25: "Breaking the Sorting Barrier ..." 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) Article Search
	Sidford, Aaron	STOC '25: "Accelerated Optimization of ..." Accelerated Optimization of Approximate Multi-commodity Flows on Directed Graphs Li Chen, Andrei Graur, and Aaron Sidford (Independent, USA; Stanford University, USA) Article Search
	Silbak, Jad	STOC '25: "Extractors for Samplable Distributions ..." 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) Article Search
	Singer, Neta	STOC '25: "Better Approximation for Weighted ..." Better Approximation for Weighted 𝑘-Matroid Intersection Neta Singer and Theophile Thiery (EPFL, Switzerland) Article Search
	Singla, Sahil	STOC '25: "Single-Sample and Robust Online ..." Single-Sample and Robust Online Resource Allocation Rohan Ghuge, Sahil Singla, and Yifan Wang (Georgia Institute of Technology, USA) Article Search
	Sinha, Pulkit	STOC '25: "Dimension Independent and ..." Dimension Independent and Computationally Efficient Shadow Tomography Pulkit Sinha (University of Waterloo, Canada) Article Search
	Sly, Allan	STOC '25: "Weak Recovery, Hypothesis ..." 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) Article Search
	Smith, Adam	STOC '25: "Privately Evaluating Untrusted ..." Privately Evaluating Untrusted Black-Box Functions Ephraim Linder, Sofya Raskhodnikova, Adam Smith, and Thomas Steinke (Boston University, USA; Google Research, n.n.) Article Search
	Sohn, Youngtak	STOC '25: "Weak Recovery, Hypothesis ..." 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) Article Search STOC '25: "Sharp Phase Transitions in ..." Sharp Phase Transitions in Estimation with Low-Degree Polynomials Youngtak Sohn and Alexander S. Wein (Brown University, USA; University of California at Davis, USA) Article Search
	Sokolov, Dmitry	STOC '25: "Supercritical Tradeoffs for ..." Supercritical Tradeoffs for Monotone Circuits Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov (EPFL, Switzerland) Article Search
	Sokołowski, Marek	STOC '25: "Fully Dynamic Biconnectivity ..." Fully Dynamic Biconnectivity in Õ(log² 𝑛) Time Jacob Holm, Wojciech Nadara, Eva Rotenberg, and Marek Sokołowski (University of Copenhagen, Denmark; DTU, Denmark; University of Warsaw, Poland; MPI-INF, Germany) Article Search
	Soleymani, Ashkan	STOC '25: "Faster Rates for No-Regret ..." 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, USA) Article Search
	Solomon, Shay	STOC '25: "Vizing’s Theorem in Near-Linear ..." Vizing’s Theorem in Near-Linear Time Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, and Tianyi Zhang (University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland) Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem. Preprint Video STOC '25: "Light Tree Covers, Routing, ..." 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) Article Search
	Song, Yifan	STOC '25: "Protecting Computations against ..." 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) We consider the question of protecting a general computation device, modeled by a stateful Boolean circuit, against leakage of partial information about its internal wires. Goyal et al. (FOCS 2016) obtained a solution for the case of bounded-communication leakage, where the wires are partitioned into two parts and the leakage can be any function computed using t bits of communication between the parts. However, this solution suffers from two major limitations: (1) it only applies to a one-shot (stateless) computation, mapping an encoded input to an encoded output, and (2) the leakage-resilient circuit consumes fresh random bits, whose number scales linearly with the circuit complexity of the computed function. In this work, we eliminate the first limitation and make progress on the second. Concretely: - We present the first construction of stateful circuits that offer information-theoretic protection against continuous bounded-communication leakage. As an application, we extend a two-party “malware-resilient” protocol of Goyal et al. to the continuous-leakage case. - For simple types of bounded-communication leakage, which leak t parities or t disjunctions of circuit wires or their negations, we obtain a deterministic variant that does not require any fresh randomness beyond the randomness in the initial state. Here we get computational security based on a subexponentially secure one-way function. This is the first deterministic leakage-resilient circuit construction for any nontrivial class of global leakage. Article Search
	Spielman, Daniel A.	STOC '25: "Statistical Inference of a ..." 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) Article Search
	Spooner, Nicholas	STOC '25: "A Zero-Knowledge PCP Theorem ..." A Zero-Knowledge PCP Theorem Tom Gur, Jack O'Connor, and Nicholas Spooner (University of Cambridge, UK; Cornell University, USA) Article Search
	Sprumont, Oscar	STOC '25: "List-Decoding Capacity Implies ..." 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) Article Search
	Srivastava, Shashank	STOC '25: "Explicit Codes Approaching ..." 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; DIMACS, USA; Institute for Advanced Study at Princeton, USA; Toyota Technological Institute at Chicago, USA) Article Search
	Stange, Katherine E.	STOC '25: "On the Complexity of Isomorphism ..." On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings Joshua 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) Article Search
	Steinke, Thomas	STOC '25: "Privately Evaluating Untrusted ..." Privately Evaluating Untrusted Black-Box Functions Ephraim Linder, Sofya Raskhodnikova, Adam Smith, and Thomas Steinke (Boston University, USA; Google Research, n.n.) Article Search
	Stemmer, Uri	STOC '25: "On Differentially Private ..." On Differentially Private Linear Algebra Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur (Tel Aviv University, Israel; Google Research, Israel; Google Research, n.n.; Technion, Israel) Article Search
	Sudan, Madhu	STOC '25: "Efficient Algorithms and New ..." Efficient Algorithms and New Characterizations for CSP Sparsification Sanjeev Khanna, Aaron Putterman, and Madhu Sudan (University of Pennsylvania, USA; Harvard University, USA) Article Search STOC '25: "Improved PIR Schemes using ..." Improved PIR Schemes using Matching Vectors and Derivatives Fatemeh Ghasemi, Swastik Kopparty, and Madhu Sudan (University of Toronto, Canada; Harvard University, USA) Article Search
	Sun, Enze	STOC '25: "Online Stochastic Matching ..." 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) Article Search
	Sun, Xiaorui	STOC '25: "On the Complexity of Isomorphism ..." On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings Joshua 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) Article Search
	Sun, Yican	STOC '25: "Almost Optimal Time Lower ..." 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) The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f:ℕ→ℕ, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1−o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1−o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing. Article Search
	Suomela, Jukka	STOC '25: "Online Locality Meets Distributed ..." 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; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland) Article Search STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Svensson, Ola	STOC '25: "A (2+ε)-Approximation Algorithm ..." 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) Article Search STOC '25: "The Cost of Consistency: Submodular ..." The Cost of Consistency: Submodular Maximization with Constant Recourse Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam (Google, Switzerland; Sapienza University of Rome, Italy; Google, USA; EPFL, Switzerland) Article Search STOC '25: "Asymptotically Optimal Hardness ..." Asymptotically Optimal Hardness for 𝑘-Set Packing and 𝑘-Matroid Intersection Euiwoong Lee, Ola Svensson, and Theophile Thiery (University of Michigan, USA; EPFL, Switzerland) Article Search
	Tahmasbi, Mehrdad	STOC '25: "Improved Bounds for Testing ..." Improved Bounds for Testing Low Stabilizer Complexity States Saeed Mehraban and Mehrdad Tahmasbi (Tufts University, USA; University of Illinois at Urbana-Champaign, USA) Article Search
	Tal, Avishay	STOC '25: "Quantum-Computable One-Way ..." 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) Article Search
	Talwar, Kunal	STOC '25: "Fingerprinting Codes Meet ..." 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) Article Search
	Tang, Ewin	STOC '25: "Learning the Closest Product ..." 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; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA) Article Search
	Tang, Zhihao Gavin	STOC '25: "Online Stochastic Matching ..." 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) Article Search
	Tasinato, Gianluca	STOC '25: "Hardness of 4-Colouring 𝐺-Colourable ..." 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) Article Search
	Tell, Roei	STOC '25: "Polynomial-Time PIT from (Almost) ..." Polynomial-Time PIT from (Almost) Necessary Assumptions Robert Andrews, Deepanshu Kush, and Roei Tell (University of Waterloo, Canada; University of Toronto, Canada) Article Search STOC '25: "When Connectivity Is Hard, ..." When Connectivity Is Hard, Random Walks Are Easy with Non-determinism Dean Doron, Edward Pyne, Roei Tell, and Ryan Williams (Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada) Two fundamental problems on directed graphs are to decide s-t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s-t connectivity running in polynomial time and no(1) space, and no known algorithm for estimating the n-step random walk matrix running in non-deterministic logspace. We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms A1 and A2 such that for every graph G, either: A1(G) outputs the transitive closure of G in polynomial time and polylogarithmic space. A2(G) outputs an approximation of the n-step random walk matrix of G in non-deterministic logspace. As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch’s theorem can be non-trivially sped up, or randomized space can be almost completely derandomized. We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron–Pyne–Tell STOC 2024, Li–Pyne–Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron–Tell CCC 2024). To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel–Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen–Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting. Article Search STOC '25: "Fiat-Shamir in the Plain Model ..." 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) Article Search
	Tendick, Lucas	STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Than, Cuong	STOC '25: "Light Tree Covers, Routing, ..." 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) Article Search
	Thiery, Theophile	STOC '25: "Better Approximation for Weighted ..." Better Approximation for Weighted 𝑘-Matroid Intersection Neta Singer and Theophile Thiery (EPFL, Switzerland) Article Search STOC '25: "Asymptotically Optimal Hardness ..." Asymptotically Optimal Hardness for 𝑘-Set Packing and 𝑘-Matroid Intersection Euiwoong Lee, Ola Svensson, and Theophile Thiery (University of Michigan, USA; EPFL, Switzerland) Article Search
	Thorup, Mikkel	STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Tian, Kevin	STOC '25: "Omnipredicting Single-Index ..." Omnipredicting Single-Index Models with Multi-index Models Lunjia Hu, Kevin Tian, and Chutong Yang (Harvard University, USA; University of Texas at Austin, USA) Article Search
	Tiegel, Stefan	STOC '25: "Sample-Optimal Private Regression ..." Sample-Optimal Private Regression in Polynomial Time Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel (Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland) Article Search STOC '25: "Near-Optimal Time-Sparsity ..." 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) Article Search STOC '25: "SoS Certificates for Sparse ..." SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More Ilias Diakonikolas, Sam 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) Article Search STOC '25: "SoS Certifiability of Subgaussian ..." SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications Ilias Diakonikolas, Sam 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) Article Search
	Tillich, Jean-Pierre	STOC '25: "Quantum Advantage from Soft ..." Quantum Advantage from Soft Decoders Andre Chailloux and Jean-Pierre Tillich (Inria, France) Article Search
	Tomer, Kabir	STOC '25: "Founding Quantum Cryptography ..." 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) Article Search
	Toruńczyk, Szymon	STOC '25: "Merge-Width and First-Order ..." Merge-Width and First-Order Model Checking Jan Dreier and Szymon Toruńczyk (TU Wien, Austria; University of Warsaw, Poland) Article Search
	Trabelsi, Ohad	STOC '25: "Breaking the 𝑂(𝑚𝑛)-Time ..." Breaking the 𝑂(𝑚𝑛)-Time Barrier for Vertex-Weighted Global Minimum Cut Julia Chuzhoy and Ohad Trabelsi (Toyota Technological Institute at Chicago, USA) Article Search
	Tulsiani, Madhur	STOC '25: "Explicit Codes Approaching ..." 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; DIMACS, USA; Institute for Advanced Study at Princeton, USA; Toyota Technological Institute at Chicago, USA) Article Search
	Tur, Nitzan	STOC '25: "On Differentially Private ..." On Differentially Private Linear Algebra Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur (Tel Aviv University, Israel; Google Research, Israel; Google Research, n.n.; Technion, Israel) Article Search
	Tzameret, Iddo	STOC '25: "Feasibly Constructive Proof ..." 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) Article Search
	Vafa, Neekon	STOC '25: "Oblivious Defense in ML Models: ..." 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) Article Search STOC '25: "Symmetric Perceptrons, Number ..." Symmetric Perceptrons, Number Partitioning, and Lattices Neekon Vafa and Vinod Vaikuntanathan (Massachusetts Institute of Technology, USA) Article Search
	Vaikuntanathan, Vinod	STOC '25: "Quantum One-Time Programs, ..." Quantum One-Time Programs, Revisited Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, and Vinod Vaikuntanathan (Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; University of California at Berkeley, USA) Article Search STOC '25: "Oblivious Defense in ML Models: ..." 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) Article Search STOC '25: "Symmetric Perceptrons, Number ..." Symmetric Perceptrons, Number Partitioning, and Lattices Neekon Vafa and Vinod Vaikuntanathan (Massachusetts Institute of Technology, USA) Article Search STOC '25: "The Jacobi Factoring Circuit: ..." The Jacobi Factoring Circuit: Quantum Factoring in Near-Linear Gates and Sublinear Space Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk (Massachusetts Institute of Technology, USA; Harvard University, USA) Article Search STOC '25: "Near-Optimal Time-Sparsity ..." 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) Article Search
	Valiant, Gregory	STOC '25: "Adaptive and Oblivious Statistical ..." Adaptive and Oblivious Statistical Adversaries Are Equivalent Guy Blanc and Gregory Valiant (Stanford University, USA) Article Search STOC '25: "A Generalized Trace Reconstruction ..." A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities Joey Rivkin, Paul Valiant, and Gregory Valiant (Stanford University, USA; Purdue University, USA) Article Search
	Valiant, Paul	STOC '25: "A Generalized Trace Reconstruction ..." A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities Joey Rivkin, Paul Valiant, and Gregory Valiant (Stanford University, USA; Purdue University, USA) Article Search
	Van den Berg, Maxim	STOC '25: "Computing Moment Polytopes ..." 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 (University of Amsterdam, Netherlands; Ruhr University Bochum, Germany; University of Copenhagen, Denmark) Article Search
	Van Dordrecht, Philippe	STOC '25: "Tolerant Testing of Stabilizer ..." 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) Article Search
	Van Handel, Ramon	STOC '25: "Matrix Chaos Inequalities ..." 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) Article Search
	Van Kirk, Katherine	STOC '25: "The Jacobi Factoring Circuit: ..." The Jacobi Factoring Circuit: Quantum Factoring in Near-Linear Gates and Sublinear Space Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk (Massachusetts Institute of Technology, USA; Harvard University, USA) Article Search
	Vassilevska Williams, Virginia	STOC '25: "Faster Weighted and Unweighted ..." 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) Article Search
	Veeren, Isadora	STOC '25: "Distributed Quantum Advantage ..." 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; 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; Inria, France) Article Search
	Velegkas, Grigoris	STOC '25: "On the Limits of Language ..." On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas (Yale University, USA) Article Search
	Vempala, Santosh S.	STOC '25: "Sampling and Integration of ..." Sampling and Integration of Logconcave Functions by Algorithmic Diffusion Yunbum Kook and Santosh S. Vempala (Georgia Institute of Technology, USA) Article Search
	Vetta, Adrian	STOC '25: "Six Candidates Suffice to ..." 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) Article Search
	Villanyi, Agi	STOC '25: "Classical Commitments to Quantum ..." Classical Commitments to Quantum States Sam Gunn, Yael Kalai, Anand Natarajan, and Agi Villanyi (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) Article Search
	Vladu, Adrian	STOC '25: "Breaking the Barrier of Self-concordant ..." Breaking the Barrier of Self-concordant Barriers: Faster Interior Point Methods for M-Matrices Adrian Vladu (CNRS, France; IRIF, France) Article Search
	Vogl, Lukas	STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Vrana, Peter	STOC '25: "Asymptotic Tensor Rank Is ..." Asymptotic Tensor Rank Is Characterized by Polynomials Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Peter Vrana, and Jeroen Zuiddam (University of Copenhagen, Denmark; University of Amsterdam, Netherlands; Budapest University of Technology and Economics, Hungary) Article Search
	Vyas, Nikhil	STOC '25: "Quasi-Linear Size PCPs with ..." 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) Article Search
	Wagner, Uli	STOC '25: "Hardness of 4-Colouring 𝐺-Colourable ..." 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) Article Search
	Waingarten, Erik	STOC '25: "Monotonicity Testing of High-Dimensional ..." 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) Article Search
	Waknine, Tom	STOC '25: "On Reductions and Representations ..." On Reductions and Representations of Learning Problems in Euclidean Spaces Bogdan Chornomaz, Shay Moran, and Tom Waknine (Technion, Israel) Article Search
	Walter, Michael	STOC '25: "Computing Moment Polytopes ..." 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 (University of Amsterdam, Netherlands; Ruhr University Bochum, Germany; University of Copenhagen, Denmark) Article Search STOC '25: "A Bound on the Quantum Value ..." 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) Article Search STOC '25: "Permutation Superposition ..." Permutation Superposition Oracles for Quantum Query Lower Bounds Christian Majenz, Giulio Malavolta, and Michael Walter (DTU, Denmark; Bocconi University, Italy; Ruhr University Bochum, Germany) Article Search
	Wang, Chunyang	STOC '25: "Phase Transitions via Complex ..." Phase Transitions via Complex Extensions of Markov Chains Jingcheng Liu, Chunyang Wang, Yitong Yin, and Yixiao Yu (Nanjing University, China) Article Search STOC '25: "Counting random 𝑘-SAT near ..." 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) Article Search
	Wang, Dingyu	STOC '25: "Harmonic Decomposition in ..." Harmonic Decomposition in Data Sketches Dingyu Wang (University of Michigan, USA) In the turnstile streaming model, a dynamic vector x=(x1,…,xn)∈ ℤn is updated by a stream of entry-wise increments/decrements. Let f∶ℤ→ ℝ+ be a symmetric function with f(0)=0. The f-moment of x is defined to be f(x) := ∑v∈[n]f(xv). We revisit the problem of constructing a universal sketch that can estimate many different f-moments. Previous constructions of universal sketches rely on the technique of sampling with respect to the L0-mass (uniform samples) or L2-mass (L2-heavy-hitters), whose universality comes from being able to evaluate the function f over the samples. To get samples, hash collisions are deliberately detected and avoided (with high probability), e.g. singleton-detectors are used in L0-sampling and the CountSketch is used in L2-sampling. Such auxiliary data structures introduce significant overhead in space. Apart from this issue, sampling-based methods are shown to perform poorly for estimating certain “nearly periodic functions” where Ω(poly(n)) samples are needed. In this paper, we propose a new universal sketching scheme that is almost “dual” to the sampling-based methods. Instead of evaluating f on samples, we decompose f into a linear combination of homomorphisms f1,f2,… from (ℤ,+) to (ℂ,×), where the fk-moments can be estimated regardless of hash collisions—because each fk is a homomorphism! Then we synthesize the estimates of the fk-moments to obtain an estimate of the f-moment. Universality now comes from the fact that we can weight the fk-moments arbitrarily, where the correct weighting depends on the harmonic structure of the function f. In contrast to the sampling-based methods, the new SymmetricPoissonTower sketch takes the harmonic approach. It embraces hash collisions instead of avoiding them, which saves multiple logn factors in space, e.g., when estimating all Lp-moments (f(z) = |z|p,p∈[0,2]). For many nearly periodic functions, the new sketch is exponentially more efficient than sampling-based methods. We conjecture that the SymmetricPoissonTower is the universal sketch that can estimate every tractable function f. Preprint
	Wang, Juqiu	STOC '25: "The FPᴺᴾ versus #P Dichotomy ..." 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) Article Search
	Wang, Kangning	STOC '25: "Six Candidates Suffice to ..." 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) Article Search
	Wang, Yifan	STOC '25: "Online Stochastic Matching ..." 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) Article Search STOC '25: "Single-Sample and Robust Online ..." Single-Sample and Robust Online Resource Allocation Rohan Ghuge, Sahil Singla, and Yifan Wang (Georgia Institute of Technology, USA) Article Search
	Wei, Zhewei	STOC '25: "Simple and Optimal Algorithms ..." 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) Article Search
	Weimann, Oren	STOC '25: "Õptimal Fault-Tolerant Labeling ..." Õ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) Article Search
	Wein, Alexander S.	STOC '25: "Statistical Inference of a ..." 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) Article Search STOC '25: "Sharp Phase Transitions in ..." Sharp Phase Transitions in Estimation with Low-Degree Polynomials Youngtak Sohn and Alexander S. Wein (Brown University, USA; University of California at Davis, USA) Article Search
	Wein, Nicole	STOC '25: "Covering Approximate Shortest ..." Covering Approximate Shortest Paths with DAGs Sepehr Assadi, Gary Hoppenworth, and Nicole Wein (University of Waterloo, Canada; University of Michigan, USA) Article Search
	Weinberger, Shmuel	STOC '25: "Coboundary Expansion of Coset ..." Coboundary Expansion of Coset Complexes Izhar Oppenheim, Tali Kaufman, and Shmuel Weinberger (Ben-Gurion University of the Negev, Israel; Bar-Ilan University, Israel; University of Chicago, USA) Coboundary expansion is a high dimensional generalization of the Cheeger constant to simplicial complexes. Originally, this notion was motivated by the fact that it implies topological expansion, but nowadays a significant part of the motivation stems from its deep connection to problems in theoretical computer science such as list agreement expansion and agreement expansion in the low soundness regime. In this paper, we prove coboundary expansion with non-Abelian coefficients for the coset complex construction of Kaufman and Oppenheim. Our proof uses a novel global argument, as opposed to the local-to-global arguments that are used to prove cosystolic expansion. Article Search
	Weinstein, Omri	STOC '25: "Approximating the Held–Karp ..." 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) Article Search STOC '25: "A Framework for Building Data ..." A Framework for Building Data Structures from Communication Protocols Alexandr Andoni, Shunhua Jiang, and Omri Weinstein (Columbia University, USA; Hebrew University of Jerusalem, Israel) Article Search
	Wichs, Daniel	STOC '25: "Unambiguous SNARGs for P from ..." 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) Article Search STOC '25: "Succinct Non-interactive Arguments ..." Succinct Non-interactive Arguments of Proximity Liyan Chen, Zhengzhong Jin, and Daniel Wichs (Tsinghua University, China; Northeastern University, USA; NTT Research, USA) Article Search
	Williams, Ryan	STOC '25: "Simulating Time with Square-Root ..." Simulating Time with Square-Root Space Ryan Williams (Massachusetts Institute of Technology, USA) Article Search STOC '25: "When Connectivity Is Hard, ..." When Connectivity Is Hard, Random Walks Are Easy with Non-determinism Dean Doron, Edward Pyne, Roei Tell, and Ryan Williams (Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada) Two fundamental problems on directed graphs are to decide s-t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s-t connectivity running in polynomial time and no(1) space, and no known algorithm for estimating the n-step random walk matrix running in non-deterministic logspace. We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms A1 and A2 such that for every graph G, either: A1(G) outputs the transitive closure of G in polynomial time and polylogarithmic space. A2(G) outputs an approximation of the n-step random walk matrix of G in non-deterministic logspace. As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch’s theorem can be non-trivially sped up, or randomized space can be almost completely derandomized. We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron–Pyne–Tell STOC 2024, Li–Pyne–Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron–Tell CCC 2024). To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel–Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen–Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting. Article Search
	Williams, Virginia Vassilevska	STOC '25: "All-Pairs Shortest Paths with ..." 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; INSAIT, Israel; INSAIT, Bulgaria; Massachusetts Institute of Technology, USA) Article Search STOC '25: "Output-Sensitive Approximate ..." 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) Article Search
	Woodruff, David P.	STOC '25: "Lifting Linear Sketches: Optimal ..." 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) Article Search
	Wootters, Mary	STOC '25: "List-Decoding Capacity Implies ..." 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) Article Search
	Wright, John	STOC '25: "The State Hidden Subgroup ..." The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement Adam Bouland, Tudor Giurgica-Tiron, and John Wright (Stanford University, USA; University of California at Berkeley, USA) Article Search
	Wu, David X.	STOC '25: "Weak Poincaré Inequalities, ..." 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) Article Search
	Wu, Kewen	STOC '25: "Locally Sampleable Uniform ..." 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) We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let f∶{0,1}m→{0,1}n be a Boolean function where each output bit of f depends only on O(1) input bits. Assume the output distribution of f on uniform input bits is close to a uniform distribution D with a symmetric support. We show that D is essentially one of the following six possibilities: (1) point distribution on 0n, (2) point distribution on 1n, (3) uniform over {0n,1n}, (4) uniform over strings with even Hamming weights, (5) uniform over strings with odd Hamming weights, and (6) uniform over all strings. This confirms a conjecture of Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). This is an extended abstract. The full paper can be found at https://arxiv.org/abs/2411.08183v1. An updated version with a stronger result can be found at https://arxiv.org/abs/2411.08183. Preprint STOC '25: "Almost Optimal Time Lower ..." 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) The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f:ℕ→ℕ, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1−o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1−o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing. Article Search
	Xi, Zoe	STOC '25: "All-Pairs Shortest Paths with ..." 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; INSAIT, Israel; INSAIT, Bulgaria; Massachusetts Institute of Technology, USA) Article Search
	Xia, Mingji	STOC '25: "The FPᴺᴾ versus #P Dichotomy ..." 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) Article Search
	Xiong, Zhongzheng	STOC '25: "Simple and Optimal Algorithms ..." 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) Article Search
	Xu, Jeff	STOC '25: "Sum-of-Squares Lower Bounds ..." Sum-of-Squares Lower Bounds for Coloring Random Graphs Aaron Potechin and Jeff Xu (University of Chicago, USA; Carnegie Mellon University, USA) Article Search
	Xu, Yinzhan	STOC '25: "Faster Weighted and Unweighted ..." 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) Article Search
	Xue, Jie	STOC '25: "Subexponential Parameterized ..." 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) Article Search STOC '25: "Efficiently Finding and Counting ..." 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) Article Search STOC '25: "Approximation Algorithms for ..." Approximation Algorithms for the Geometric Multimatching Problem Shinwoo An, Eunjin Oh, and Jie Xue (POSTECH, South Korea; New York University Shanghai, China) Article Search
	Yamakawa, Takashi	STOC '25: "Cryptographic Characterization ..." Cryptographic Characterization of Quantum Advantage Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa (Kyoto University, Japan; NTT, Japan) Article Search
	Yan, Shuyi	STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Yang, Chutong	STOC '25: "Omnipredicting Single-Index ..." Omnipredicting Single-Index Models with Multi-index Models Lunjia Hu, Kevin Tian, and Chutong Yang (Harvard University, USA; University of Texas at Austin, USA) Article Search
	Yang, Kuan	STOC '25: "Counting random 𝑘-SAT near ..." 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) Article Search
	Yao, Penghui	STOC '25: "On the Computational Power ..." 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) Article Search
	Ye, Christopher	STOC '25: "Faster Weighted and Unweighted ..." 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) Article Search
	Ye, Qi	STOC '25: "Stabilizer Bootstrapping: ..." 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) Article Search
	Yin, Longhui	STOC '25: "Breaking the Sorting Barrier ..." 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) Article Search
	Yin, Yitong	STOC '25: "Phase Transitions via Complex ..." Phase Transitions via Complex Extensions of Markov Chains Jingcheng Liu, Chunyang Wang, Yitong Yin, and Yixiao Yu (Nanjing University, China) Article Search STOC '25: "Rapid Mixing at the Uniqueness ..." Rapid Mixing at the Uniqueness Threshold Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang (Nanjing University, China; Georgia Institute of Technology, USA) Article Search STOC '25: "Counting random 𝑘-SAT near ..." 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) Article Search
	Yingchareonthawornchai, Sorrachai	STOC '25: "Approximating the Held–Karp ..." 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) Article Search STOC '25: "Deterministic Vertex Connectivity ..." 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) Article Search STOC '25: "Global vs. s-t Vertex Connectivity ..." Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, and Sorrachai Yingchareonthawornchai (KTH Royal Institute of Technology, Sweden; CWI, Netherlands; MPI-INF, Germany; Saarland University, Germany; University of Birmingham, UK; Hebrew University of Jerusalem, Israel; ETH Zurich, Switzerland) Article Search
	Yoo, Youngho	STOC '25: "Disjoint Paths Problem with ..." Disjoint Paths Problem with Group-Expressable Constraints Chun-Hung Liu and Youngho Yoo (Texas A&M University, USA) We study an extension of the k-Disjoint Paths Problem where, in addition to finding k disjoint paths joining k given pairs of vertices in a graph, we ask that those paths satisfy certain constraints expressable by abelian groups. We give an O(n8) time algorithm to solve this problem under the assumption that the constraint can be expressed as avoiding a bounded number of group elements; moreover, our O(n8) algorithm allows any bounded number of such constraints to be combined. Examples of group-expressable constraints include: (1) paths of length ℓ modulo m for any fixed integers ℓ and m with m ≥ 2, (2) paths passing through a bounded number of prescribed sets of edges and/or vertices, and (3) paths that are long detours (si-ti-paths with length at least (si,ti)+ℓ for any fixed integer ℓ). The k=1 case of the problem with modularity constraints solves a problem in [Arkin, Papadimitriou, and Yannakakis, J. ACM, (1991)] that has remained open for over 30 years. Our work also implies a polynomial time algorithm for testing the existence of a subgraph isomorphic to a subdivision of a fixed graph, where each path of the subdivision between branch vertices satisfies any combination of a bounded number of group-expressable constraints. This in particular gives a unified polynomial time algorithm for testing the existence of k disjoint cycles with such constraints. For example, we can test in polynomial time the existence of k disjoint cycles in surface-embedded graphs such that each cycle is non-homologous to 0 and is at least ℓ longer than the minimum length of such a cycle. In addition, our work implies similar results addressing edge-disjointness. Article Search
	Yu, Huacheng	STOC '25: "Lifting Linear Sketches: Optimal ..." 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) Article Search STOC '25: "Strong XOR Lemma for Information ..." Strong XOR Lemma for Information Complexity Pachara Sawettamalya and Huacheng Yu (Princeton University, USA) For any {0,1}-valued function f, its n-folded XOR is the function f⊕ n where f⊕ n(X1, …, Xn) = f(X1) ⊕ ⋯ ⊕ f(Xn). Given a procedure for computing the function f, one can apply a “naive” approach to compute f⊕ n by computing each f(Xi) independently, followed by XORing the outputs. This approach uses n times the resources required for computing f. In this paper, we prove a strong XOR lemma for information complexity in the two-player randomized communication model: if computing f with an error probability of O(n−1) requires revealing I bits of information about the players’ inputs, then computing f⊕ n with a constant error requires revealing Ω(n) · (I − 1 − on(1)) bits of information about the players’ inputs. Our result demonstrates that the naive protocol for computing f⊕ n is both information-theoretically optimal and asymptotically tight in error trade-offs. Preprint STOC '25: "Optimal Static Dictionary ..." 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) Article Search
	Yu, Nengkun	STOC '25: "Pauli Measurements Are Not ..." 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) Article Search
	Yu, Sophie H.	STOC '25: "From Signaling to Interviews ..." 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) Article Search
	Yu, Xifan	STOC '25: "Statistical Inference of a ..." 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) Article Search
	Yu, Yixiao	STOC '25: "Phase Transitions via Complex ..." Phase Transitions via Complex Extensions of Markov Chains Jingcheng Liu, Chunyang Wang, Yitong Yin, and Yixiao Yu (Nanjing University, China) Article Search
	Yue, Di	STOC '25: "Near-Optimal Dimension Reduction ..." 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) Article Search
	Yuen, Henry	STOC '25: "QMA vs QCMA and Pseudorandomness ..." QMA vs QCMA and Pseudorandomness Jiahui Liu, Saachi Mutreja, and Henry Yuen (Fujitsu Research, n.n.; Columbia University, USA) Article Search
	Yun, Zhiwei	STOC '25: "Quasi-Linear Size PCPs with ..." 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) Article Search
	Zadimoghaddam, Morteza	STOC '25: "The Cost of Consistency: Submodular ..." The Cost of Consistency: Submodular Maximization with Constant Recourse Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam (Google, Switzerland; Sapienza University of Rome, Italy; Google, USA; EPFL, Switzerland) Article Search
	Zamir, Or	STOC '25: "Optimality of Frequency Moment ..." Optimality of Frequency Moment Estimation Mark Braverman and Or Zamir (Princeton University, USA; Tel Aviv University, Israel) Estimating the second frequency moment of a stream up to (1±ε) multiplicative error requires at most O(logn / ε2) bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least Ω(logn + 1/ε2) space is needed. We prove a tight lower bound of Ω(log(n ε2 ) / ε2) for all ε = Ω(1/√n). Note that when ε>n−1/2 + c, where c>0, our lower bound matches the classic upper bound of AMS. For smaller values of ε we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound. Our lower bound holds also for the more general problem of p-th frequency moment estimation for the range of p∈ (1,2], giving a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments. Article Search
	Zehavi, Meirav	STOC '25: "Subexponential Parameterized ..." 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) Article Search STOC '25: "Efficiently Finding and Counting ..." 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) Article Search
	Zhandry, Mark	STOC '25: "A General Quantum Duality ..." 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) Article Search
	Zhang, Guochuan	STOC '25: "Long Arithmetic Progressions ..." Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses Lin Chen, Yuchen Mao, and Guochuan Zhang (Zhejiang University, China) Article Search
	Zhang, Hanwen	STOC '25: "Solving the Correlation Cluster ..." Solving the Correlation Cluster LP in Nearly Linear 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, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland) Article Search
	Zhang, Junkai	STOC '25: "Optimal Static Dictionary ..." 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) Article Search
	Zhang, Rachel Yun	STOC '25: "Explicit Two-Sided Vertex ..." 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) Article Search
	Zhang, Ruilong	STOC '25: "Constant Approximation for ..." 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) Article Search
	Zhang, Shuo	STOC '25: "Constant Approximation of ..." 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, China; Renmin University of China, China) Article Search
	Zhang, Tianyi	STOC '25: "Vizing’s Theorem in Near-Linear ..." Vizing’s Theorem in Near-Linear Time Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, and Tianyi Zhang (University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland) Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem. Preprint Video
	Zhang, Xinyuan	STOC '25: "Rapid Mixing at the Uniqueness ..." Rapid Mixing at the Uniqueness Threshold Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang (Nanjing University, China; Georgia Institute of Technology, USA) Article Search
	Zhang, Zhihan	STOC '25: "Stabilizer Bootstrapping: ..." 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) Article Search
	Zhang, Zihan	STOC '25: "Explicit Folded Reed-Solomon ..." 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) Article Search
	Zhao, Andrew	STOC '25: "Learning the Structure of ..." Learning the Structure of any Hamiltonian from Minimal Assumptions Andrew Zhao (Sandia National Laboratories, USA) We study the problem of learning an unknown quantum many-body Hamiltonian H from black-box queries to its time evolution e−i H t. Prior proposals for solving this task either impose some assumptions on H, such as its interaction structure or locality, or otherwise use an exponential amount of computational postprocessing. In this paper, we present algorithms to learn any n-qubit Hamiltonian, which do not need to know the Hamiltonian terms in advance, nor are they restricted to local interactions. Our algorithms are efficient as long as the number of terms m is polynomially bounded in the system size n. We consider two models of control over the time evolution: the first has access to time reversal (t < 0), enabling an algorithm that outputs an є-accurate classical description of H after querying its dynamics for a total of O(m/є) evolution time. The second access model is more conventional, allowing only forward-time evolutions; our algorithm requires O(||H||3/є4) evolution time in this setting. Central to our results is the recently introduced concept of a pseudo-Choi state of H. We extend the utility of this learning resource by showing how to use it to learn the Fourier spectrum of H, how to achieve nearly Heisenberg-limited scaling with it, and how to prepare it even under our more restricted access models. Article Search
	Zhou, Kangjie	STOC '25: "Discrepancy Algorithms for ..." Discrepancy Algorithms for the Binary Perceptron Shuangping Li, Tselil Schramm, and Kangjie Zhou (Stanford University, USA; Columbia University, USA) Article Search
	Zhou, Renfei	STOC '25: "Optimal Non-oblivious Open ..." Optimal Non-oblivious Open Addressing Michael A. Bender, William Kuszmaul, and Renfei Zhou (Stony Brook University, USA; Carnegie Mellon University, USA) Article Search STOC '25: "Optimal Static Dictionary ..." 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) Article Search
	Zhou, Samson	STOC '25: "Lifting Linear Sketches: Optimal ..." 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) Article Search
	Zhu, Xiaoyi	STOC '25: "Simple and Optimal Algorithms ..." 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) Article Search
	Zuckerman, David	STOC '25: "Linear Hashing Is Good ..." Linear Hashing Is Good Michael Jaber, Vinayak M. Kumar, and David Zuckerman (University of Texas at Austin, USA) Article Search
	Zuiddam, Jeroen	STOC '25: "Computing Moment Polytopes ..." 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 (University of Amsterdam, Netherlands; Ruhr University Bochum, Germany; University of Copenhagen, Denmark) Article Search STOC '25: "Asymptotic Tensor Rank Is ..." Asymptotic Tensor Rank Is Characterized by Polynomials Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Peter Vrana, and Jeroen Zuiddam (University of Copenhagen, Denmark; University of Amsterdam, Netherlands; Budapest University of Technology and Economics, Hungary) Article Search