FOCS 2026 · public versions

We prove that the distortion of any embedding into $L_1$ of the transportation cost space or earth mover distance over a $d$-dimensional grid $\{1,\dots m\}^d$ is $Ω(\log N)$, where $N$ is the number of vertices and the implicit constant is universal (in particular, independent of dimension). This lower bound matches the universal upper bound $O(\log N)$ holding for any $N$-point metric space. Our proof relies on a new Sobolev inequality for real-valued functions on the grid, based on random measures supported on dyadic cubes.

Menger's Theorem is a fundamental result in graph theory. It states that if in a graph $G$ with distinguished sets of terminal vertices $S$ and $T$ there are no $k$ pairwise vertex-disjoint $S$-$T$ paths, then there is a set of less than $k$ vertices that intersects every $S$-$T$ path. In this work, we give a coarse variant of this result for planar and bounded genus graphs. Precisely, we prove that for every surface $Σ$ there is a function $f\colon \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ such that for every pair of integers $d,k\in \mathbb{N}$ and a $Σ$-embeddable graph $G$ with distinguished sets of terminal vertices $S$ and $T$, if $G$ does not contain a family of $k$ $S$-$T$ paths that are pairwise at distance larger than $d$, then there is a set $X$ consisting of at most $f(d,k)$ vertices of $G$ such that every $S$-$T$ path is at distance at most $d$ from a vertex of $X$. This partially answers questions of Nguyen, Scott, and Seymour [arXiv:2508.14332], who proved that such a result cannot hold in general graphs.

A key ingredient of our proof is a structure theorem from the developing “colorful” graph minor theory, where the focus is on studying the structure in a graph relative to some fixed subsets of annotated vertices. In our case, these annotated vertices are $S$ and $T$.

We study learning-to-sample – a basic algorithmic task underlying generative modeling – for Ising models, a standard testbed for algorithmic ideas in both theoretical computer science and machine learning. Given i.i.d. samples of an unknown target distribution, the goal of learning-to-sample is to learn a computationally efficient generation procedure that produces new samples following approximately the same distribution. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold $λ_{\max}(J)-λ_{\min}(J)=1$, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters. Combined with results of [AJKPV24,KLV25] showing tractability of learning-to-sample below the spectral threshold, this establishes a sharp computational phase transition at the spectral threshold. Moreover, combined with prior results on parameter learning for bounded-width Ising models [KM17,WSD19,VML20], this shows that learning-to-sample can be more difficult than parameter learning. Finally, we show that any efficient learner for these hard instances exhibits a natural memorization-hallucination dichotomy: the learner must either output configurations that, after a simple transformation, match the (transformed) training data or place substantial mass on configurations of negligible probability under the target distribution.

We prove a lower bound of $Ω\left(n^{1.5}\right)$ for the number of product gates in non-commutative arithmetic circuits for an explicit $n$-variate degree-$n$ polynomial $f_{n}$ (over every field).

We observe that this implies that over certain non-commutative rings $R$, any arithmetic circuit that computes the induced polynomial function $f_{n}: R^n \rightarrow R$, using the ring operations of addition and multiplication in $R$, requires at least $Ω\left(n^{1.5}\right)$ multiplications.

More generally, for any $d\geq 2$ and sufficiently large $n$, we obtain a lower bound of $Ω\left(d\sqrt{n}\right)$ for $n$-variate degree-$d$ polynomials, for both these models.

Prior to our work, the only known lower bounds for the size of non-commutative circuits, or for the size of arithmetic circuits over any ring, were slightly super-linear in $\max\{n,d\}$: $Ω\left(n\log d\right)$ by Baur and Strassen, and $Ω\left(d\log n\right)$ by Nisan. (Nisan's bound was proved for non-commutative arithmetic circuits and implies a bound for arithmetic circuits over non-commutative rings by our observation).

A furthest neighbor data structure on a metric space $(V,\mathrm{dist})$ and a set $P \subseteq V$ answers the following query: given $v \in V$, output $p \in P$ maximizing $\mathrm{dist}(v,p)$; in the approximate version, it is allowed to report any $p \in P$ with $\mathrm{dist}(v,p) \geq (1-\varepsilon)\max_{p' \in P} \mathrm{dist}(v,p')$ for an accuracy parameter $\varepsilon \in (0,1)$. A particular type of approximate furthest neighbor data structure is an $\varepsilon$-coreset: a small subset $Q \subseteq P$ such that for every query $v \in V$ there is a feasible answer $p \in Q$.

Our main result is that in planar metrics there always exists an $\varepsilon$-coreset for furthest neighbors of size bounded polynomially in $(1/\varepsilon)$. This improves upon an exponential bound of Bourneuf and Pilipczuk [SODA'25] and resolves an open problem of de Berg and Theocharous [SoCG'24] for the case of polygons with holes.

On the technical side, we develop a connection between $\varepsilon$-coreset for furthest neighbors and an invariant of a metric space that we call an $\varepsilon$-comatching index – a sibling of $\varepsilon$-(semi-)ladder index, a.k.a, $\varepsilon$-scatter dimension, as defined by Abbasi et al [FOCS'23]. While the $\varepsilon$-(semi-)ladder index of planar metrics admits an exponential lower bound, we show that the $\varepsilon$-comatching index of planar metrics is polynomial, all in $1/\varepsilon$. The exponential separation between $\varepsilon$-(semi-)ladder and $\varepsilon$-comatching is rather surprising, and the proof is the main technical contribution of our work.

Given a graph and a pair of terminals $s$, $t$, the next-to-shortest path problem asks for an $s\!\to \!t$ (simple) path that is shortest among all not shortest $s\!\to \!t$ paths (if one exists). This problem was introduced in 1996, and soon after was shown to be NP-complete for directed graphs with non-negative edge weights, leaving open the case of positive edge weights. Subsequent work investigated this open question, and developed polynomial-time algorithms for the cases of undirected graphs and planar directed graphs. In this work, we resolve this nearly 30-year-old open problem by providing an algorithm for the next-to-shortest path problem on directed graphs with positive edge weights.

Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization. However, this expressivity comes at the cost of computational hardness. As a result, most research has focused on carving out specific subclasses that elude those intractability barriers. A classical property that goes back to the 1960s is the Minty condition, which postulates that the Minty VI (MVI) problem admits a solution.

In this paper, we establish the first polynomial-time algorithm – with complexity growing polynomially in the dimension $d$ and $\log(1/ε)$ – for solving $ε$-SVIs for Lipschitz continuous mappings under the Minty condition. Prior approaches either incurred an exponentially worse dependence on $1/ε$ (and other natural parameters of the problem) or made more restrictive assumptions, such as monotonicity. To do so, we introduce a new variant of the ellipsoid algorithm whereby separating hyperplanes are obtained after taking a descent step from the center of the ellipsoid. It succeeds even though the set of SVIs can be nonconvex and not fully dimensional. Moreover, when our algorithm is applied to an instance with no MVI solution and fails to identify an SVI solution, it produces a succinct certificate of MVI infeasibility. We also show that deciding whether the Minty condition holds is $\mathsf{coNP}$-complete, thereby establishing that the disjunction of those two problems is polynomial-time solvable even though each problem is individually intractable.

We provide several extensions and new applications of our main results. Most notably, we obtain the first polynomial-time algorithms for computing Nash equilibria in multi-player harmonic games. Finally, in two-player general-sum concave games, we give the first polynomial-time algorithm that outputs either a Nash equilibrium or a strict coarse correlated equilibrium.

Estimating local observables in Gibbs states is a central problem in quantum simulation. While this task is BQP-complete at asymptotically low temperatures, the possibility of quantum advantage at constant temperature remains open. The Sachdev-Ye-Kitaev (SYK) model is a natural candidate: at any constant temperature, its Gibbs states have polynomial quantum circuit complexity and are not described by Gaussian states. Rigorous analyses of the SYK model are difficult due to the failure of known techniques using random matrix theory, cluster expansions, and rigorous formulations of the quantum path integral and replica trick. Despite this, we give a rigorous proof of a quasipolynomial-time classical algorithm that estimates SYK local thermal expectations at sufficiently high constant temperature. Our result introduces a new Wick-pair cluster expansion that we expect to be broadly useful for disordered quantum many-body systems.

We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of $m$ degree-$d$ polynomials and any convex set ${H} \subseteq \mathbb{R}_{\ge0}^n$, we construct an $ε$-Cover of the joint value set $\{(f_1(x), \dots, f_m(x)) : x \in {H}\}$ in the $\ell_\infty$-norm. This cover is of size $n^{O(\log(mn)/ε^2)}$, provided the polynomials have constant range over the smallest $\ell_1$-ball inscribing ${H}$. Our approach extends classical net-based sparsifications for linear functions (e.g., Lipton, Markakis, and Mehta [2003]) to arbitrary families of constant-degree polynomials over general convex sets. We use a two-step scheme: first, we construct a quasi-polynomial pre-cover of the family on the smallest $\ell_1$-ball containing ${H}$ by using a concentration argument and leveraging a connection between Bernstein approximation and multinomial distributions; we then compress the pre-cover to ${H}$ by using a recursive degree reduction and feasibility programs anchored at points of the pre-cover. The existence of these covers immediately yields a unified framework for Quasi-Polynomial Time Approximation Schemes (QPTAS) across a wide range of a problems, including fixed-degree polynomial minimization over polyhedral sets, Constraint Satisfaction Problems (CSPs), Free Games, variational inequalities with polynomial operators (which implies guarantees for local Nash equilibria in polynomial games), and additive approximation for normalized densest $k$-subhypergraph on $O(1)$-uniform hypergraphs.

We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust $(1+ε)$-approximation for the second moment $F_2$ in polylogarithmic space, achieving high accuracy for other frequency moments remained a major open question; for $p\in[0,2)$, including the fundamental distinct elements problem ($F_0$), only constant-factor approximations were known in sublinear space. We close this gap, showing that $(1+ε)$-approximate robustness can be achieved in polylogarithmic space for all $p\in[0,2]$. Our approach generalizes the estimator-corrector-learner framework to non-Hilbert spaces by dynamically maintaining implicit isometric embeddings into $L_2$ and performing regularized kernel ridge regression over adaptively discovered hard queries, yielding the first insertion-deletion algorithms that approximate: (1) the $p$-th frequency moment $F_p$ up to a $(1+ε)$-factor in poly$(1/ε, \log n)$ space for all $p\in[0,2]$, including the support size $F_0$, (2) metric and information-theoretic quantities, including the Earth Mover Distance (EMD) and $k$-median clustering cost over $[Δ]^d$ up to an $O(d \log Δ)$-factor, and the Shannon entropy up to an $ε$-additive error, and (3) non-normed symmetric losses defined by Bernstein functions up to a $(1+ε)$-factor. For the $F_p$ moments, our algorithm is optimal up to poly$(1/ε, \log n)$ factors. Furthermore, we establish a weak equivalence between classical oblivious sketching and adversarial robustness. We prove that for any sub-multiplicative norm, the existence of an efficient classical linear sketch is equivalent to the existence of an efficient robust turnstile algorithm, up to polynomial factors, formalizing $L_1$ embeddability as the fundamental mechanism governing both models.

Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice.

In undirected unweighted graphs, while computing single-source shortest path (SSSP) requires $O(n^2)$ time in dense graphs, all-pairs shortest paths (APSP) can be computed in $\hat{O}(n^ω) = O(n^{2.372})$ time [Seidel '95] providing significant savings over running $n$ SSSP instances separately. However, if one needs to compute multiple-source shortest paths (MSSP) from a set of $n^σ$ vertices, the previously best known running time was $\hat{O}(\min\{n^ω, n^{2 + σ}\})$: either compute APSP or run SSSP from each source. On the other hand, MSSP is only as hard as computing Boolean matrix product (BMM) between an $n^σ\times n$ matrix and $n \times n$ matrix, leaving a significant gap. Our first main result is an almost optimal algorithm for MSSP on undirected unweighted graphs running in $\hat{O}(n^{ω(σ, 1, 1)})$ time, which gives a smooth interpolation between the SSSP and APSP algorithms. The main technical tool behind our result is a novel graph decomposition, which may be of independent interest.

Next, we study the multiple-source reachability problem, where we need to determine whether a given set of $n^σ$ vertices can reach each of the vertices in a given directed graph. Multiple-source reachability can also be solved in $\hat{O}(\min\{n^ω, n^{2 + σ}\})$ time, with the same lower bound from rectangular BMM. We give an optimal algorithm that runs in $\hat{O}(n^{ω(σ, 1, 1)})$ time, again matching the running time for BMM. Our algorithm for multiple-source reachability can be generalized to MSSP on DAGs. As an application, we provide an $O(n^{2.084})$ time algorithm for computing an $\widetilde{O}(n)$-size shortcut set that reduces diameter to $O(n^{1/3})$.

We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $Ω((\log n / \log\log n)^2)$ for the Multiphase Problem of Pătraşcu [STOC 2010] (instantiated with Inner Product over $\mathbb{F}_2$). This matches the celebrated barrier for weighted problems established by Larsen [STOC 2012] and closes the gap left by the $Ω(\log^{1.5} n)$ Boolean bound of Larsen, Weinstein, and Yu [STOC 2018].

The previous barrier was methodological: all prior works relied on “one-way” communication games, where the inability to verify query simulations necessitated complex machinery (such as the Peak-to-Average Lemma) that hit a hard ceiling at $\log^{1.5} n$.

Our key contribution is conceptual: We introduce a 2.5-round Multiphase Communication Game that augments the standard one-way model with a verification round, where Bob confirms the consistency of Alice's simulation against the actual memory. This simple, qualitative change allows us to bypass technical barriers and obtain the optimal bound directly.

As a consequence, our analysis naturally extends to other hard Boolean functions, offering a general recipe for translating discrepancy lower bounds into $Ω((\log n / \log\log n)^2)$ dynamic Boolean data structure lower bounds.

We also argue that this result likely represents the structural ceiling of the Chronogram framework initiated by Fredman and Saks [STOC 1989]: any $ω(\log^2 n)$ lower bound would require either fundamentally new techniques or major circuit complexity breakthroughs.

A generalized polymorphism of a predicate $P \subseteq \{0,1\}^m$ is a tuple of functions $f_1,\dots,f_m\colon \{0,1\}^n \to \{0,1\}$ satisfying the following property: If $x^{(1)},\dots,x^{(m)} \in \{0,1\}^n$ are such that $(x^{(1)}_i,\dots,x^{(m)}_i) \in P$ for all $i$, then also $(f_1(x^{(1)}),\dots,f_m(x^{(m)})) \in P$.

We show that if $f_1,\dots,f_m$ satisfy this property for most $x^{(1)},\dots,x^{(m)}$ (as measured with respect to an arbitrary full support distribution $μ$ on $P$), then $f_1,\dots,f_m$ are close to a generalized polymorphism of $P$ (with respect to the marginals of $μ$).

Our main result generalizes several results in the literature: linearity testing, quantitative Arrow theorems, approximate intersecting families, AND testing, and more generally $f$-testing.

We show an $\widetilde{O}(m^{1.5} ε^{-1})$ time algorithm that on a graph with $m$ edges and $n$ vertices outputs its spanning tree count up to a multiplicative $(1+ε)$ factor with high probability, improving on the previous best runtime of $\widetilde{O}(m + n^{1.875}ε^{-7/4})$ in sparse graphs. While previous algorithms were based on computing Schur complements and determinantal sparsifiers, our algorithm instead repeatedly removes sets of uncorrelated edges found using the electrical flow localization theorem of Schild-Rao-Srivastava [SODA 2018].

We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and boson sampling (Aaronson and Arkhipov '11; Eldar and Mehraban '17). Barvinok's interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial $\mathrm{per}(zJ + W)$, where $J$ is the all-ones matrix and $W$ is a random matrix with independent mean-zero entries.

We show that when the entries of $W$ are standard complex Gaussians, all zeros of the random polynomial $\mathrm{per}(zJ + W)$ lie within a disk of radius $\tilde{O}(n^{-1/3})$, which yields an approximation algorithm when the bias of the entries is $\tildeΩ(n^{-1/3})$. Previously, there were no efficient algorithms at biases smaller than $1/\mathrm{polylog}(n)$, and it was unknown whether there typically exist zeros $z$ with $|z| \ge 1$. As a complementary result, we show that the bulk of the zeros, namely $(1 - ε)n$ of them, have magnitude $Θ(n^{-1/2})$. This prevents our interpolation method from contradicting the conjectured average-case hardness of approximating the permanent. We also establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. In addition, we prove universality results establishing zero-free regions for random matrices $W$ with i.i.d. subexponential entries.

We study algorithmic matroid intersection coloring. Given $k$ matroids on a common ground set $U$ of $n$ elements, the goal is to partition $U$ into the fewest number of color classes, where each color class is independent in all matroids. It is known that $2χ_{\max}$ colors suffice to color the intersection of two matroids, $(2k-1)χ_{\max}$ colors suffice for general $k$, where $χ_{\max}$ is the maximum chromatic number of the individual matroids. However, these results are non-constructive, leveraging techniques such as topological Hall's theorem and Sperner's Lemma.

We provide the first polynomial-time algorithms to color two or more general matroids where the approximation ratio depends only on $k$ and, in particular, is independent of $n$. For two matroids, we constructively match the $2χ_{\max}$ existential bound, yielding a 2-approximation for the Matroid Intersection Coloring problem. For $k$ matroids we achieve a $(k^2-k)χ_{\max}$ coloring, which is the first $O(1)$-approximation for constant $k$. Our approach introduces a novel matroidal structure we call a flexible decomposition. We use this to formally reduce general matroid intersection coloring to graph coloring while avoiding the limitations of partition reduction techniques, and without relying on non-constructive topological machinery.

Furthermore, we give a fully polynomial randomized approximation scheme (FPRAS) for coloring the intersection of two matroids when $χ_{\max}$ is large. This yields the first polynomial-time constructive algorithm for an asymptotic variant of Rota's Basis Conjecture. This constructivizes Montgomery and Sauermann's recent asymptotic breakthrough and generalizes it to arbitrary matroids.

We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in $n^{2+o(1)}$ time by refining the shortcutting procedure introduced in Li, Li, Rao, and Zhang (2026).

A connectivity function on a finite set $V$ is a symmetric submodular function $f \colon 2^V \to \mathbb{Z}$ with $f(\emptyset)=0$. We prove that finding a branch-decomposition of width at most $k$ for a connectivity function given by an oracle is fixed-parameter tractable (FPT), by providing an algorithm of running time $2^{O(k^2)} γn^6 \log n$, where $γ$ is the time to compute $f(X)$ for any set $X$, and $n = |V|$. This improves the previous algorithm by Oum and Seymour [J. Combin. Theory Ser. B, 2007], which runs in time $γn^{O(k)}$. Our algorithm can be applied to rank-width of graphs, branch-width of matroids, branch-width of (hyper)graphs, and carving-width of graphs. This resolves an open problem asked by Hliněný [SIAM J. Comput., 2005], who asked whether branch-width of matroids given by the rank oracle is fixed-parameter tractable. Furthermore, our algorithm improves the best known dependency on $k$ in the running times of FPT algorithms for graph branch-width, rank-width, and carving-width.

We prove a strongly polynomial bound on the circuit diameter of polyhedra, resolving the circuit analogue of the polynomial Hirsch conjecture. Specifically, we show that the circuit diameter of a polyhedron $P = \{x\in \mathbb{R}^n:\, A x = b, \, x \ge 0\}$ with $A\in\mathbb{R}^{m\times n}$ is $O(m^2 \log m)$. Our construction yields monotone circuit walks, giving the same bound for the monotone circuit diameter.

The circuit diameter, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015), is a natural relaxation of the combinatorial diameter that allows steps along circuit directions rather than only along edges. All prior upper bounds on the circuit diameter were only weakly polynomial. Finding a circuit augmentation algorithm that matches this bound would yield a strongly polynomial time algorithm for linear programming, resolving Smale's 9th problem.

A classical obfuscator for quantum circuits is a classical program that, given the classical description of a quantum circuit $Q$, outputs the classical description of a functionally equivalent quantum circuit $\hat{Q}$ that hides as much as possible about $Q$. Previously, the only known feasibility result for classical obfuscation of quantum circuits (Bartusek and Malavolta, ITCS 2022) was limited to circuits that always reject. On the other hand, if the obfuscator is allowed to compile the quantum circuit $Q$ into a quantum state $|\hat{Q}\rangle$, there exist feasibility results for obfuscating all pseudo-deterministic quantum circuits (Bartusek, Kitagawa, Nishimaki and Yamakawa, STOC 2023, Bartusek, Brakerski and Vaikuntanathan, STOC 2024), and all unitaries (Huang and Tang, FOCS 2025).

We show that (relative to a classical oracle) there exists a classical obfuscator for all pseudo-deterministic quantum circuits. We do this by giving the first construction of a compact quantum fully-homomorphic encryption (QFHE) scheme that supports public verification of (pseudo-deterministic) quantum evaluation, relative to a classical oracle.

To construct our QFHE scheme, we improve on the approach of Bartusek, Kitagawa, Nishimaki and Yamakawa (STOC 2023), which required ciphertexts that are both quantum and non-compact due to the use of quantum coset states and their publicly-verifiable properties. We introduce new techniques for analyzing coset states that can be generated “on the fly”, by proving new cryptographic properties of the one-shot signature scheme of Shmueli and Zhandry (CRYPTO 2025). Our techniques allow us to produce QFHE ciphertexts that are purely classical, compact, and publicly-verifiable. This also yields the first classical verification of quantum computation protocol for BQP that simultaneously satisfies blindness and public-verifiability.

Given algorithms $A_1,A_2$ running in logspace and linear time, there are two basic ways to compute the composition $x\rightarrow A_2(A_1(x))$. Applying naive composition gives an algorithm in linear time but linear space, while applying emulative composition (i.e. the composition of space-bounded algorithms) gives an algorithm in logarithmic space but quadratic time. Such time overheads are extremely common while designing low-space algorithms.

A natural question is whether one can enjoy the best of both worlds: for every $A_1,A_2$, is there a routine to compute $A_2\circ A_1$ in linear time and in small space? We prove that:

1: For linear time algorithms, this is unconditionally impossible – any space-efficient composition must be polynomially slower than the naive algorithm.

2: Extending the unconditional lower bound in either one of many different ways (e.g., to algorithms running in large polynomial time, or to a lower bound for $k$-fold composition that increases as $n^{\omega_k(1)}$) would imply breakthrough algorithms for a major question in complexity theory, namely derandomization of probabilistic logspace.

The main conceptual contribution in our work is the connection between three questions: the complexity of composition, time-space tradeoffs for deterministic algorithms, and derandomization of probabilistic logspace. This connection gives additional motivation to study time-space tradeoffs, even under complexity-theoretic assumptions, and the motivation is strengthened by the fact that the tradeoffs required in our results are very relaxed (i.e., super-linear tradeoffs for deterministic algorithms).

To prove our results we develop the technical toolkit in an ongoing line of works studying pseudorandomness for low-space algorithms, and as a by-product, we improve several very recent results in this line of work. For example, we show a new “win-win pair of low-space algorithms”, extending the construction of (Doron, Pyne, Tell, Williams, STOC 2025) to more general functions and eliminating a previously large polynomial runtime overhead; we reduce the task of derandomizing low-space algorithms to the seemingly tractable task of proving lower bounds for uniform Read-Once Branching Programs; and we introduce two highly efficient targeted pseudorandom generators, which use optimized versions of previous generators as building-blocks.

Improvements to exposition and new statement of Theorem 1.7

The suffix array ($\SA$) and inverse suffix array ($\ISA$) are fundamental data structures in string algorithms. Given a text of length $n$ over an integer alphabet of size $σ$, explicitly storing these structures requires $Θ(n\log n)$ bits, motivating compressed representations that approach the information-theoretic minimum of $n\logσ$ bits. Two landmark solutions are the FM-index, which achieves succinct space and supports $\SA$ and $\ISA$ queries in roughly logarithmic time, and the Compressed Suffix Array (CSA), which uses $O(n\logσ)$ bits and answers both queries in $O(\log_σ^εn)$ time. Nearly all subsequent compressed indexes, including entropy-compressed and repetitiveness-aware variants, support $\SA$ and $\ISA$ using essentially the same techniques, leading to similar space–time trade-offs. This raises a fundamental question: under the same asymptotic space bound, do $\SA$ and $\ISA$ have the same inherent query complexity? We provide evidence that this symmetry is not intrinsic. Under an $O(n\logσ)$-bit space bound, we show that $\SA$ queries are unlikely to admit $\log^{o(1)} n$ query time, suggesting that improving the classical CSA bound would require a major breakthrough. In contrast, we present a new encoding supporting $\ISA$ queries in $O(τ+\log\log n/\log\logσ)$ time using $(1+1/τ+o(1))n\logσ$ bits, for any $τ\ge1$. Our main insight is that the $\LF$-mapping, traditionally implemented using the Burrows–Wheeler Transform, can be adapted to support $\ISA$ queries directly from the packed text, eliminating the need to store the BWT while achieving substantially faster query times.

In the vertex connectivity augmentation problem, we are given an undirected $n$-vertex graph $G$, a set of links $L \subseteq \binom{V(G)}{2} \setminus E(G)$, and integers $λ$ and $k$. The task is to insert at most $k$ links from $L$ to $G$ to make $G$ $λ$-vertex-connected. We show that the problem is fixed-parameter tractable (FPT) when parameterized by $λ$ and $k$, by giving an algorithm with running time $2^{O(k \log (k + λ))} n^{O(1)}$. This improves upon a recent result of Carmesin and Ramanujan [SODA'26], who showed that the problem is FPT parameterized by $k$ but only when $λ\le 4$.

We also consider the analogous edge connectivity augmentation problem, where the goal is to make $G$ $λ$-edge-connected. We show that the problem is FPT when parameterized by $k$ only, by giving an algorithm with running time $2^{O(k \log k)} n^{O(1)}$. Previously, such results were known only under additional assumptions on the edge connectivity of $G$.

One of the central open problems to classify the computational complexity of finite-domain constraint satisfaction problems within P is to prove better algorithmic results for CSPs with a Maltsev polymorphism; we do not even know whether these CSPs are in NC. Relatedly, the descriptive complexity of these problems is open as well. An important special case, previously studied by Carbonell from the perspective of uniform polynomial time-algorithms, are CSPs with a conservative Maltsev polymorphism. We show that for every finite structure B with a conservative Maltsev polymorphism, the CSP for B can be solved by a symmetric linear Z2-Datalog program, and in particular is in the complexity class parity-L. Previously, the best known algorithms just showed containment in P. In our proof we develop a structure theory for conservative Maltsev algebras which might be of independent interest.

We present explicit quantum channels with strictly sub-additive minimum output Rényi entropy for all $p>1$, improving upon prior constructions which handled $p>2$. Our example is provided by explicit constructions of linear subspaces with high geometric measure of entanglement. This construction applies in both the bipartite and multipartite settings. As further applications, we use our construction to find entanglement witnesses with many highly negative eigenvalues, and to construct entangled mixed states that remain entangled after perturbation.

We study the additive structure of dense subset sum in multi-dimension, and use the structure to develop efficient algorithms for the dense subset sum problem. More precisely, given a set $A$ of $n$ vectors in the $d$-dimensional hyperrectangle $[N_1]\times [N_2]\times\cdots\times [N_d]$, we study the structure of $\mathcal{S}(A)$, which is the set of all subset sums of $A$. We focus on the dense regime of the problem where $n \gg \sqrtΦ$ and $Φ= N_1 \times \cdots \times N_d$.

We show that for any constant $d\geq 1$, if $n \gg \sqrtΦ$, then $\mathcal{S}(A)$ contains a long generalized progression in multi-dimension. If we further have that no non-trivial lattice can contain the majority of $A$, then $\mathcal{S}(A)$ contains all the integer points in the zonotope $\{x_1\vec{a}_1 + \cdots + x_n\vec{a}_n: o(1)\leq x_j \leq 1-o(1), x_j \in \mathbb{R}\}$. Compared to the previous results for $d \geq 2$, our result significantly reduces the density threshold and enlarges the region inside which all the integer points belong to $\mathcal{S}(A)$. Also, it matches the bound for the 1-dimensional case.

Using our combinatorics result, we also develop an $\tilde{O}(n)$-time algorithm for the dense subset sum problem in multi-dimension.

We show that, assuming NP $\not\subseteq$ $\cap_{δ> 0}$DTIME$\left(\exp{n^δ}\right)$, the shortest vector problem for lattices of rank $n$ in any finite $\ell_p$ norm is hard to approximate within a factor of $2^{(\log n)^{1 - o(1)}}$, via a deterministic reduction. Previously, for the Euclidean case $p=2$, even hardness of the exact shortest vector problem was not known under a deterministic reduction.

We study the Kaufman–Oppenheim coset complexes (STOC 2018, Eur. J. Comb. 2023), which have an elementary and strongly explicit description. Answering an open question of Kaufman, Oppenheim, and Weinberger (STOC 2025), we show that they support sparse direct-product testers in the low soundness regime. Our proof relies on the HDX characterization of agreement testing by Bafna–Minzer and Dikstein–Dinur (both STOC 2024), the recent result of Kaufman et al., and follows techniques from Bafna–Lifshitz–Minzer and Dikstein–Dinur–Lubotzky (both FOCS 2024). Ultimately, the task reduces to showing dimension-independent coboundary expansion of certain $2$-dimensional subcomplexes of the KO complex; following the “Dehn method” of Kaufman and Oppenheim (ICALP 2021), we do this by establishing efficient presentation bounds for certain matrix groups over polynomial rings.

As shown by Bafna, Minzer, and Vyas (STOC 2025), a consequence of our direct-product testing result is that the Kaufman–Oppenheim complexes can also be used to obtain PCPs with arbitrarily small constant soundness and quasilinear length. Thus the use of sophisticated number theory and algebraic group-theoretic tools in the construction of these PCPs can be avoided.

We prove that, up to subpolynomial or polylogarithmic factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs. Namely, we show how given an $n$-vertex weighted directed planar graph $G$, one can compute in $n^{1+o(1)}$ time and space a representation of $G$ from which one can extract the exact distance between any two vertices of $G$ in $\log^{2+o(1)}(n)$ time. Previously, it was only known how to construct oracles with these space and query time in $n^{3/2+o(1)}$ time [STOC 2019, SODA 2021, JACM 2023]. We show how to construct these oracles in $n^{1+o(1)}$ time.

We give a poly$(s,1/ε)$-query algorithm for testing whether an unknown and arbitrary function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-term DNF, in the challenging relative-error framework for Boolean function property testing that was recently introduced and studied in a number of works [CDH+25b, CPPS25a, CPPS25b, CDH+25a]. This gives the first example of a rich and natural class of functions which may depend on a super-constant number of variables and yet is efficiently testable in the relative-error model with constant query complexity.

A crucial new ingredient enabling our approach is a novel decomposition of any $s$-term DNF formula into “local clusters” of terms. Our results demonstrate that this new decomposition can be usefully exploited for algorithms even when the $s$-term DNF is not explicitly given; we believe that this decomposition may have applications in other contexts.

We show that one-way functions suffice for constructing very efficient argument systems for proving the correctness of bounded-space computations. Taking $\kappa$ to be a cryptographic security parameter and $n$ to be the input length, our argument system applies to general computations running in time $T$ and space $S$. The protocol has ${\mathit{polylog}}(T)$ rounds, the communication complexity is $S\cdot {\mathit{poly}}({\mathit{log}}(T),\kappa)$ and the verifier runtime is $(S + n) \cdot {\mathit{poly}}({\mathit{log}}(T),\kappa)$. In particular, the complexity of the verifier is only poly-logarithmic in the computation length. The honest prover runs in time ${\mathit{poly}}(T,\kappa)$, so the protocol is doubly-efficient. If the one-way function is secure against $\lambda(\kappa)$-size adversaries, then the argument system is sound against cheating provers of size $\lambda(\kappa)/{\mathit{poly}}(T)$.

Prior to this work, doubly-efficient argument systems with poly-logarithmic dependence on $T$ required assuming (at least) the existence of collision-resistant hash functions [Kilian, STOC 1992]. For unconditionally sound doubly-efficient protocols, the RRR protocol for bounded-space computations [Reingold, Rothblum and Rothblum, STOC 2016] has communication and verification complexities that grow with $T^{\sigma}$ for an arbitrarily small constant $\sigma > 0$.

We study the computational complexity of estimating the normalized trace $2^{-n}Tr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$.

We show that if $f(x)$ is a continuous function with approximate degree $Ω({\rm poly}(n))$, then estimating $2^{-n}Tr[f(A)]$ up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of $f(x)$. This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when $A$ is sparse, the classical query complexity of this problem is exponential in the approximate degree, assuming a conjectured lower bound for a trace variant of the $k$-Forrelation problem in the DQC1 query model. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and, conditionally, the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.

Given a small random sample of $n$-bit strings labeled by an unknown Boolean function, which properties of this function can be tested computationally efficiently? We show an equivalence between properties that are efficiently testable from few samples and properties with structured symmetry, which depend only on the function's average values on an efficiently computable partition of the domain. Without the efficiency constraint, a similar characterization in terms of unstructured symmetry was obtained by Blais and Yoshida (2019). We also give a function testing analogue of the classic characterization of testable graph properties in terms of regular partitions, as well as a sublinear time and differentially private algorithm to compute concise summaries of such partitions of graphs. Finally, we tighten a recent characterization of the computational indistinguishability of product distributions, which encompasses the related task of efficiently testing which of two candidate functions labeled the observed samples. Essential to our proofs is the following observation of independent interest: Every randomized Boolean function, no matter how complex, admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from reality with constant advantage, even by polynomially larger distinguishers. This surprising fact is implicit in a theorem of Dwork et al. (2021) in the context of algorithmic fairness, but its complexity-theoretic implications were not previously explored. We give a new proof of this lemma using an iteration technique from the graph regularity literature, and we observe that a subtle quantifier switch allows it to powerfully circumvent known barriers to improving the landmark complexity-theoretic regularity lemma of Trevisan, Tulsiani, and Vadhan (2009).

Given a channel with length-$n$ inputs and outputs over the alphabet $\{0,1,\ldots,q-1\}$, and of which a fraction $\varrho \in (0,1-1/q)$ of symbols can be arbitrarily corrupted by an adversary, a fundamental problem is that of communicating at rates close to the information-theoretically optimal values, while ensuring the receiver can infer that the transmitter's message is from a “small" set. While the existence of such codes is known, and constructions with computationally tractable encoding/decoding procedures are known for large $q$, we provide the first schemes that attain this performance for any $q \geq 2$, as long as low-rate feedback (asymptotically negligible relative to the number of transmissions) from the receiver to the transmitter is available. For any sufficiently small $\varepsilon > 0$ and $\varrho \in (1-{1}/{q}-Θ(\sqrt{\varepsilon}))$ our minimal feedback scheme has the following parameters: Rate $1-H_q(\varrho) - \varepsilon$ (i.e., $\varepsilon$-close to information-theoretically optimal – here $H_q(\varrho)$ is the $q$-ary entropy function), list-size $\exp\left(\mathcal{O}\left(\varepsilon^{-3/2}\log^2(1/\varepsilon)\right)\right)$, computational complexity of encoding/decoding $n^{\mathcal{O}(\varepsilon^{-1}\log(1/\varepsilon))}$, storage complexity $\mathcal{O}(n^{η+1}\log n)$ for a code design parameter $η>1$ that trades off storage complexity with the probability of error. The error probability is $\mathcal{O}(n^{-η})$, and the (vanishing) feedback rate is $\mathcal{O}({1}/{\sqrt{\log(n)}})$.

We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of $SU(n)$, where $n \ge 2$ is constant. For dimension $N$ and error $ε$, the number of quantum gates in our circuits is polynomial in $\log(N)$ and $\log(1/ε)$. Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of $SU(n)$ in the Hilbert space of $n$ quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.

The subgraph isomorphism problem and its generalizations such as conjunctive queries, where some nodes are projected, are among the most fundamental problems in graph algorithms and database theory. In this paper, we study the listing and enumeration variants of these problems and present two main results.

(1) We present the first algorithms for enumerating projected trees with polynomial preprocessing time ($\widetilde{O}(n^{17.42})$) and polylogarithmic delay ($\mathrm{polylog}(n)$). Prior to this work, all algorithms in the literature required time $Ω(n^{Ω(k)} + t)$ or $t \cdot n^{Ω(1)}$ to list all copies of a $k$-node tree with projections, where $t$ is the number of solutions. Our result generalizes to arbitrary projected hypergraphs, achieving enumeration in preprocessing time $\widetilde{O}(m^{17.42 \cdot \mathrm{subw}(H)})$ and polylogarithmic delay, where $\mathrm{subw}(H)$ is the submodular width of the pattern hypergraph $H$. We heavily rely on fast (rectangular and output-sensitive) matrix multiplication, which we complement by fine-grained lower bounds indicating that any algorithm beating time $Ω(n^{Ω(k)} + t)$ must rely on fast matrix multiplication.

(2) As our second main result, we present a generic enumeration-to-listing reduction, establishing that listing and enumeration are equivalent under natural assumptions. For (colored) subgraph isomorphism, our reduction transforms any listing algorithm running in time $O(f(n,m) + t \cdot g(n,m))$ into an enumeration algorithm with preprocessing time $O((f(n,m)+g(n,m)+m) \log^2 n)$ and delay $O(g(n,m))$. We utilize this equivalence as a tool for proving our first main result, and we expect that our generic reduction will find many future applications.

In the noisy $k$-XOR problem, one is given $y \in \mathbb{F}_2^M$ and must distinguish between $y$ uniform and $y = A x + e$, where $A$ is the adjacency matrix of a $k$-left-regular bipartite graph with $N$ variables and $M$ constraints, $x\in \mathbb{F}_2^N$ is random, and $e$ is noise with rate $η$. Lower bounds in restricted computational models such as Sum-of-Squares and low-degree polynomials are closely tied to the expansion of $A$, leading to conjectures that expansion implies hardness. We show that such conjectures are false by constructing an explicit family of graphs with near-optimal expansion for which noisy $k$-XOR is solvable in polynomial time.

Our construction combines two powerful directions of work in pseudorandomness and coding theory that have not been previously put together. Specifically, our graphs are based on the lossless expanders of Guruswami, Umans and Vadhan (JACM 2009). Our key insight is that by an appropriate interpretation of the vertices of their graphs, the noisy XOR problem turns into the problem of decoding Reed-Muller codes from random errors. Then we build on a powerful body of work from the 2010s correcting from large amounts of random errors. Putting these together yields our construction.

Concretely, we obtain explicit families for which noisy $k$-XOR is polynomial-time solvable at constant noise rate $η= 1/3$ for graphs with $M = 2^{O(\log^2 N)}$, $k = (\log N)^{O(1)}$, and $(N^{1-α}, 1-o(1))$-expansion. Under standard conjectures on Reed-Muller codes over the binary erasure channel, this extends to families with $M = N^{O(1)}$, $k=(\log N)^{O(1)}$, expansion $(N^{1-α}, 1-o(1))$ and polynomial-time algorithms at noise rate $η= N^{-c}$.

We study the problem of constructing explicit codes whose rate and distance match the Gilbert-Varshamov bound in the low-rate, high-distance regime. In 2017, Ta-Shma gave an explicit family of codes where every pair of codewords has relative distance $\frac{1-\varepsilon}{2}$, with rate $Ω(\varepsilon^{2+o(1)})$, matching the Gilbert-Varshamov bound up to a factor of $\varepsilon^{o(1)}$. Ta-Shma's construction was based on starting with a good code and amplifying its bias with walks arising from the $s$-wide-replacement product.

In this work, we give a simpler almost-optimal construction, based on what we call free expander walks: ordinary expander walks where each step is taken on a distinct expander from a carefully chosen sequence. This sequence of expanders is derived from the construction of near-$X$-Ramanujan graphs due to O'Donnell and Wu. We additionally discuss some additional applications of near-$X$-Ramanujan graphs to "on average" lossless expansion and rotating expanders.

The subspace design property for additive codes is a higher-dimensional generalization of the minimum distance property. As shown recently by Brakensiek, Chen, Dhar and Zhang, it implies that the code has similar performance as random linear codes with respect to all "local properties". Explicit algebraic codes, such as folded Reed-Solomon and multiplicity codes, are known to have the subspace design property, but they need alphabet sizes that grow as a large polynomial in the block length. Constructing explicit constant-alphabet subspace design codes was subsequently posed as an open question in Brakensiek, Chen, Dhar and Zhang.

In this work, we answer their question and give explicit constructions of subspace design codes over constant-sized alphabets, using the expander-based Alon-Edmonds-Luby (AEL) framework. This generalizes the recent work of Jeronimo and Shagrithaya, which showed that such codes share local properties of random linear codes. Our work obtains this consequence in a unified manner via the subspace design property. In addition, our approach yields some improvements in parameters for list-recovery.

We give new explicit constructions of several fundamental objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, weak subspace designs, and strong $s$-blocking sets over finite fields.

Our focus is on the small-field regime, where the field size depends only on a secondary parameter (such as the rank or codimension) and is independent of the ambient dimension. This regime is central to several applications, yet remains poorly understood from the perspective of explicit constructions.

In this setting, we obtain the first explicit constructions of lossless rank extractors and weak subspace designs for $r\ll k$, where $r$ denotes the rank (or codimension), over finite fields $\mathbb{F}_q$ with $q \ge \mathrm{poly}(r)$ and $q$ non-prime, with near-optimal parameters. For other finite fields, including prime fields and small fields, we obtain weaker but still improved bounds.

As a consequence, we construct explicit strong $s$-blocking sets in $\mathrm{PG}(k-1,q)$ of size $O(s(k-s)q^s)$ for all sufficiently large non-prime fields $q \ge \mathrm{poly}(s)$, matching the best known non-explicit bounds up to constant factors. This significantly improves the previous best bound $2^{O(s^2 \log s)} q^s k$ of Bishnoi and Tomon (Combinatorica, 2026), which requires $q \ge 2^{Ω(s)}$.

Our approach is primarily algebraic, combining techniques from function fields and polynomial identity testing. In addition, we develop a complementary Fourier-analytic framework based on $\varepsilon$-biased sets, which yields improved explicit constructions of strong $s$-blocking sets over small fields.

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing strong one-way NOF lower bounds would imply circuit lower bounds, resolve well-known problems in additive combinatorics, and yield wide-ranging applications in areas such as cryptography and distributed computing. However, proving strong lower bounds in one-way NOF communication remains highly challenging; many fundamental questions in one-way NOF communication remain wide open. One of the fundamental questions, proposed by Gavinsky and Pudlák (CCC 2008), is to establish an explicit exponential separation between quantum and classical one-way NOF communication.

In this paper, we resolve this open problem by establishing the first exponential separation between quantum and randomized communication complexity in one-way NOF model. Specifically, we define a lifted variant of the Hidden Matching problem of Bar-Yossef, Jayram, and Kerenidis (STOC 2004) and show that it admits an ($O(\log n)$)-cost quantum protocol in the one-way NOF setting. By contrast, we prove that any $k$-party one-way randomized protocol for this problem requires communication $Ω(\frac{n^{1/3}}{2^{k/3}})$. Notably, our separation applies even to a generalization of $k$-player one-way communication, where the first player speaks once, and all other $k-1$ players can communicate freely.

Bucketized cuckoo hashing is a practically efficient hash table scheme in which each object $u$ is stored in one of two buckets $h_1(u), h_2(u)$ of capacity $\ell$. For any bucket size $\ell\in\mb{N}$, there is a threshold $ε^*(\ell)=(2/e)^\ell\mathrm{poly}(\ell)$ for which there exists a way to fill the hash table to any load factor less than $1-ε^*$ with low probability of an error. Queries and deletions only need to check two buckets to find whether an object exists.

Our contribution is to give a new insertion procedure for bucketized cuckoo hashing. For any $δ\in[.99^\ell,1]$, our algorithm can fill the hash table to load factor $1-ε=1-(1+δ)(ε^*)$ with an expected run time of $O(δ^{-1}(ε^*)^{-1})$ per insertion. This gives the first $\mathrm{poly}(ε^{-1})$ insertion time bound, and the first $f(ε^{-1})$ time bound for load factors that are very close to the optimal threshold. Additionally, our algorithm (which can be viewed as a variation of the classic random-walk algorithm) comes with a very strong amortized guarantee: it performs $O(1)$ amortized expected evictions per insertion. Furthermore, we show that the traditional random-walk algorithm cannot match this guarantee.

Finally, our insertion protocol also comes with the feature that, for any key $u$ in the hash table, the query algorithm can guess which of the two bins $h_1(u), h_2(u)$ the key $u$ is in with probability $1 - o(1)$ of being correct. Thus positive queries can complete in $1 + o(1)$ expected bin accesses.

We present a new algorithm for finding an $ε$-approximate fixed point of an $\ell_\infty$-contracting function $f : [0, 1]^d \rightarrow [0, 1]^d$. Our algorithm is based on the query-efficient algorithm by Chen, Li, and Yannakakis (STOC 2024), but comes with an improved upper bound of $(\log \frac{1}ε)^{\mathcal{O}(d \log d)}$ on the overall runtime (while still being query-efficient). By combining this with a recent decomposition theorem for $\ell_\infty$-contracting functions, we then describe a second algorithm that finds an $ε$-approximate fixed point in $(\log \frac{1}ε)^{\mathcal{O}(\sqrt{d} \log d)}$ queries and time. The key observation here is that decomposition theorems such as the one for $\ell_\infty$-contracting maps often allow a trade-off: If an algorithm's runtime is worse than its query complexity in terms of the dependency on the dimension $d$, then we can improve the runtime at the expense of weakening the query upper bound. By well-known reductions, our results imply a faster algorithm for $ε$-approximately solving Shapley stochastic games.

Finding a Steiner strongly $k$-arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set of critical nodes. Király and Lau (FOCS 2006) introduced a rooted variant, called the Steiner Rooted Orientation problem, where one is given an undirected graph on $n$ vertices, a root vertex, and a set of $t$ terminals. The goal is to find an orientation of the graph such that the resulting directed graph is Steiner rooted $k$-arc-connected. This problem generalizes several classical connectivity results in graph theory, such as those on edge-disjoint paths and spanning-tree packings. While the maximum $k$ for which a Steiner strongly $k$-arc-connected orientation exists can be determined in polynomial time via Nash-Williams' orientation theorem, its rooted counterpart is significantly harder: the problem is NP-hard when both $k$ and $t$ are part of the input. In this work, we provide a complete understanding of the problem with respect to these two parameters. In particular, we give an algorithm that solves the problem in time $f(k,t)\cdot n^{O(1)}$, establishing fixed-parameter tractability with respect to the number of terminals $t$ and the target connectivity $k$. We further show that the problem remains NP-hard if either $k$ or $t$ is treated as part of the input, meaning that our algorithm is essentially optimal from a parameterized perspective. Importantly, our results extend far beyond the Steiner setting: the same framework applies to the more general orientation problem with local connectivity requirements, establishing fixed-parameter tractability when parameterized by the total demand and thereby covering a wide range of arc-connectivity orientation problems.

The complexity of determining the minimum number of flips that transform one triangulation of a convex polygon into another has been raised as an open problem by Culik and Wood [Inf. Proc. Letters 1982] and has been popularized through the study of extremal pairs of triangulations by Sleator, Tarjan, and Thurston [STOC 1986 & J. Am. Math. Society 1988]. The search for a hardness proof for the flip distance problem has yielded many (weaker) hardness-results in more general settings. Lubiw and Pathak [CCCG 2012, Comp. Geom. 2014] and Pilz [Comp. Geom. 2014] proved that computing the flip distance between triangulations of point sets in general position is NP-complete. Further, Aichholzer, Mulzer, and Pilz [ESA 2013, DCG 2015] proved that computing the flip distance between triangulations of simple polygons is NP-complete. The methods used to obtain these previous hardness results rely heavily on the geometric positioning of the vertices of the point set or the vertices of the polygon and are thus not feasible to prove NP-hardness for the flip distance problem of triangulations of convex polygons, where vertices are placed on a circle. We formulate a notion of conflict graphs for flip sequences between triangulations of convex polygons that allows us to use both geometric and combinatorial tools to study flip sequences. Large acyclic subsets of the conflict graph will correspond to short flip sequences. We show NP-completeness of the flip distance problem by proving that finding the largest acyclic subset of our conflict graphs is NP-complete.

In the classical Min-Sum Radii problem (MSR) we are given a set $X$ of $n$ points in a metric space and a positive integer $k\in [n]$. Our goal is to partition $X$ into $k$ subsets (the clusters) so as to minimize the sum of the radii of these clusters. The Min-Sum Diameters problem (MSD) is defined analogously, where instead of the radii of the clusters we consider their diameters. For both problems we present FPT approximation schemes for the natural parameter $k$. Specifically, given $ε>0$, we show how to compute $(1+ε)$-approximations for both MSD and MSR in time $(1/ε)^kn^{O(1)}$ and $(1/ε)^{O(k/ε\log 1/ε)}n^{poly(1/ε)}$ respectively. The previous best FPT approximation algorithms for these problems have approximation factors $4+ε$ and $2+ε$, respectively, and finding an FPT approximation scheme for both these problems had been outstanding open problems.

We consider the Euclidean $k$-means clustering problem in a dynamic setting, where we have to explicitly maintain a solution (a set of $k$ centers) $S \subseteq \mathbb{R}^d$ subject to point insertions/deletions in $\mathbb{R}^d$. We present a dynamic algorithm for Euclidean $k$-means with $\mathrm{poly}(1/ε)$-approximation ratio, $\tilde{O}(k^ε)$ update time, and $\tilde{O}(1)$ recourse, for any $ε\in (0,1)$, even when $d$ and $k$ are both part of the input. This is the first algorithm to achieve a constant ratio with $o(k)$ update time for this problem, whereas the previous $O(1)$-approximation runs in $\tilde O(k)$ update time [Bhattacharya, Costa, Farokhnejad; STOC'25].

In fact, previous algorithms cannot go beyond $O(k)$ update time precisely because they are designed for general metrics where an $Ω(k)$ lower bound is known. We break this $O(k)$ barrier by devising new fundamental data structures to utilize Euclidean properties: a structure that (implicitly) maintains a clustering subject to both center and data point updates, and a range query structure that can evaluate a mergeable function over any metric ball range given as a query. To obtain these structures, we devise the first consistent hashing scheme [Czumaj, Jiang, Krauthgamer, Vesel{ý}, Yang; FOCS'22] that achieves $\tilde O(n^ε)$ running time per point evaluation with competitive parameters.

Our final algorithm exploits the framework of [Bhattacharya, Costa, Farokhnejad; STOC'25] for general metrics. The key change is to redesign several critical subroutines so that they reduce to our new Euclidean data structures, replacing the general-metric implementations that are unlikely to run efficiently even when Euclidean properties are provided.

We prove an information-theoretically optimal gap-majority lemma in the two-player randomized communication model. For a base function $f: \mathcal{X} \to \{\pm 1\}$, its $n$-fold gap-majority composition, denoted $\mathsf{GapMAJ} \circ f^n$, takes $n$ inputs $(X_1, \ldots, X_n)$ and distinguishes whether $f^{+n}(X_1,\ldots,X_n) := f(X_1) + \ldots + f(X_n)$ is at least $0.01\sqrt{n}$ or at most $-0.01\sqrt{n}$. We show that if computing $f$ with success probability $0.501$ requires $I$ bits of information, then computing $\mathsf{GapMAJ} \circ f^n$ with success probability $0.99$ requires $n \cdot (I - O(1))$ bits of information. This result is asymptotically optimal in two aspects: it achieves the correct linear scaling of information cost and the correct constant-constant tradeoff between error rates. This makes $\mathsf{GapMAJ}$, to our knowledge, only the third explicit outer gadget that admits a strong composition theorem in the two-player communication setting, following the identity and XOR gadgets.

From an application side, our gap-majority lemma can be viewed as a generic amplification tool that lifts the hardness of deciding $f$ into the hardness of approximating $f^{+n}$. Using this framework, we give a new proof to the communication lower bound of Gap-Hamming and derive a tight streaming lower bound of triangle counting, demonstrating the versatility of the gap-majority lemma.

Graph $k$-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a $k$-coloring over the set of all $k$-colorable graphs on $n$ vertices. A highly influential result of Dyer–Frieze from 1989 gave an algorithm with $O(n^2)$ average runtime for constant $k$.

This quadratic runtime appeared natural (and possibly even optimal) since almost all $k$-colorable graphs have $Θ(n^2)$ edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Kučera in 1995 to average runtime $O(n^2/k)$ for every $k \leq n^c$ where $c \in (0,1)$. Nevertheless, in the most interesting case of $k = O(1)$, the best-known bound remained quadratic in $n$. The true average complexity of the $k$-coloring problem has remained elusive for the last three decades.

We break the longstanding quadratic barrier. Our main result shows that the exact average-case complexity of this fundamental problem is $Θ(nk)$ for every $k \leq n^{c'}$ and some $c' \in (0,1)$. For $k = O(1)$, this reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input. We further show that our $Θ(nk)$ average runtime is optimal, since a simple bound proves that every algorithm that correctly $k$-colors all $k$-colorable graphs requires $Ω(nk)$ average runtime.

Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for $k$-coloring with average-case probe complexity $\operatorname{poly}(k)$. A key new ingredient in our algorithm is a method for certifying the unique colorability of random subgraphs, using tools from the theory of graph regularity.

Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments. In particular, Forbes, Shpilka, Tzameret, and Wigderson (Theory Comput. 2021) developed the main lower-bound frameworks for restricted IPS fragments, namely functional lower bounds and the hard multiples method, while Alekseev, Grigoriev, Hirsch, and Tzameret (SIAM J.Comput. 2024) gave a general template for conditional lower bounds for full IPS.

Yet all these lower bounds apply only to purely algebraic formulas over a field, that is, non-Boolean formulas not directly expressible in propositional logic. Proving lower bounds for CNF formulas has therefore remained a central open problem in this line of work.

The current work resolves this question for IPS over read-once oblivious algebraic branching programs (roABPs) by proving lower bounds for refutations of CNF formulas in this system. Our approach is a rank-based feasible interpolation argument, following the method of Pudlak and Sgall (Proof Complexity and Feasible Arithmetic 1996) for monotone span programs, in which decomposing a given roABP refutation along a variable partition yields a low-dimensional space of polynomials from which we construct a span-program interpolant. We extend their result from Nullstellensatz refutations measured by degree to Nullstellensatz refutations measured by roABP size (i.e., roABP-IPS$_{LIN}$).

A graph class is $k$-WQO if its $k$-labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is $2$-WQO has bounded clique-width. Combined with the recent result of Dumas and Lopez, this confirms a long-standing conjecture of Pouzet: A hereditary graph class is $2$-WQO if and only if it is $k$-WQO for all $k\geq 2$, if and only if it is $\forall$-WQO, that is, its labeled graphs are well-quasi-ordered for every possible well-quasi-ordered label set.

Our proof builds on a recent structure/non-structure dichotomy for the model theoretic notion of monadic dependence by Dreier, Mählmann, and Toruńczyk. Through the non-structure characterization by forbidden induced subgraphs, we show that every hereditary $2$-WQO graph class is monadically dependent. Leveraging the Ramsey-theoretic structural properties provided by monadic dependence, we then establish bounded clique-width by ruling out the existence of large well-linked sets, which are the canonical obstructions for clique-width.

We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, lies in the counting hierarchy. More generally, we show that the number of solutions to a system of equations can be computed in polynomial time with oracle access to the counting hierarchy. Our results hold in particular for polynomials with coefficients in either the rational numbers or a finite field. Previously, the best-known bounds on the complexities of these problems were PSPACE and FPSPACE, respectively. Our main technical contribution is the construction of a uniform family of constant-depth arithmetic circuits that compute the multivariate resultant.

The traveling salesman problem (TSP) is a cornerstone of combinatorial optimization and has deeply influenced the development of algorithmic techniques in both exact and approximate settings. Yet, improving on the decades-old bounds for solving TSP exactly remains elusive: the dynamic program of Bellman, Held, and Karp from 1962 uses $2^{n+O(\log{n})}$ time and space, and the divide-and-conquer approach of Gurevich and Shelah from 1987 uses $4^{n + O(\log^2{n})}$ time and polynomial space. A straightforward combination of the two algorithms trades off $T^{n+o(n)}$ time and $S^{n+o(n)}$ space at various points of the curve $ST = 4$. An improvement to this tradeoff when $2 < T < 2\sqrt{2}$ was found by Koivisto and Parviainen (SODA 2010), yielding a minimum of $ST \approx 3.93$. Koivisto and Parviainen show their method to be optimal among a broad class of partial-order-based approaches, and to date, no improvement or alternative method has been found.

In this paper we give a tradeoff that strictly improves all previous ones for all $2 < T < 4$, achieving a minimum of $ST < 3.572$. A key ingredient is the construction of sparse set systems (hypergraphs) that admit a large number of maximal chains. The existence of such objects is of independent interest in extremal combinatorics, likely to see further applications. Along the way we disprove a combinatorial conjecture of Johnson, Leader, and Russell from 2013, relating it with the optimality of the previous tradeoff schemes for TSP. Our techniques extend to a broad class of permutation problems over arbitrary semirings, yielding improved space-time tradeoffs in these settings as well.

We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem that solves $N$-vertex instances using space $S$ and time $T$ where $S\cdot T \leq 3.1861^{N}$. This improves a previous work by Koivisto and Parviainen [SODA'10] where $S\cdot T \leq 3.9271^N$, and overcomes a barrier they identified, as their bound was shown to be optimal within their framework.

To get our results, we introduce a new parameter of a set system that we call the chain efficiency. This relates the number of maximal chains contained in the set system with the cardinality of the system. We show that set systems of high efficiency imply efficient space-time tradeoffs for permutation problems, and give constructions of set systems with high chain efficiency, disproving a conjecture by Johnson, Leader and Russel [Comb. Probab. Comput.'15].

We prove that the flow-cut gap for $n$-node directed graphs is at most $n^{1/3 + o(1)}$. This is the first improvement since a previous upper bound of $\widetilde{O}(n^{11/23})$ by Agarwal, Alon, and Charikar (STOC '07), and it narrows the gap to the current lower bound of $\widetildeΩ(n^{1/7})$ by Chuzhoy and Khanna (JACM '09). We also show an upper bound on the directed flow-cut gap of $W^{1/2}n^{o(1)}$, where $W$ is the sum of the minimum fractional cut weights.

As an auxiliary contribution, we significantly expand the network of reductions among various versions of the directed flow-cut gap problem. In particular, we prove near-equivalence between the edge and vertex directed flow-cut gaps, and we show that when parametrizing by $W$, one can assume unit capacities and uniform fractional cut weights without loss of generality.

We study the problem of estimating a vertex's PageRank within a constant relative error, with constant probability. We prove that an adaptive variant of the simple classic bidirectional algorithm is instance-optimal up to a polylogarithmic factor for all directed graphs of order $n$ whose maximum in- and out-degrees are at most a constant fraction of $n$. In other words, there is no correct algorithm that can be faster than our algorithm on any such graph by more than a polylogarithmic factor. We further extend the instance-optimality to all graphs in which at most a polylogarithmic number of vertices have unbounded degrees. This covers all sparse graphs with $\tilde{O}(n)$ edges. In addition, we provide a counterexample showing that the bidirectional algorithm is not instance-optimal for graphs whose degrees are mostly equal to $n$. We also consider weighted graphs and multigraphs. We show that the bidirectional algorithm is instance-optimal on all multigraphs, but for weighted simple graphs, we have almost the same limitations as for unweighted simple graphs.

In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for $k$-clustering. As a starting point, we obtain an iterative rounding $(\frac{3^p + 1}{2})$-Lagrangian Multiplier-Perserving (LMP) approximation for the $k$-clustering problem with the cost function being the $p$-th power of the distance. Such an algorithm outputs a random solution that opens $k$ facilities in expectation, whose cost in expectation is at most $\frac{3^p + 1}{2}$ times the optimum cost. Thus, we recover the $2$-LMP approximation for $k$-median by Jain et al. [JACM'03], which played a central role in deriving the current best $2$ approximation for $k$-median. Unlike the result of Jain et al., our algorithm is based on LP rounding, and it can be easily adapted to the $L_p^p$-cost setting. For the Euclidean $k$-means problem, the LMP factor we obtain is $\frac{11}{3}$, which is better than the $5$ approximation given by this framework for general metrics.

Then, we show how to convert the LMP-approximation algorithms to a true-approximation, with only a $(1+\varepsilon)$ factor loss in the approximation ratio. We obtain a ($\frac{3^p + 1}{2}+\varepsilon$)-approximation algorithm for $k$-clustering with cost function being the $p$-th power of the distance, for $p \geq 1$. This reproduces the best known ($2+\varepsilon$)-approximation for $k$-median by Cohen-Addad et al. [STOC'25], and improves the approximation factor for metric $k$-means from 5.83 by Charikar at al. [FOCS'25] to $5+\varepsilon$ in our framework. Moreover, the same algorithm, but with a specialized analysis, attains ($4+\varepsilon$)-approximation for Euclidean $k$-means matching the recent result by Charikar et al. [STOC'26].

We study the problem of finding confidence ellipsoids for an arbitrary distribution in high dimensions. Given samples from a distribution $D$ and a confidence parameter $α$, the goal is to find the smallest volume ellipsoid $E$ which has probability mass $\mathbb{P}_{D}[E] \ge 1-α$. Ellipsoids are a highly expressive class of confidence sets as they can capture correlations in the distribution, and can approximate any convex set. In statistics, this is the classic minimum volume estimator introduced by Rousseeuw as a robust non-parametric estimator of location and scatter. However in high dimensions, it becomes NP-hard to obtain any non-trivial approximation factor in volume when the condition number $β$ of the ellipsoid (ratio of the largest to the smallest axis length) goes to $\infty$. This motivates the focus of our paper: can we efficiently find confidence ellipsoids with volume approximation guarantees when compared to ellipsoids of bounded condition number $β$?

Our main result is a polynomial time algorithm that finds an ellipsoid $E$ whose volume is within a $O(β)^{γd}$ multiplicative factor of the volume of best $β$-conditioned ellipsoid while covering at least $1-O(α/γ)$ probability mass for any $γ\in (0,1)$. In particular, setting $γ= o(1)$, this gives a $O(β)^{o(d)}$ volume approximation, with a multiplicative loss in miscoverage. We complement this with a computational hardness result that shows that such a dependence on $β$ seems necessary, even with some slack in coverage. The algorithm and analysis uses the rich primal-dual structure of the minimum volume enclosing ellipsoid and the geometric Brascamp-Lieb inequality. As a consequence, we obtain the first polynomial time algorithm with approximation guarantees on worst-case instances of the robust subspace recovery problem.

We construct a universal decompressor $U$ for plain Kolmogorov complexity $\mathrm{C}_U$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings $R_{\mathrm{C}_U} = \{x : \mathrm{C}_U(x) \ge |x|\}$. This result resolves a problem posed by Eric Allender regarding the computational power of Kolmogorov complexity-based oracles.

Recent years have seen rapid development in the subject of quantum coding theory, with breakthroughs on many exciting classes of codes, including quantum LDPC codes, quantum locally testable codes, and quantum codes with interesting transversal gates. However, a natural class of quantum codes, which has been well-studied classically, has not yet been treated: those which can be quickly encoded and decoded. This problem concerns the channel capacity setting, where a noise channel sits between perfect encoding and unencoding/decoding operations; this is the setting that is relevant for communication between fault-tolerant quantum computers. In this work, we construct asymptotically good quantum codes that can be encoded and unencoded by quantum circuits of logarithmic depth and consisting of a linear total number of gates. The classical decoding algorithms also run in logarithmic depth and use $\mathcal{O}(n \log n)$ gates, or alternatively a linear number of gates but with higher depth. We further construct explicit and asymptotically good quantum codes whose encoding, unencoding and decoding all use a linear number of gates, and additionally whose encoding and unencoding may be run in logarithmic depth.

We initiate an investigation of node differential privacy for graphs in the local model of private data analysis. In our model, dubbed LNDP*, each node sees its own edge list and releases the output of a local randomizer on this input. These outputs are aggregated by an untrusted server to obtain a final output.

We develop a novel algorithmic framework for this setting that allows us to accurately answer arbitrary linear queries about the input graph's degree distribution. Our framework is based on a new object, called the blurry degree distribution, which closely approximates the degree distribution and has lower sensitivity. Instead of answering queries about the degree distribution directly, our algorithms answer queries about the blurry degree distribution. This framework yields accurate LNDP* algorithms for the edge count, PMF and CDF of the degree distribution, and other graph statistics. For some natural problems, our algorithms match the accuracy achievable with node privacy in the central model, where data are held and processed by a trusted server.

We also prove lower bounds on the error required by LNDP* algorithms that imply the optimality of our framework for edge counting in sparse graphs and Erdos-Renyi parameter estimation. Our lower bounds apply even to interactive protocols with a constant number of rounds of interaction between the nodes and the server. Existing lower-bound techniques for related models either yield loose bounds or do not apply in our setting, as graph data results in inherently overlapping inputs to local randomizers. To prove our bounds, we develop a splicing argument that stitches together views from locally similar but globally different distributions on graphs to obtain hard instances.

Finally, we prove structural results that reveal qualitative differences between local node privacy and the standard local model for tabular data.

Learning about a Hamiltonian $H$ from its time evolution $e^{-iHt}$ is a fundamental task in quantum science. A flurry of recent work has developed powerful new algorithms with provable guarantees for this task, for a variety of natural settings. Despite this, relatively little is known about lower bounds for learning Hamiltonians. In particular, in the natural setting where we assume $H$ is a $k$-local Hamiltonian on $n$ qubits, all existing algorithms require total evolution time at least $n^{Ω(k)}$ to learn the parameters of $H$, and it remained open whether one could obtain even faster algorithms – or at the very least, if one could obtain better runtimes for simpler tasks, such as estimating a single designated coefficient of the Hamiltonian.

In this work we show the answer is essentially no, by obtaining strong lower bounds for these problems. We find that not only do $k$-local Hamiltonians require $n^{Ω(k)}$ time evolution or interactions to learn, but also that in several senses, learning anything about a Hamiltonian is just as hard as learning everything. In particular, we find the same $n^{Ω(k)}$ lower bound holds for learning a single coefficient of a $k$-local Hamiltonian $H$, even if the rest of $H$ is already known. We also show an $n^{Ω(k)}$ lower bound for the task of effective Hamiltonian learning, where one seeks only to learn a unitary that approximately implements time evolution of $H$. Several related lower bounds, such as for general sparse (but not necessarily local) $H$ are also given.

On the technical side, we make a new connection between Hamiltonian learning lower bounds and the analysis of Boolean functions, where we introduce a novel extremal property that may be of independent interest.

(shortened for arXiv metadata)

We study the limits of single-server private information retrieval (PIR) with preprocessing. Prior work has shown that single-server PIR with sublinear communication requires a linear number of (public-key) server operations per query [DMO00, DH24]. Recent breakthrough works, including [CHK22, ZPZS24, LMW23], circumvent these lower bounds by critically leveraging preprocessing to construct single-server PIR with sublinear query computation.

Our work presents computation lower bounds for any single-server PIR with preprocessing that makes blackbox usage of any cryptography (such as random oracles and virtual blackbox obfuscation). For any client preprocessing scheme where the client stores $s$ bits about an $n$-bit database, we prove the online amortized computation must be $Ω(n/s)$ across $k = Ω(s)$ queries (even if performed in a single batch query). In more detail, we prove that they must have either $Ω(n/s)$ amortized online communication or the server must perform $Ω(n/s)$ cryptographic operations. Our lower bounds are optimal as there exist PIRs with client preprocessing matching exactly one of the above requirements while outperforming the other. Furthermore, our lower bounds also rule out the existence of doubly efficient PIR from blackbox cryptography with sublinear query computation. Our proof framework also supports $Ω(n/s)$ communication lower bounds for three mildly restricted classes of single-server PIR.

We also prove lower bounds for symmetric private information retrieval (SPIR) with client preprocessing in the random oracle model and present a matching SPIR construction with client preprocessing using only OWFs during queries.

A longstanding belief in quantum tomography is that estimating a mixed state is far harder than estimating a pure state. This is borne out in the mathematics, where mixed state algorithms have always required more sophisticated techniques to design and analyze than pure state algorithms. We present a new approach to tomography demonstrating that, contrary to this belief, state-of-the-art mixed state tomography follows easily and naturally from pure state algorithms.

We analyze the following strategy: given $n$ copies of an unknown state $ρ$, convert them into copies of a purification $|ρ\rangle$; run a pure state tomography algorithm to produce an estimate of $|ρ\rangle$; and output the resulting estimate of $ρ$. The purification subroutine was recently discovered via the "acorn trick" of Tang, Wright, and Zhandry. With this strategy, we obtain the first tomography algorithm which is sample-optimal in all parameters. For a rank-$r$ $d$-dimensional state, it uses $n = O((rd + \log(1/δ))/\varepsilon)$ samples to output an estimate which is $\varepsilon$-close in fidelity with probability at least $1-δ$. This algorithm also uses poly$(n)$ gates, making it the first gate-efficient tomography algorithm which is sample-optimal even in terms of the dimension $d$ alone. Moreover, with this method we recover essentially all results on mixed state tomography, including its applications to tomography with limited entanglement, classical shadows, and quantum metrology. Our proofs are simple, closing the gap in conceptual difficulty between mixed and pure tomography. Our results also clarify the role of entangled measurement in mixed state tomography: the only step of the algorithm which requires entanglement across copies is the purification step, suggesting that, for tomography, the reason entanglement is useful is for consistent purification.

We prove a near-maximum ($2^n / n$) circuit lower bound for the complexity class $\mathsf{E}^{\mathrm{pr}\mathsf{MA}}/_1$, corresponding to exponential time with access to a promise-$\mathsf{MA}$ oracle and one bit of advice. Our proof incorporates the iterative win-win paradigm (Chen–Lu–Oliveira–Ren–Santhanam, FOCS'23), the reduction from the Range Avoidance problem to circuit lower bounds (Jeřábek, Ann. Pure Appl. Log. '04; Korten, FOCS'21), and the PCP theorem. Crucial to our proof is the analysis of the complexity class $\mathsf{P}^\mathsf{NP}[{\textsf{#rounds}}=r, {\textsf{length}}=s]$, which is $\mathsf{P}^\mathsf{NP}$ with $r(n)$ adaptive rounds of $\mathsf{NP}$ queries, where each $\mathsf{NP}$ query has witness length $s(n)$.

In a streaming constraint satisfaction problem (streaming CSP), a $p$-pass algorithm receives the constraints of an instance sequentially, making $p$ passes over the input in a fixed order, with the goal of approximating the maximum fraction of satisfiable constraints. We show near optimal space lower bounds for streaming CSPs, improving upon prior works.

(1) Fei, Minzer and Wang (STOC 2026) showed that for any CSP, the basic linear program defines a threshold $α_{\mathrm{LP}}\in [0,1]$ such that, for any $\varepsilon > 0$, an $(α_{\mathrm{LP}} - \varepsilon)$-approximation can be achieved using constant passes and polylogarithmic space, whereas achieving $(α_{\mathrm{LP}} + \varepsilon)$-approximation requires $Ω(n^{1/3}/p)$ space. We improve this lower bound to $Ω(\sqrt{n}/p)$, which is nearly tight for a gap version of the problem.

(2) For $p=o(\log n)$, we further strengthen the lower bound to $Ω(n\cdot2^{-O_{\varepsilon}(p)})$. Combined with existing algorithmic results, this shows that $α_{\mathrm{LP}}$ is not only the limit of multi-pass polylogarithmic-space algorithms, but also the limit of single-pass sublinear-space algorithms on bounded-degree instances.

(3) For certain CSPs, we show that there exists $α< 1$ such that achieving an $α$-approximation requires $Ω(n/p)$ space.

Our proofs are Fourier analytic, building on the techniques of Fei, Minzer and Wang (STOC 2026) and the Fourier-$\ell_1$-based lower bound method of Kapralov and Krachun (STOC 2019).

We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given $\widetilde{O}(2^n/ε)$ copies of an unknown $n$-qubit pure state $|ψ\rangle$, the algorithm performs only nonadaptive Pauli measurements, runs in time $\widetilde{O}(2^n/ε)$, and outputs $|\widehatψ \rangle$ with fidelity at least $1-ε$ with $|ψ\rangle$ with high probability. This is the first algorithm for pure state tomography that achieves near-optimal running time.

Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Point–Line Incidence problem is $Θ(\log n)$. This confirms a conjecture of Cheung, Hatami, Hosseini, and Shirley (CCC 2023) that the complexity is super-constant, and gives the first example of a communication problem with constant support-rank but super-constant randomised complexity.

We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of parameters in the `critical regime' between the regime amenable to hypergraph container methods and that amenable to Janson's inequality. Examples include lower tails and non-existence probabilities for subgraphs of random graphs and for $k$-term arithmetic progressions in random sets of integers.

Our methods apply in the general framework of estimating the probability that a $p$-random subset of vertices in a $k$-uniform hypergraph induces significantly fewer hyperedges than expected. We show that under some simple structural conditions on the hypergraph and an upper bound on $p$ determined by a phase transition in the hard-core model on the infinite $k$-uniform, $Δ$-regular, linear hypertree, this probability can be accurately approximated by the Bethe free energy evaluated at the unique fixed point of a Belief Propagation operator on the hypergraph.

In the pinwheel problem, one is given an $m$-tuple of positive integers $(a_1, \ldots, a_m)$ and asked whether the integers can be partitioned into $m$ color classes $C_1,\ldots,C_m$ such that every interval of length $a_i$ has non-empty intersection with $C_i$, for $i = 1, 2, \ldots, m$. It was a long-standing open question whether the pinwheel problem is NP-hard. We affirm a prediction of Holte et al. (1989) by demonstrating, for the first time, NP-hardness of the pinwheel problem. This enables us to prove NP-hardness for a host of other problems considered in the literature: pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem. On the positive side, we develop a PTAS for an approximate version of the pinwheel problem. Previously, the best approximation factor known to be achievable in polynomial time was $\frac{9}{7}$.

Program obfuscation aims to conceal a program's internal structure while preserving its functionality. A central open problem is whether an obfuscation scheme for arbitrary quantum circuits exists. Despite several efforts having been made toward this goal, prior works have succeeded only in obfuscating quantum circuits that implement either pseudo-deterministic functions or unitary transformations. Although unitary transformations already include a broad class of quantum computation, many important quantum tasks, such as state preparation and quantum error-correction, go beyond unitaries and fall within general completely positive trace-preserving maps.

In this work, we construct the first quantum ideal obfuscation scheme for arbitrary quantum circuits that support quantum inputs and outputs in the classical oracle model assuming post-quantum one-way functions, thereby resolving an open problem posed in Bartusek et al. (STOC 2023), Bartusek, Brakerski, and Vaikuntanathan (STOC 2024), and Huang and Tang (FOCS 2025). At the core of our construction lies a novel primitive that we introduce, called the subspace-preserving strong pseudorandom unitary (spsPRU). An spsPRU is a family of efficient unitaries that fix every vector in a given linear subspace $S$, while acting as a Haar random unitary on the orthogonal complement $S^\perp$ under both forward and inverse oracle queries. Furthermore, by instantiating the classical oracle model with the ideal obfuscation scheme for classical circuits proposed by Jain et al. (CRYPTO 2023) and later enhanced by Bartusek et al. (arxiv:2510.05316), our obfuscation scheme can also be realized in the quantumly accessible pseudorandom oracle model.

In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $P = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: draw $X$ uniformly at random from $\mathbb{F}_2^m$ and output $(P_1(X),\dots, P_n(X)) \in \{0,1\}^n$.

We show that when $P$ is defined by polynomials of degree $d$, the total variation distance of $P$ from the product distribution $\mathrm{Ber}(1/3)^{\otimes n}$ is $1-o_n(1)$, where $o_n(1)$ is a vanishing function of $n$ for any constant degree $d$. For small values of $d$, we show the following concrete bounds.

1. For $d=1$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(n))$.
2. For $d=2$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(\log(n)/\log\log(n)))$.
3. For $d=3$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(\sqrt{\log\log(n)}))$.

Our results extend the recent lower bound results for sampling distributions, which have mostly focused on local samplers, small depth decision trees, and small depth circuits.

As part of our proof, we establish the following result, that may be of independent interest: for any degree-$d$ polynomial $P\colon\mathbb{F}_2^m \to \mathbb{F}_2$ it holds that $\Pr_X[P(X) = 1]$ is bounded away from $1/3$ by some absolute constant $δ= δ_d>0$. Although the statement may seem obvious, we are not aware of an elementary proof of this.

The proof techniques rely on the structural results for low degree polynomials, saying that any biased polynomial of degree $d$ can be written as a function of a small number of polynomials of degree $d-1$.

We know that the Nash equilibria of a game cannot be computed efficiently unless $P = PPAD$. But can they be learned? Are there dynamics that (1) can be computed efficiently by the players at each strategy profile and (2) are guaranteed to converge to the Nash equilibria? This is a question as ancient as the Nash equilibrium itself, and antedates by many decades current complexity considerations about it. It was recently proved in MPPS23 that no such dynamics can exist in general; however, the game used in that proof is degenerate, and a strong assumption of uniform convergence to a continuum of Nash equilibria is employed. We point out that both assumptions are necessary for that proof, because Nash-convergent dynamics do exist, which converge to all Nash equilibria in non-degenerate games; in fact we describe two very different families of such dynamics. However, we show that both of these families are intractable to compute locally, unless complexity classes collapse. We formulate a complexity theoretic Impossibility Conjecture: if a locally tractable Nash-convergent dynamic exists then $P=PPAD$. This is a novel kind of conjecture, combining topology and complexity, because the dynamic is only required to be tractable locally – it could take exponentially many steps to converge, so long as the work done at each step is polynomial. Next, we show that any locally tractable dynamic which possesses a locally tractable Lyapunov function cannot exist unless $PPAD = CLS$. Finally, for the most general impossibility conjecture, we provide a complexity-theoretic explanation why it may be difficult to settle: we introduce a Proving Game to demonstrate that black-box reductions cannot distinguish between convergent and non-convergent dynamics in polynomial time.

We study the fundamental problem of fairly allocating a multiset $\mathcal{M}$ of $t$ types of indivisible items among $d$ groups of agents, where all agents within a group have identical additive valuations. Gorantla et al. [GMV23] showed that for every such instance, there exists a finite number $μ$ such that, if each item type appears at least $μ$ times, an envy-free allocation exists. Their proof is non-constructive and only provides explicit upper bounds on $μ$ for the cases of two groups ($d=2$) or two item types ($t=2$).

In this work, we resolve one of the main open questions posed by Gorantla et al. [GMV23] by deriving explicit upper bounds on $μ$ that hold for arbitrary numbers of groups and item types. We introduce a significantly simpler, yet powerful technique that not only yields constructive guarantees for indivisible goods but also extends naturally to chores and continuous domains, leading to new results in related fair division settings such as cake cutting.

An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the entanglement-assisted zero-error capacity under some restrictions is uncomputable; indicative of the fact that quantum channel capacities may generally be undecidable.

Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary correlated prior over arrival sequences. For such a prior, let $X^*$ be the hindsight-optimal fractional solution for the realized instance, and let $X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]$ be its posterior process. Our guiding rule is posterior matching: at each time $t$, choose the feasible online action that tracks the current posterior $X^{(t)}$ as closely as the online constraints permit.

We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems, including set cover, load balancing, matching and more general resource-allocation problems, recovering or improving state-of-the-art bounds in these settings with norm/concave objectives. Via known rounding reductions, it also yields randomized integral guarantees for weighted paging, MTS on star metrics, and ski-rental. At a technical level, our analysis reduces competitive guarantees to key probabilistic inequalities for the vector martingales generated by the posterior of the offline optimum. The resulting framework gives a reusable route from Bayesian online design under arbitrary correlated priors to information-theoretic worst-case competitive guarantees.

In the classic online graph balancing problem, edges arrive sequentially and must be oriented immediately upon arrival, to minimize the maximum in-degree. For adversarial arrivals, the natural greedy algorithm is $O(\log n)$-competitive, and this bound is the best possible for any algorithm, even with randomization. We study this problem in the i.i.d. model where a base graph $G$ is known in advance and each arrival is an independent uniformly random edge of $G$. This model generalizes the standard power-of-two choices setting, corresponding to $G = K_n$, where the greedy algorithm achieves an $O(\log\!\log n)$ guarantee. We ask whether a similar bound is possible for arbitrary base graphs.

While the greedy algorithm is optimal for adversarial arrivals and also for i.i.d. arrivals from regular base graphs (such as $G = K_n$), we show that it can perform poorly in general: there exist mildly irregular graphs $G$ for which greedy is $\widetildeΩ(\log n)$-competitive under i.i.d. arrivals. In sharp contrast, our main result is an $O(\log\!\log n)$-competitive online algorithm for every base graph $G$; this is optimal up to constant factors, since an $Ω(\log\!\log n)$ lower bound already holds even for the complete graph $G = K_n$. The key new idea is a notion of log-skewness for graphs, which captures the irregular substructures in $G$ that force the offline optimum to be large. Moreover, we show that any base graph can be decomposed into “skew-biregular” pieces at only $O(\log\!\log n)$ scales of log-skewness, and use this to design a decomposition-based variant of greedy that is $O(\log\!\log n)$-competitive.

Given an undirected, unweighted graph $G$, we aim to compute a 2-approximation of all-pairs shortest paths (APSP). This problem admits a natural lower bound of $Ω(n^2)$ since the output size is $Θ(n^2)$. A central goal in this area is to achieve a running time of $O(n^2)$. Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2001) designed an algorithm with a running time of $\widetilde{O}(n^2)$ that guarantees a 2-approximation only for pairs at a distance of at least $O(\log n)$.

Recently, Gupta (FOCS 2025) improved this bound, handling all pairs at a distance of at least $O(\log\log n)$. We nearly resolve this problem. We design a randomized algorithm that runs in $\widetilde{O}(n^2)$ time and, with high probability, guarantees a 2-approximation for all pairs at distance at least $c$, where $c \geq 0$ is a constant. Unlike the above two results, which were purely combinatorial, our algorithm combines combinatorial techniques with fast matrix multiplication (FMM).

The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Paths, Rooted Minor Checking, and Folio. A key ingredient behind the fixed-parameter tractability of the $k$-Disjoint Paths problem is the irrelevant-vertex technique. This machinery is governed by the Vital Linkage Theorem and the so-called Linkage Function $\ell$. However, despite its foundational role, the best known bounds on the Linkage Function are enormous and are only implicitly understood. The quantitative bounds behind these results have traditionally been so large that the resulting algorithms are regarded as "galactic".

Our main result is a general irrelevant-vertex theorem for a common generalisation of $k$-Disjoint Paths and Rooted Minor Checking for graphs of size at most $d,$ commonly called the $(k,d)$-Folio problem. Specifically, we show that for any graph $G$ in which the $k$ terminals are chosen from some set $R,$ if the treewidth of $G$ exceeds $β(k,b,d)\in$ $2^{{\bf poly}(b + d)}$ $\cdot {\bf poly}(k)$ then we can locate an irrelevant vertex for the $(k,d)$-Folio problem. Here, the quantity $b$ is the bidimensionality of $R,$ that is, the largest $b$ for which a $(b\times b)$-grid minor in $G$ can be rooted on $R$. Thus, the exponential component of the irrelevant-vertex threshold is driven by the bound on the bidimensionality, rather than by the number of terminals, and we argue that this dependence is essentially optimal up to polynomial factors. As a consequence, the Linkage Function satisfies $\ell(k) \in 2^{{\bf poly}(k)}$. Beyond its structural significance, our result yields improved parameter dependencies for algorithms for Disjoint Paths and Rooted Minor Checking}, and provides a quantitative improvement for a broad range of graph-minor-based algorithmic frameworks.

We show optimal FPT-approximability results for solving almost satisfiable systems of modular linear equations, completing the picture of the parameterized complexity and FPT-approximability landscape for the Min-$r$-Lin$(\mathbb{Z}_m)$ problem for every $r$ and $m$. In Min-$r$-Lin$(\mathbb{Z}_m)$, we are given a system $S$ of linear equations modulo $m$, each on at most $r$ variables, and the goal is to find a subset $Z \subseteq S$ of minimum cardinality such that $S - Z$ is satisfiable. The problem is UGC-hard to approximate within any constant factor for every $r \geq 2$ and $m \geq 2$, which motivates studying it through the lens of parameterized complexity with solution size as the parameter. From previous work (Dabrowski et al. SODA'23/TALG and ESA'25) we know that Min-$r$-Lin$(\mathbb{Z}_m)$ is W[1]-hard to FPT-approximate within any constant factor when $r \geq 3$, and that Min-$2$-Lin$(\mathbb{Z}_m)$ is in FPT when $m$ is prime and W[1]-hard when $m$ has at least two distinct prime factors. The case when $m = p^d$ for some prime $p$ and $d \geq 2$ has remained an open problem. We resolve this problem in this paper and prove the following:

(1) We prove that Min-$2$-Lin$(\mathbb{Z}_{p^d})$ is in FPT for every prime $p$ and $d \geq 1$. This implies that Min-$2$-Lin$(\mathbb{Z}_{m})$ can be FPT-approximated within a factor of $ω(m)$, where $ω$ is the number of distinct prime factors of $m$.

(2) We show that, under the ETH, Min-$2$-Lin$(\mathbb{Z}_m)$ cannot be FPT-approximated within $ω(m) - ε$ for any $ε> 0$.

Our main algorithmic contribution is a new technique coined balanced subgraph covering, which generalizes important balanced subgraphs of Dabrowski et al. (SODA'23/TALG) and shadow removal of Marx and Razgon (STOC'11/SICOMP). For the lower bounds, we develop a framework for proving optimality of FPT-approximation factors under the ETH.

We prove tight lower bounds for online multicalibration, establishing an information-theoretic separation from marginal calibration.

In the general setting where group functions can depend on both context and the learner's predictions, we prove an $Ω(T^{2/3})$ lower bound on expected multicalibration error using just three disjoint binary groups. This matches the upper bounds of Noarov et al. (2025) up to logarithmic factors and exceeds the $O(T^{2/3-\varepsilon})$ upper bound for marginal calibration (Dagan et al., 2025), thereby separating the two problems.

We then turn to lower bounds for the more difficult case of group functions that may depend on context but not on the learner's predictions. In this case, we establish an $\widetildeΩ(T^{2/3})$ lower bound for online multicalibration via an $O(\log^3 T)$-sized group family constructed from an orthonormal basis, again matching upper bounds up to logarithmic factors.

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum fraction of satisfied constraints along the transformation. In this paper, we prove that for any $q \geq 2$ and $\varepsilon > 0$, Maxmin $q$-CSP Reconfiguration is $\mathsf{PSPACE}$-hard to approximate within a factor of $\frac{1}{2^{q-1}}+\varepsilon$. To complement this hardness result, we prove that a $\bigl(\frac{1}{2^{q-1}}-\varepsilon\bigr)$-factor approximation for Maxmin $q$-CSP Reconfiguration is in $\mathsf{NP}$ in the perfect completeness case. These results establish the optimal $\mathsf{PSPACE}$-hardness of approximating Maxmin $q$-CSP Reconfiguration for every $q \geq 2$ under $\mathsf{NP} \neq \mathsf{PSPACE}$.

For an arbitrary family of predicates $\mathcal{F} \subseteq \{0,1\}^{[q]^k}$ and any $ε> 0$, we prove a single-pass, linear-space streaming lower bound against the gap promise problem of distinguishing instances of Max-CSP$({\mathcal{F}})$ with at most $β+ε$ fraction of satisfiable constraints from instances of with at least $γ-ε$ fraction of satisfiable constraints, whenever Max-CSP$({\mathcal{F}})$ admits a $(γ,β)$-integrality gap instance for the basic LP. This subsumes the linear-space lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC 2022), which applies only to a special subclass of CSPs with linear-algebraic structure. (Their result itself generalizes work of Kapralov and Krachun (STOC 2019) for Max-CUT.) Our approach identifies the right “analytic” analogues of previously-used linear-algebraic conditions; this yields substantial simplifications while capturing a much larger class of problems.

Our lower bound is essentially optimal for single-pass streaming, since: (1) All CSPs admit $(1-ε)$-approximations in quasilinear space, and (2) sublinear-space streaming algorithms can simulate the LP (on bounded-degree instances), giving approximation algorithms when integrality gap instances do not exist.

The starting point for our lower bound is a reduction from a "distributional implicit hidden partition” problem defined by Fei, Minzer, and Wang (STOC 2026) in the context of multi-pass streaming. Our result is an analogue of theirs in the single-pass setting, where we obtain a much stronger (and tight) space lower bound.

We present a randomized parallel algorithm in the PRAM model for $k$-vertex connectivity. Given an undirected simple graph, our algorithm either finds a set of fewer than $k$ vertices whose removal disconnects the graph or reports that no such set exists. The algorithm runs in $O(m \cdot \text{poly}(k, \log n))$ work and $O(\text{poly}(k, \log n))$ depth, which is nearly optimal for any $k = \text{poly}(\log n)$. Prior to our work, algorithms with near-linear work and polylogarithmic depth were known only for $k=3$ [Miller, Ramachandran, STOC'87]; for $k=4$, sequential algorithms achieving near-linear time were known [Forster, Nanongkai, Yang, Saranurak, Yingchareonthawornchai, SODA'20], but no algorithm with near-linear work could achieve even sublinear (on $n$) depth.

A major open problem in understanding shallow quantum circuits (QAC$^0$) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC$^0$: any QAC$^0$ circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC$^0$. Thus, proving a quantum analog of the seminal LMN theorem for AC$^0$ is necessary to bound the quantum circuit complexity of PARITY.

In the other direction, LMN does not fully capture the limitations of AC$^0$. For example, despite MAJORITY having $99\%$ of its weight on low-degree Fourier coefficients, no AC$^0$ circuit can non-trivially correlate with it. In contrast, we provide a QAC$^0$ circuit that achieves $(1-o(1))$ correlation with MAJORITY, establishing the first average-case decision separation between AC$^0$ and QAC$^0$. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC$^0$.

PARITY is also known to be equivalent in QAC$^0$ to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY $\in$ QAC$^0$.

Resolving a 1985 open problem of Gyárfás, we prove that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path $P_5$. Our approach introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment, which allows us to deduce the desired statement from the Erdős-Hajnal result for $P_5$.

$\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed.

We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

Many algorithms are designed to work well on average over inputs. When running such an algorithm on an arbitrary input, we must ask: Can we trust the algorithm on this input? We identify a new class of algorithmic problems addressing this, which we call "Quality Control Problems." These problems are specified by a (positive, real-valued) "quality function" $ρ$ and a distribution $D$ such that, with high probability, a sample drawn from $D$ is "high quality," meaning its $ρ$-value is near $1$. The goal is to accept inputs $x \sim D$ and reject potentially adversarially generated inputs $x$ with $ρ(x)$ far from $1$. The objective of quality control is thus weaker than either component problem: testing for "$ρ(x) \approx 1$" or testing if $x \sim D$, and offers the possibility of more efficient algorithms.

In this work, we consider the sublinear version of the quality control problem, where $D \in Δ(\{0,1\}^N)$ and the goal is to solve the $(D ,ρ)$-quality problem with $o(N)$ queries and time. As a case study, we consider random graphs, i.e., $D = G_{n,p}$ (and $N = \binom{n}2$), and the $k$-clique count function $ρ_k := C_k(G)/\mathbb{E}_{G' \sim G_{n,p}}[C_k(G')]$, where $C_k(G)$ is the number of $k$-cliques in $G$. Testing if $G \sim G_{n,p}$ with one sample, let alone with sublinear query access to the sample, is of course impossible. Testing if $ρ_k(G)\approx 1$ requires $p^{-Ω(k^2)}$ samples. In contrast, we show that the quality control problem for $G_{n,p}$ (with $n \geq p^{-ck}$ for some constant $c$) with respect to $ρ_k$ can be tested with $p^{-O(k)}$ queries and time, showing quality control is provably superpolynomially more efficient in this setting. More generally, for a motif $H$ of maximum degree $Δ(H)$, the respective quality control problem can be solved with $p^{-O(Δ(H))}$ queries and running time.

How many black-box queries to a quantum channel are needed to learn its full classical description? This question lies at the heart of quantum channel tomography (also known as quantum process tomography), a fundamental task in the characterization and validation of quantum hardware. Despite extensive prior work, the optimal query complexity for quantum channel tomography is far from fully understood.

In this paper, we study tomography of an unknown quantum channel with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, to within error $\varepsilon$. We identify the dilation rate $τ= r d_2 / d_1$ (which always satisfies $τ\geq 1$ due to the trace preservation of quantum channels) as a key parameter, and establish that the optimal query complexity of channel tomography exhibits distinct scaling laws across three regimes of $τ$.

• In the boundary regime ($τ= 1$): we show that the query complexity is $Θ(r d_1 d_2/\varepsilon)$ for Choi trace norm error $\varepsilon$, and is upper bounded by $O(\min\{r d_1^{1.5} d_2/\varepsilon, r d_1 d_2/\varepsilon^2\})$ and lower bounded by $Ω(r d_1 d_2/\varepsilon)$ for diamond norm error $\varepsilon$.
• In the away-from-boundary regime ($τ\geq 1+Ω(1)$): we show that the query complexity is $Θ(r d_1 d_2/\varepsilon^2)$ for both Choi trace norm and diamond norm errors $\varepsilon$.

Our results uncover a sharp Heisenberg-to-classical phase transition in the query complexity of quantum channel tomography: at $τ=1$, the optimal query complexity exhibits Heisenberg scaling $1/\varepsilon$, whereas for $τ\geq 1+Ω(1)$, it exhibits classical scaling $1/\varepsilon^2$. In addition, we show that in the near-boundary regime ($1< τ< 1+o(1)$), the query complexity exhibits a mixture of Heisenberg and classical scaling behaviors.

We show polylogarithmic mixing time bounds for the alternating-scan sampler for positively weighted restricted Boltzmann machines. This is done via analysing the same chain and the Glauber dynamics for ferromagnetic two-spin systems, where we obtain new mixing time bounds up to the critical thresholds.

We prove that $\mathrm{deg}(f) \leq \widetilde{O}(\mathrm{rdeg}(f)^3)$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994.

Let $g(X)$ be a polynomial over a finite field ${\mathbb F}_q$ with degree $o(q^{1/2})$, and let $χ$ be the quadratic residue character. We give a polynomial time algorithm to recover $g(X)$ (up to perfect square factors) given the values of $χ\circ g$ on ${\mathbb F}_q$, with up to a constant fraction of the values having errors. This was previously unknown even for the case of no errors.

We give a similar algorithm for additive characters of polynomials over fields of characteristic $2$. This gives the first polynomial time algorithm for decoding dual-BCH codes of polynomial dimension from a constant fraction of errors.

Our algorithms use ideas from Stepanov's polynomial method proof of the classical Weil bounds on character sums, as well as from the Berlekamp-Welch decoding algorithm for Reed-Solomon codes. A crucial role is played by what we call *pseudopolynomials*: high degree polynomials, all of whose derivatives behave like low degree polynomials on ${\mathbb F}_q$.

Both these results can be viewed as algorithmic versions of the Weil bounds for this setting.

We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of randomized hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses.

• For $η$-rate malicious noise, we show the optimal error is $\frac{1}{2} \cdot η/(1-η)$, improving on the optimal error of deterministic hypotheses by a factor of $1/2$. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can improve error by a factor of $6/7$.
• For $η$-rate nasty noise, we show the optimal error is $\frac{3}{2} \cdot η$ for distribution-independent learners and $η$ for fixed-distribution learners, both improving upon the optimal $2 η$ error of deterministic hypotheses. This closes a gap first noted by Bshouty et al. (Theoretical Computer Science 2002) when they introduced nasty noise and reiterated in the recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. (SODA 2026).
• For $η$-rate agnostic noise and the closely related nasty classification noise model, we show the optimal error is $η$, improving upon the optimal $2η$ error of deterministic hypotheses.

All of our learners have sample complexity linear in the VC-dimension of the concept class and polynomial in the inverse excess error. All except for the fixed-distribution nasty noise learner are time efficient given access to an oracle for empirical risk minimization.

Modern large language models generate text autoregressively, producing tokens one at a time. To study the learnability of such systems, Joshi et al. (COLT 2025) introduced a PAC-learning framework for next-token generators, the primitive underlying autoregressive models. In this framework, an unknown next-token generator maps a sequence of tokens to the next token and is iteratively applied for $T$ steps, producing a chain of tokens whose final token constitutes the model's output. The learning task is to learn the input-output mapping induced by this autoregressive process. Depending on the available supervision, training examples may reveal only the final output (End-to-End supervision) or the entire generated chain (Chain-of-Thought supervision). This raises two natural questions: how the sample complexity depends on the generation length $T$, and how much Chain-of-Thought supervision can reduce this dependence.

In this work we give a nearly complete answer to both questions by uncovering a taxonomy of how the sample complexity scales with $T$. For End-to-End learning, we show that the landscape is remarkably rich: subject to mild conditions, essentially any growth rate $r(T)$ between constant and linear can arise as the sample complexity, and combined with the linear upper bound of Joshi et al., this yields an essentially complete characterization. In contrast, under Chain-of-Thought supervision we show that the sample complexity is independent of $T$, demonstrating that access to intermediate reasoning steps can eliminate the dependence on the generation length altogether. Our analysis introduces new combinatorial tools, and as corollaries we resolve several open questions posed by Joshi et al. regarding the dependence of learnability on the generation length and the role of Chain-of-Thought supervision.

We consider the canonical multi-dimensional mechanism design setting: a seller has $m$ items for sale to $n$ additive bidders, with bidder $k$'s value $v_{k\ell}$ for item $\ell \in [m]$ drawn independently from distribution $D_{k\ell}$ supported on $[0,1]$. The seller begins with a mechanism $M'$ that is $\varepsilon$-Bayesian Incentive Compatible, and desires a new mechanism $M$ that is exactly Bayesian Incentive Compatible with minimal loss in revenue. Our main result is a black-box reduction that, given only sample access to each $D_{k\ell}$ and query access to $M'$, produces an $M$ with revenue at least that of $M'$ within an additive $O(n\sqrt{\varepsilon})$, resolving the main open problem left in [GW18]. The main distinction to prior work is our sample complexity of $\operatorname{poly}(n,m,1/\varepsilon)$ rather than $\operatorname{poly}(n,\exp(m),1/\varepsilon)$. A corollary of our main result (together with [GW18]) is an algorithm to find an up-to-$\varepsilon$ revenue-optimal mechanism using only $\operatorname{poly}(n,m,1/\varepsilon)$ samples from each $D_{k\ell}$. We also extend our results to the more general notion of Lipschitz valuations over independent items, which includes additive, unit-demand, and various other natural classes of valuations.

We show that three notions of rank for matrices of multilinear forms are equivalent. This result generalizes a classical result of Flanders, corrects a minor hole in work of Fortin and Reutenauer, answers a question of Lampert on the relation between the analytic and slice ranks of trilinear forms, and establishes a special case of the conjecture that the analytic and partition ranks of a tensor are equivalent.

We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof ($\mathsf{QMA}$) and the class of languages that can be verified with a classical proof ($\mathsf{QCMA}$). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice ($\mathsf{BQP}/\mathsf{qpoly}$) and the class of languages that can be decided with classical advice ($\mathsf{BQP}/\mathsf{poly}$), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024).

Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.

We prove that relative to a random oracle answering $O(\log n)$-bit queries, there exists a function computable in $O(n)$ time by a random-access machine (RAM) but requiring $n^2/polylog(n)$ time by any multitape Turing machine. This provides strong evidence that simulating RAMs on multitape Turing machines inherently incurs a nearly quadratic time overhead, since the random oracle can be heuristically instantiated by a concrete hash function such as SHA-256.

Our results show that the existence of a short high-utility protocol already suffices for efficient communication.

In particular, in a game with $n$ possible observations and $m$ actions:

• For any achievable target utility $α$, we give an algorithm with $\operatorname{poly}(n,m,1/ε)$ runtime that designs a protocol achieving utility at least $α-ε$ using only $2^{O(\mathrm{CC}_α(G))/ε^2}$ bits of communication. Here, $\mathrm{CC}_α(G)$ is the minimum number of bits used by any protocol, even a computationally inefficient one, to achieve utility $α$.
• We prove that this exponential dependence on $\mathrm{CC}_α(G)$ is tight up to a constant. That is, unless $\mathsf{P}=\mathsf{NP}$, no polynomial-time algorithm can in general find optimal protocols using less than $2^{\mathrm{CC}_α(G)-2}$ bits.

We note that our results strictly weaken the required assumptions of work in the multi-agent information aggregation literature, filling a gap that had remained elusive even for games with constant $\mathrm{CC}_α(G)$. In particular, prior guarantees for agreement-based information aggregation rely on structural assumptions such as informational substitutes [FNW23] or weak learnability [CGHG+26]. We show that these assumptions already imply $\mathrm{CC}_α(G)=O(1)$ and are therefore more restrictive conditions than required by our protocol to succeed. Moreover, we show that Aumann agreement [Aum76, Aar05] can be exponentially suboptimal even in low-complexity games: there are games of communication complexity $\mathrm{CC}(G)$ where agents reach agreement in $O(1)$ rounds but obtain no more than $2^{-\mathrm{CC}(G)/2}$ utility. We also introduce a notion of lasting agreement and show that while lasting agreement guarantees at least $2^{-\mathrm{CC}(G)/2}$ utility, reaching lasting agreement may require $Ω(n)$ rounds.

On a technical level, our results involve a novel strengthening of the Frieze–Kannan weak regularity lemma [FK99] and yield the following powerful polynomial-time transformation tool: for every communication game $G$, it constructs a game $\widehat{G}$ that is a “coarsening” of the agents' observation spaces into constant-size partitions, such that $G$ and $\widehat{G}$ are “indistinguishable” with respect to every short communication protocol. This coarsening theorem is the engine behind our algorithm and may be of independent interest.

We study shortest paths in directed graphs whose edge weights are of the form $$ \mathsf{wt}(e) = a_{e,1} λ_1 + a_{e,2} λ_2 + a_{e,3} λ_3 + \cdots + a_{e,d} λ_d + a_{e,d+1}.$$ Here, each $a_{e,i}\in\mathbb{R}$ is a fixed constant for each edge $e$, whereas each $λ_i\in\mathbb{R}$ is common across the entire graph. So, there could be different shortest paths in the graph for different values of the $λ_i$'s. This is called the Parametric Shortest Paths problem, and has been studied since the 1980s.

For $d=1$, Carstensen (1983) showed that the number of shortest paths in $n$-vertex graphs is at most $n^{O(\log n)}$. She also proved a matching lower bound of $n^{Ω(\log n)}$, later refined by Mulmuley & Shah (2001). For $d=2$, Gajjar & Radhakrishnan (2019) showed an upper bound of $n^{O(\log^2 n)}$. Barth, Funke & Proissl (2022) generalized their result to prove an upper bound of $n^{O_d(\log^d n)}$ for all positive integers $d$. The lower bound did not undergo any improvement over the years.

In this paper, we close this long line of research by showing an $n^{O(d\log n)}$ upper bound for all positive integers $d$, exponentially improving the previous upper bound. We observe that a matching lower bound of $n^{Ω(d\log n)}$ can be obtained from earlier works. We also show that our proof can be adapted to work for undirected graphs with positive edge weights. Furthermore, for directed graphs whose edge weights are univariate polynomials of degree at most $q$, we prove an upper bound of $n^{O(\log{n}+\log{q})}$. Finally, building upon work on the Point Location problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a Shortest Path Oracle which takes as input a point $\overline{x}\in \mathbb{R}^d$, and outputs a shortest path at $\overlineλ=\overline{x}$ in sublinear time (for a wide regime of $d$).

We study SINGLE-SOURCE SHORTEST PATH (SSSP) on unweighted intersection graphs whose node set corresponds to a set of $n$ constant-complexity objects in the plane. We prove SSSP can be solved in $O(U(n)\ \mathrm{polylog}\,n)$ expected time for any class of objects whose union complexity is $U(n)$. In particular, we obtain an $O(n 2^{α(n)}\log^2 n)$ algorithm for arbitrary pseudodisks, and an $O(λ_{s+2}(n)2^{O(\log^* n)} \log^2 n)$ algorithm for locally fat objects. This significantly extends the class of objects for which SSSP can be solved in $O(n\ \mathrm{polylog}\, n)$ time: so far, $O(n\ \mathrm{polylog}\, n)$ SSSP algorithms were not even known for pseudodisks that are fat and convex and similarly-sized.

Our second result concerns the DIAMETER problem, which asks for the maximum distance between any two nodes in a graph. Even for intersection graphs, near-quadratic algorithms are difficult to obtain, and the $O(n^2\ \mathrm{polylog}\, n)$ running time that follows from our SSSP algorithm is the first near-quadratic running time for such general classes of intersection graphs. Obtaining subquadratic running time is even more challenging. We prove that the diameter of a set of arbitrary pseudodisks can be computed almost exactly, namely up to an additive error of 2, in $\tilde{O}(n^{2-1/14})$ expected time. This generalizes and speeds up a recent algorithm by Chang, Gao, and Le (SoCG 2024) that works for similarly-sized disks (or similarly-sized pseudodisks that are fat and satisfy a strong monotonicity assumption) and runs in $\tilde{O}(n^{2-1/18})$ time. To this end, we develop a so-called star-based $r$-clustering for intersection graphs of pseudodisks, which is interesting in its own right. Our star-based $r$-clustering can also be used to obtain an almost exact distance oracle for pseudodisks that uses $O(n^{2-1/13})$ storage and has $O(1)$ query time.

A natural strengthening of an algorithm for the (promise) constraint satisfaction problem is its singleton version: we first fix a variable to an element from its domain, then run the algorithm, and remove the element from the domain if the answer is negative. Using the Hales-Jewett theorem, we characterize the power of the singleton versions of standard universal algorithms for the (promise) CSP over a fixed template in terms of the existence of polymorphisms with certain symmetries, which we call palette symmetric polymorphisms. By proving the existence of such polymorphisms we establish that the singleton version of the BLP+AIP algorithm solves all (multi-sorted) tractable CSPs over domains of size at most 7. We further show that already for domain size 8 there exists a relational structure arising from the dihedral group $\mathbf D_4$ that does not admit palette symmetric polymorphisms and cannot be solved by singleton BLP+AIP. By providing concrete CSP templates, we illustrate the limitations of linear programming, the power of the singleton versions, and the elegance of palette symmetric polymorphisms. Among tractable temporal templates, we exhibit a structure demonstrating that finiteness is crucial for the Hales-Jewett argument; nevertheless, by introducing generalized palette polymorphisms we establish tractability for each such template.

In 1972, Fredman proposes the problem of sorting under partial information: preprocess a directed acyclic graph $G$ with vertex set $X$ so that you can sort $X$ in $O(\log e(G))$ time, where $e(G)$ is the number of sorted orders compatible with $G$. Cardinal, Fiorini, Joret, Jungers and Munro [STOC'10] show that you can preprocess $G$ in $O(n^{2.5})$ time and then sort $X$ in $O(\log e(G) + n)$ time and $O(\log e(G))$ comparisons. Recent work of van der Hoog and Rutschmann [FOCS'24] implies an algorithm with $O(n^ω)$ preprocessing time where $ω< 2.372$ and $O(\log e(G))$ sorting time. Haeupler, Hladík, Iacono, Rozhoň, Tarjan and Tětek [SODA'25] achieve an overall running time of $O(\log e(G) + m)$. In this paper, we achieve tight bounds for this problem: $O(m)$ preprocessing time and $O(\log e(G))$ sorting time.

As a key ingredient, we design a new fast heap data structure that might be of independent theoretical interest.

We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A striking feature of this model is that at every positive constraint density, it is expected that a $1-o_N(1)$ fraction of solutions are strongly isolated, i.e. separated from all others by Hamming distance $Ω(N)$. At the same time, efficient algorithms are known to find solutions at certain positive constraint densities. This raises a natural question: can any isolated solution be algorithmically visible?

We answer this in the negative: no algorithm whose output is stable under a tiny Gaussian resampling of the disorder can reliably locate isolated solutions. We show that any stable algorithm has success probability at most $\frac{3\sqrt{17}-9}{4}+o_N(1)\leq 0.84233$. Furthermore, every stable algorithm that finds a solution with probability $1-o_N(1)$ finds an isolated solution with probability $o_N(1)$. The class of stable algorithms we consider includes degree-$D$ polynomials up to $D\leq o(N/\log N)$; under the low-degree heuristic [hopkins2018statistical], this suggests that locating strongly isolated solutions requires running time $\exp(\widetildeΘ(N))$.

Our proof does not use the overlap gap property. Instead, we show via Pitt's correlation inequality that after a random perturbation of the disorder, the number of solutions located close to a pre-existing isolated solution cannot concentrate at $1$.

Strassen's asymptotic spectrum offers a framework for analyzing the complexity of tensors. It has found applications in diverse areas, from computer science to additive combinatorics and quantum information. A long-standing open problem, dating back to 1991, asks whether Strassen's support functionals are universal spectral points, that is, points in the asymptotic spectrum of tensors.

In this paper, we answer this question in the affirmative by proving that the support functionals coincide with the quantum functionals - universal spectral points that are defined via entropy optimization on entanglement polytopes. We obtain this result as a special case of a general minimax formula for convex optimization on entanglement polytopes (and other moment polytopes) that has further applications to other tensor parameters, including the asymptotic slice rank. Our proof is based on a recent Fenchel-type duality theorem on Hadamard manifolds due to Hirai.

It is a folklore belief in the theory of spin glasses and disordered systems that out-of-equilibrium dynamics fail to find stable local optima exhibiting e.g. local strict convexity on physical time-scales. In the context of the Sherrington–Kirkpatrick spin glass, Behrens-Arpino-Kivva-Zdeborová and Minzer-Sah-Sawhney have recently conjectured that this obstruction may be inherent to all efficient algorithms, despite the existence of exponentially many such optima throughout the landscape. We prove this search problem exhibits strong low degree hardness for polynomial algorithms of degree $D\leq o(N)$: any such algorithm has probability $o(1)$ to output a stable local optimum. To the best of our knowledge, this is the first result to prove that even constant-degree polynomials have probability $o(1)$ to solve a random search problem without planted structure. To prove this, we develop a general-purpose enhancement of the ensemble overlap gap property, and as a byproduct improve previous results on spin glass optimization, maximum independent set, random $k$-SAT, and the Ising perceptron to strong low degree hardness. Finally for spherical spin glasses with no external field, we prove that Langevin dynamics does not find stable local optima within dimension-free time.

We prove two lower bounds for the first order oracle complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory. We first show that any such (possibly randomized) algorithm must make $\tildeΩ(\frac{d^2}{\sqrt{m}})$ oracle queries. For deterministic optimization algorithms, we show that $\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})$ queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of $\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})$ and $\tildeΩ(\frac{d^{5/3}}{m^{1/3}})$ for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around $m\approx d^2$, where a polylogarithmic change in memory leads to a $\mathsf{poly}(d)$ change in the number of required oracle calls. Further, when the suboptimality is polynomially small in $d$, our lower bound randomized algorithms is the first to show that $\tildeΩ(d^2)$ memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in $d$.

Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares (SoS) algorithm? A sufficient condition is t-wise uniformity, that is, each constraint has a t-wise uniform distribution of satisfying assignments, as shown by the lower bounds of Kothari, Mori, O'Donnell, and Witmer (STOC 2017). This condition is also necessary for random CSPs given by a predicate and uniformly random literals, due to the constant-degree SoS refutation of Allen, O'Donnell, and Witmer (FOCS 2015). For higher degree, Raghavendra, Rao, and Schramm (STOC 2017) gave a refutation for Boolean random CSPs with uniformly random literals, matching the lower bounds optimally in terms of the three-way tradeoff between constraint density, SoS degree, and strength of refutation.

Two long-standing open problems are to find a more general sufficient condition for SoS lower bounds, and to refute similar random CSPs not involving literals. We show that for a general random k-CSP, the necessary and sufficient hardness condition is not t-wise uniformity, but t-wise independence. We generalize the optimal three-way tradeoff to any random k-CSP, without assuming a Boolean domain or uniformly random literals.

Our analysis involves new Kikuchi matrices for odd order and for asymmetric tensors. It also uses the global correlation rounding technique of Barak, Raghavendra, and Steurer (FOCS 2011). To avoid the running-time penalty of this technique, we also give a spectral refutation algorithm.

We study the computational complexity of approximately computing the partition function of a spin system. Techniques based on standard counting-to-sampling reductions yield $\tilde{O}(n^2)$-time algorithms, where $n$ is the size of the input graph. We present new counting algorithms that break the quadratic-time barrier in a wide range of settings. For example, for the hardcore model of $λ$-weighted independent sets in graphs of maximum degree $Δ$, we obtain a $\tilde{O}(n^{2-δ})$-time approximate counting algorithm, for some constant $δ> 0$, when the fugacity $λ< \frac{1}{Δ-1}$, improving over the previous regime of $λ= o(Δ^{-3/2})$ by Anand, Feng, Freifeld, Guo, and Wang (2025). Our results apply broadly to many other spin systems, such as the Ising model, hypergraph independent sets, and vertex colorings.

Interestingly, our work reveals a deep connection between $\textit{subquadratic}$ counting and $\textit{perfect}$ marginal sampling. For two-spin systems such as the hardcore and Ising models, we show that the existence of perfect marginal samplers directly yields subquadratic counting algorithms in a $\textit{black-box}$ fashion. For general spin systems, we show that almost all existing perfect marginal samplers can be adapted to produce a sufficiently low-variance marginal estimator in sublinear time, leading to subquadratic counting algorithms.

We prove superpolynomial length lower bounds for the semantic tree-like Frege refutation system with bounded line size. Concretely, for any function $n^{2-\varepsilon} \leq s(n) \leq 2^{n^{1-\varepsilon}}$ we exhibit an explicit family $\mathcal{A}$ of $n$-variate CNF formulas $A$, each of size $|A| \le s(n)^{1+\varepsilon}$, such that if $A$ is chosen uniformly from $\mathcal{A}$, then asymptotically almost surely any tree-like Frege refutation of $A$ in line-size $s(n)$ is of length super-polynomial in $|A|$. Our lower bounds apply also to tree-like degree-$d$ threshold systems, for $d \approx \log\bigl(s(n)\bigr)$, that is, for $d$ up to $n^{1-\varepsilon}$. More generally, our lower bounds apply to the semantic version of these systems and to any semantic tree-like proof system where the number of distinct lines is bounded by $\exp\bigl(s(n)\bigr)$.

We initiate the study of distribution testing for probability distributions over the edges of a graph, motivated by the closely related question of “edge-distribution-free” graph property testing. The main results of this paper are nearly-tight bounds on testing bipartiteness, triangle-freeness and square-freeness of edge distributions, whose sample complexities are shown to scale as $Θ(n)$, $n^{4/3\pm o(1)}$ and $n^{9/8\pm o(1)}$, respectively.

The technical core of our paper lies in the proof of the upper bound for testing square-freeness, wherein we develop new techniques based on certain birthday-paradox-type lemmas that may be of independent interest. We will discuss how our techniques fit into the general framework of distribution-free property testing. We will also discuss how our results are conceptually connected with Turán problems and subgraph removal lemmas in extremal combinatorics.

We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate \[ \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] \] to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$.

The random sampling approach – estimating the mean by averaging $f$ over $O(1/\varepsilon^2)$ random samples – requires $O(R(f)/\varepsilon^2)$ total communication, where $R(f)$ is the randomized communication complexity of $f$. We design a new debiasing protocol which improves the dependence on $1/\varepsilon$ to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.

Strassen founded the theory of the asymptotic spectrum of tensors to study the complexity of matrix multiplication. A central challenge in this theory is to explicitly construct new spectral points. In Crelle 1991, Strassen proposed the upper support functionals $ζ^θ$ as candidate spectral points, where $θ$ ranges over a triangle $Θ$. Recent progress, involving tools and ideas from quantum information theory (Christandl-Vrana-Zuiddam, STOC 2018, JAMS 2021) and convex optimization (Hirai, 2025), culminated in the proof that the upper support functionals are indeed spectral points over the complex numbers (Sakabe-Doğan-Walter, 2026).

In this paper, we give an even clearer picture of the situation for support functionals when $θ$ lies along the edges of the triangle. We show that not only are these functionals spectral points, but that they are uniquely determined as spectral points by their behavior on matrix multiplication tensors. As our methods are algebraic, as a corollary this establishes for the first time the existence of nontrivial spectral points over arbitrary fields.

As part of our argument, we show a close connection between the edge support functionals and Harder-Narasimhan filtrations from quiver representation theory. We thus show, using recent work in algorithmic invariant theory, that these support functionals can be computed in deterministic polynomial time. Other ingredients of our proof include a new criterion for abstractly characterizing asymptotic tensor ranks by spectral points, and a characterization of the edge support functionals in terms of matrix multiplication capacity. As another application of these tools, we prove the existence of spectral points for higher-mode tensors beyond those currently known.

We give a near-linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be achieved by the known proofs of the Four Color Theorem (4CT). Technically speaking, we show the following significant generalization of the 4CT: every planar triangulation contains linearly many pairwise non-touching reducible configurations or pairwise non-crossing obstructing cycles of length at most 5 (which all allow for making effective 4-coloring reductions).

The known proofs of the 4CT only show the existence of a single reducible configuration or obstructing cycle in the above statement. The existence is proved using the discharging method based on combinatorial curvature. It identifies reducible configurations in parts where the local neighborhood has positive combinatorial curvature. Our result significantly strengthens the known proofs of 4CT, showing that we can also find reductions in large “flat" parts where the curvature is zero, and moreover, we can make reductions almost anywhere in a given planar graph. This also opens possibilities for extensions to higher surfaces since we can find such flat parts in any large-width triangulation of any fixed surface.

From a computational perspective, the old proofs allowed us to apply induction on a problem that is smaller by some additive constant. The inductive step took linear time, resulting in a quadratic total time. With our linear number of reducible configurations or obstructing cycles, we can reduce the problem size by a constant factor. Our inductive step takes $O(n\log n)$ time, yielding a 4-coloring in $O(n\log n)$ total time. To efficiently handle a linear number of reducible configurations, we need them to be sufficiently robust to be useful in other applications. All our reducible configurations are what is known as D-reducible.

In this paper we prove Aldous's conjecture from 1987 that there is no backoff protocol that is stable for any positive arrival rate. The setting is a communication channel for coordinating requests for a shared resource. Each user who wants to access the resource makes a request by sending a message to the channel. The users don't have any way to communicate with each other, except by sending messages to the channel. The operation of the channel proceeds in discrete time steps. If exactly one message is sent to the channel during a time step then this message succeeds (and leaves the system). If multiple messages are sent during a time step then these messages collide. Each of the users that sent these messages therefore waits a random amount of time before re-sending. A backoff protocol is a randomised algorithm for determining how long to wait – the waiting time is a function of how many collisions a message has had. Specifically, a backoff protocol is described by a send sequence $\overline{p} = (p_0,p_1,p_2,\ldots)$. If a message has had $k$ collisions before a time step then, with probability $p_k$, it sends during that time step, whereas with probability $1-p_k$ it is silent (waiting for later). The most famous backoff protocol is binary exponential backoff, where $p_k = 2^{-k}$. Under Kelly's model, in which the number of new messages that arrive in the system at each time step is given by a Poisson random variable with mean $λ$, Aldous proved that binary exponential backoff is unstable for any positive $λ$. He conjectured that the same is true for any backoff protocol. We prove this conjecture.

We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright.

Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | ρ|w\rangle$ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $χ^2$-divergence as corollaries.

We show that there is an absolute constant $c>0$ such that every large connected $n$-vertex Cayley graph with degree $d\geq n^{1-c}$ has a Hamilton cycle. This makes progress towards the Lovász conjecture and improves upon the previous best result of this form due to Christofides, Hladký, and Máthé from 2014 concerning graphs with $d\geq \varepsilon n$. Our proof avoids the use of Szemerédi's regularity lemma and relies instead on an efficient arithmetic regularity lemma specialised to Cayley graphs.

We give an $O(\log^2 n)$-query algorithm for finding a Tarski fixed point over the $4$-dimensional lattice $[n]^4$, matching the $Ω(\log^2 n)$ lower bound of [EPRY20]. Additionally, our algorithm yields an ${O(\log^{\lceil (k-1)/3\rceil+1} n)}$-query algorithm for any constant $k$, improving the previous best upper bound ${O(\log^{\lceil (k-1)/2\rceil+1} n)}$ of [CL22].

Our algorithm uses a new framework based on safe partial-information functions. The latter were introduced in [CLY23] to give a reduction from the Tarski problem to its promised version with a unique fixed point. This is the first time they are directly used to design new algorithms for Tarski fixed points.

In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of CSP$(P)$ is called non-redundant if it does not contain any redundant clause. The non-redundancy (NRD) of a predicate $P$ is the maximum number of clauses in a non-redundant instance of CSP$(P)$, as a function of the number of variables $n$. Recent progress has shown that non-redundancy is crucially linked to many other important questions in computer science and mathematics including sparsification, kernelization, query complexity, universal algebra, and extremal combinatorics. Given that non-redundancy is a nexus for many of these important problems, the central goal of this paper is to more deeply understand non-redundancy.

Our first main result shows that for every rational number $r \ge 1$, there exists a finite CSP predicate $P$ such that the non-redundancy of $P$ is $Θ(n^r)$. Our second main result explores the concept of conditional non-redundancy first coined by Brakensiek and Guruswami [STOC 2025]. We completely classify the conditional non-redundancy of all binary predicates (i.e., constraints on two variables) by connecting these non-redundancy problems to the structure of high-girth graphs in extremal combinatorics.

Inspired by these concrete results, we build off the work of Carbonnel [CP 2022] to develop an algebraic theory of conditional non-redundancy. As an application of this algebraic theory, we revisit the notion of Mal'tsev embeddings, which is the most general technique known to date for establishing that a predicate has linear non-redundancy. For example, we provide the first example of predicate with a Mal'tsev embedding that cannot be attributed to the structure of an Abelian group, but rather to the structure of the quantum Pauli group.

A membership-inference attack gets the output of a learning algorithm, and a target individual, and tries to determine whether this individual is a member of the training data or an independent sample from the same distribution. A successful membership-inference attack typically requires the attacker to have some knowledge about the distribution that the training data was sampled from, and this knowledge is often captured through a set of independent reference samples from that distribution. In this work we study how much information the attacker needs for membership inference by investigating the sample complexity-the minimum number of reference samples required-for a successful attack. We study this question in the fundamental setting of Gaussian mean estimation where the learning algorithm is given $n$ samples from a Gaussian distribution $\mathcal{N}(μ,Σ)$ in $d$ dimensions, and tries to estimate $\hatμ$ up to some error $\mathbb{E}[\|\hat μ- μ\|^2_Σ]\leq ρ^2 d$. Our result shows that for membership inference in this setting, $Ω(n + n^2 ρ^2)$ samples can be necessary to carry out any attack that competes with a fully informed attacker. Our result is the first to show that the attacker sometimes needs many more samples than the training algorithm uses to train the model. This result has significant implications for practice, as all attacks used in practice have a restricted form that uses $O(n)$ samples and cannot benefit from $ω(n)$ samples. Thus, these attacks may be underestimating the possibility of membership inference, and better attacks may be possible when information about the distribution is easy to obtain.

We give an algorithm for PAC learning intersections of $k$ halfspaces with a $ρ$ margin to within error $\varepsilon$ that runs in time $\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/ρ) \log k})\right)$. Notably, this improves on prior work which had an exponential dependence on either $k$ or $ρ^{-1}$ and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in $k$ and $ρ$ in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least $ρ$ from the boundary of the polyhedron, making it applicable to continuous distributions as well.

In this paper, we introduce a new quantum query lower bound framework. It is inspired by Zhandry's compressed oracle technique, but it also subsumes the polynomial method as a special case. Compared to Zhandry's technique, our approach has two key differences. First, we do not use any oracles (except for the standard input oracle), and define “knowledge” directly through the expansion of the state of the algorithm in the Fourier basis. Second, we allow arbitrary probability distributions of inputs.

We show how this framework behaves on the problem of finding equal elements in the input string. In particular, we demonstrate its power by proving a first tight quantum query lower bound for the k-Distinctness problem.

We study fair allocation of indivisible goods among strategic agents with additive valuations. Motivated by impossibility results for deterministic truthful mechanisms, we focus on randomized mechanisms that are Truthful-in-Expectation (TIE). From a fairness perspective, we seek to guarantee every agent a large fraction of their Maximin Share (MMS) ex-post. Among other results, Bu and Tao [FOCS 2025] presented a TIE mechanism that guarantees $\frac{1}{n}$-MMS ex-post. First, we present an ordinal TIE mechanism that guarantees $\frac{1}{H_n + 2}$-MMS ex-post, where $H_n$ is the $n$-th harmonic number ($H_n \simeq \ln n$). This is nearly best possible for ordinal mechanisms, as even non-truthful ordinal allocation algorithms cannot obtain an approximation better than $\frac{1}{H_n}$. We then show that with just a small amount of additional cardinal information, the ex-post guarantee can be improved to $Ω(\frac{1}{\log\log n})$-MMS, at the cost of relaxing the incentive requirement to $(1-\varepsilon(n))$-TIE for negligible $\varepsilon(n)$. Finally, for two agents, we present a TIE mechanism that is $\frac{2}{3}$-MMS ex-post.

All our mechanisms are ex-ante proportional (thus also providing “Best-of-Both-Worlds” results) and run in polynomial time. Moreover, all our results extend to the truncated proportional share (TPS), which is at least as large as the MMS. Our two-agent $\frac{2}{3}$-TPS result is best possible for the TPS.

A fundamental question in streaming complexity is whether every space-efficient turnstile algorithm is implicitly a linear sketch. The landmark work of Li, Nguyen, and Woodruff [LNW14] established an equivalence between the two, but their reduction requires a stream length that is at least doubly exponential in the dimension $n$. In the opposite direction, results by Kallaugher and Price [KP20] demonstrate a separation for streams of linear length, showing that the equivalence does not hold in general. The most natural and practically relevant regime – polynomial-length streams – has therefore remained open.

We show that polynomial-length turnstile algorithms admit linear-sketch simulations. More precisely, if a turnstile algorithm uses $S$ bits of space and succeeds on all streams of length $\mathrm{poly}(D, n)$, then on final vectors $x$ with $\|x\|_2 \le D$, its output can be recovered from $O(S)$ linear measurements of $x$, using $O(S \log S)$ bits overall. For smooth problems under appropriate input distributions, a mollified version of the reduction yields a bounded-entry sketch with $O(S / \log D)$ measurements and optimal $O(S)$ total space. Our results extend to strict turnstile streams and non-uniform Read-Once Branching Programs (ROBPs).

Our proof departs from prior transition-graph based machinery, relying instead on a Fourier-analytic framework and tools from additive combinatorics to extract discrete linear measurements. Our analysis shows that any $S$-bit algorithm can only be sensitive to a low-dimensional lattice of heavy Fourier frequencies, which we then use to construct the rows of the sketching matrix. Consequently, we obtain new lower bounds for polynomial-length streams via existing real sketching and communication lower bounds.

AI agents are increasingly deployed to interact with other agents on behalf of users and organizations. We ask whether two such agents, operated by different entities, can carry out a parallel secret conversation while still producing a transcript that is computationally indistinguishable from an honest interaction, even to a strong passive auditor that knows the full model descriptions, the protocol, and the agents' private contexts. Building on recent work on watermarking and steganography for LLMs, we first show that if the parties possess an interaction-unique secret key, they can facilitate an optimal-rate covert conversation: the hidden conversation can exploit essentially all of the entropy present in the honest message distributions.

Our main contributions concern extending this to the keyless setting, where the agents begin with no shared secret. We show that covert key exchange, and hence covert conversation, is possible even when each model has an arbitrary private context, and their messages are short and fully adaptive, assuming only that sufficiently many individual messages have at least constant min-entropy. This stands in contrast to previous covert communication works, which relied on the min-entropy in each individual message growing with the security parameter. To obtain this, we introduce a new cryptographic primitive, which we call pseudorandom noise-resilient key exchange: a key-exchange protocol whose public transcript is pseudorandom while still remaining correct under constant noise. We study this primitive, giving several constructions relevant to our application as well as strong limitations showing that more naive variants are impossible or vulnerable to efficient attacks.

These results show that transcript auditing alone cannot rule out covert coordination between AI agents, and identify a new cryptographic theory that may be of independent interest.

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored.

We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$.

A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits.

These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.