Papers

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.

For any tripartite relation $R\subseteq \mathbb{Z}^3$, the $R$-Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R$. The All-Edge $R$-Triangle problem asks to determine for every edge whether it is contained in such a triangle. It is known that $R$-Triangle and All-Edge $R$-Triangle are subcubically fine-grained equivalent for every $R$ [Vassilevska W.-Williams'10]. However, while it is conjectured that these problems are tightly equivalent, this reduction only shows that if $R$-Triangle has an $O(n^{3-\epsilon})$-time algorithm for some $\epsilon>0$, then All-Edge $R$-Triangle has an $O(n^{3-\epsilon/3})$-time algorithm. This paper provides a strong unconditional barrier to a tight equivalence: the reduction of [Vassilevska W.-Williams'10] is optimal for black-box reductions that work for arbitrary $R$. We give further results about black-box reductions between a variety of $R$-triangle problems. Our positive results yield new reductions between several classes of triangle and matrix problems — for instance, we demonstrate that an $O(n^{2.53})$-time algorithm for computing equality or dominance product would imply an improvement on known algorithms for computing boolean $(\min, +)$-product, giving the first conditional lower bound for dominance and equality product. Our negative results can be thought of as barriers against natural fine-grained proof techniques. Besides the result that a tighter equivalence between $R$-Triangle and All-Edge $R$-Triangle is not possible, we also show that no appropriately "black-box" reductions are capable of demonstrating a subcubic equivalence between triangle counting and binary integer matrix multiplication, or a tight equivalence between boolean matrix multiplication and listing $n^2$ triangles, and more, despite the fact that all of these equivalences are conjectured to hold.

We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the term clone of such a central extension. We develop the difference clonoid of such a central extension and use it to show that the number of $2$-step nilpotent algebras on a fixed finite set is finite if and only if the set is of squarefree order. The subpower membership problem for a finite algebraic structure $\mathbb{A}$ is the problem of deciding on input $a_1,\dots,a_k, b \in A^n$, whether $b$ is in the subalgebra of $\mathbb{A}^n$ generated by $a_1, \dots, a_k$. We show that for a large class of nilpotent Mal'cev algebras the subpower membership problem is solvable in polynomial time, in particular for $2$-step nilpotent Mal'cev algebras of squarefree order.

For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (Theor. Comput. Sci., 2013) for fixed finite/cofinite \((\sigma,\rho)\)-problems and of Bergougnoux and Kanté (SIAM J. Discrete Math., 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for Weighted Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no \(2^{o(w^2)}n^{O(1)}\)-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry \(k^2\) assignment bits through cuts of rank \(O(k)\). The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of \((\sigma,\rho)\)-set problems. This family includes cases in which \(\sigma\) is neither finite nor cofinite and contains the entire nontrivial cofinite–cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis (\(\#\mathrm{ETH}\)), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width \(w\) is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

We consider a fundamental problem of mixedness testing: Given $n$ copies of an $N$-qubit state $\rho$, determine whether $\rho = \mathbb{I}_d/d$ or $\|\rho-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \tilde{\Theta}\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

In a graph $G$, a set of edges $F$ is called a forcing set if there exists a unique perfect matching $M$ such that $F \subseteq M$. Similarly, a set of edges $A$ is called an anti-forcing set if the graph with edge set $ E(G)\setminus A$ has a unique perfect matching. It is known that, given a bipartite graph $G$ of maximum degree~$3$ and a perfect matching $M$, the problem of deciding whether there exists a forcing set of size at most $k$ for $M$ is NP-complete. Moreover, given a bipartite graph $G$ of maximum degree~$4$ and a perfect matching $M$, the problem of deciding whether there exists an anti-forcing set of size at most $k$ for $M$ is NP-complete. Furthermore, given a bipartite graph of maximum degree~$5$, the problem of deciding whether there exists a perfect matching $M$ that can be made unique by a forcing set of size at most $k$ is also NP-complete. In contrast, the computational complexity of deciding whether there exists a perfect matching $M$ that can be made unique by an anti-forcing set of size at most $k$ is not known, even for general graphs. In this paper, we show that all of these problems remain NP-complete even when restricted to bipartite graphs of maximum degree~$3$.

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $\delta>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - \delta$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $\Omega(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a combinatorial framework originally motivated by Boolean satisfiability, based on triplet structures and a filter that we call Simple Vertex Intersection (SVI). We formalise the core of TLS, including its translation from 3-CNF, the clearing procedure, and the SVI algorithm. For the well-formed sliding-window fragment, we prove explicit polynomial-time bounds for the filter stages and verify the translation and intersection operations. Our main contribution is a precise correctness boundary: for general formulas, SVI non-emptiness is necessary but not sufficient for satisfiability; for aligned structures, we prove a full bi-implication, extended to systems of structures. We also formalise the grouped-window translation and provide a formal counterexample to its completeness. We introduce VFR (Verified Filter for Romanov's triplet logic), an extracted OCaml prototype that implements a verified decision procedure for the sliding-window fragment and a sound filter for general 3-CNF, with a Python runtime and Docker packaging. Benchmarks corroborate the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises over 23,000 lines of code, with 424 proved lemmas and no unproved assumptions.

We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as “pseudo-distributions”). As a consequence, we resolve a question left open by the work of O'Donnell and Schramm [OS19] that they had explicitly attributed to the lack of such an inequality. A Cauchy-Schwarz inequality is exactly satisfied by pseudo-distributions satisfying the constraints of the sum-of-squares semidefinite programming hierarchy and already has scores of applications. However, the proof there requires global positive semidefiniteness. Our approximate version, on the other hand, relies only on local positive semidefiniteness satisfied by the Sherali-Adams pseudo-distributions. Our formulation loses an additive error that scales with the L1 norm of the coefficients of the constituent polynomials, and this loss is asymptotically tight. Our proof is elementary and relies on a simple sampling argument. As an application, we resolve a question left open in the work of O'Donnell and Schramm that gives a trade-off between constraint density and the Sherali-Adams degree for refuting random constraint satisfaction problems. Specifically, for odd arity CSPs, we show that the constraint density requirement for a given degree can be improved by a polynomial factor in $n$. Along the way, we observe that by a simple extension, the results in their work extend to a more general semirandom setting.

The cluster graphs on $n$ vertices, the disjoint unions of complete graphs, have the integer partitions of $n$ as their isomorphism classes, and the quotient edit distance $q^*(\lambda,\mu)=\min_{\sigma\in S_n}|E(G_\lambda)\triangle\sigma E(G_\mu)|$ makes that set a metric space. Its geometry and its complexity both issue from one identity: $q^*$ is an affine function of the maximum of $\lVert X\rVert_F^2$ over the contingency tables with margins $\lambda$ and $\mu$. Our main result is an explicit optimal embedding. The weighted dyadic sums of the Ferrers staircase, taken at the critical exponent $\frac14$, give a map $F_n$ into $\ell_2^{\,<4n}$ that acts on a single partition and is computable in $O(n)$ time, and its distortion is $\Theta(n^{1/4})$. That order is optimal, since $c_2(\mathcal K_n)=\Theta(n^{1/4})$: the lower half follows from a $\Theta(\sqrt n)$-dimensional Hamming cube of partitions and Enflo's theorem, so the determination needs no other external input. The analytic core is a scale-free inverse inequality for every integer sequence with $v(1)=v(N+1)=0$ and $v(s)-v(s+1)\in s\mathbb Z$: its critical dyadic energy is at least $\lVert v\rVert_1^2/(63504\sqrt{\mathrm{TV}(v)})$. Combinatorially the same identity yields two explicit $\ell_1$ models, the vertex-mass metric on sorted degree sequences with $\frac12\delta_1\le q^*<\frac32\delta_1$ and the block-energy metric with $q^*\le B\le2q^*-1$, both constants optimal; hence $c_1(\mathcal K_n)\le2$, and an $O(n\log n)$-time algorithm returns an alignment of cost below $2q^*$ carrying the certificate $q^*\in[\lceil(B+1)/2\rceil,B]$. Computationally, deciding $q^*(\lambda,\mu)\le Q$ is strongly NP-complete and admits no FPTAS, while the farthest alignment is polynomial-time solvable. The best constant in the inverse inequality remains open; an exactly solvable chirp family caps it at $\frac23$.

We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot be solved in f(n)|I|^{O(1)} time for any computable function f where |I| is the size of the encoding and n is the number of variables.

In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account for several factors, including agents' cost for reaching the bus stops, their travel time, or the energy consumption of the buses. We study the complexity of several variants of this problem, focusing on how the objective function and the models for agents' walking costs influence the problem complexity. After observing that even the simplest agent cost model leads to hardness on general networks, we consider networks with tree structure. Our main findings are as follows. First, allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars. Second, consistent agent models (where agents differ only in their starting points and destinations) make the problem easier in some cases. Finally, allowing agents to choose between using the bus and walking directly can make the problem considerably harder. Most of our hardness results show not only classical NP-hardness but also parameterized intractability for the natural parameter $k$, the number of bus stops.

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement “low-degree testing” using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka “honest”) prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $\alpha>0$, there exists $\beta>0$, such that for sufficiently large $n$, if a set $A\subseteq \mathbb{F}_p^n$ has density at least $\alpha$, then it contains at least $\beta$ fraction of all somewhat restricted $3$-APs. Our proof builds on recently developed machinery from [Bhangale, Khot, Minzer, 2026]. Our main new ingredient is an arithmetic regularity lemma for patterns such as somewhat restricted 3-APs. This result is in the spirit of arithmetic regularity lemmas from the theory of Gowers uniformity norms [Green, Tao, 2010] and may be of independent interest.

Many AI systems make decisions locally, even when every realized output must obey an additive conservation law, such as selecting exactly a fixed number of items. This constraint can be statistically invisible: small subsets of a balanced fixed-budget output look increasingly independent, yet communication-free coordinate-parallel generation needs exponentially many pre-shared plans, while a sequential exact sampler needs only logarithmic memory. We study product measures conditioned on additive conservation laws in the intermediate regime where one plan is selected before a fixed-order pass, every plan is a bounded-state stochastic executor whose support is entirely legal, and the mixture of plan laws approximates the target distribution in total variation. Our main result identifies the optimal asymptotic selector rate, up to constant factors, with the killed spectral profile of the conservation-difference walk. The resulting coordination cost decreases as an inverse power of live-state width, with an exponent determined by intrinsic conservation rank rather than alphabet size; the law extends to noncentral budgets and heterogeneous local scores. The converse is driven by a state-versus-resource-sum obstruction, while a rate-matching construction compiles discrepancy control into exact-support finite-state plans. Complementary results characterize block-parallel plan complexity and the benefit of programmable output order. Together, these results show precisely how online memory substitutes for front-loaded coordination in exact-support generation.

Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, there exists a constant $c>0$ such that no polynomial-time algorithm can always produce a solution whose weight is within $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $\Omega(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal–dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.

For every $n\geq 9$ that is a multiple of 3, we construct an explicit access structure on $n$ participants. In every perfect secret-sharing scheme realising this access structure, if $S$ denotes the random secret, then the sum of the share entropies is at least $\left(\frac{n^2}{9}+\frac{2n}{3}\right)H(S)$, and some participant has share entropy at least $\left(\frac{n}{6}+\frac12\right)H(S)$. After normalisation by $H(S)$, these are respectively $\Omega(n^2)$ and $\Omega(n)$ lower bounds and also give the same asymptotic lower bounds on the total and largest expected binary lengths of the shares. This improves by a logarithmic factor the longstanding general lower bounds of $\Omega(n^2/\log n)$ for total share size and $\Omega(n/\log n)$ for maximum share size due to Csirmaz. The proof uses only elementary Shannon inequalities, together with some averaging arguments. The Shannon-information method has universal $O(n^2)$ and $O(n)$ ceilings for the total and maximum normalised entropy lower bounds it can certify, so our construction reaches both ceilings up to constant factors.

The current best bounds on the matrix multiplication exponent $\omega$ are obtained through a refinement of the laser method called combination loss analysis (Duan et al., 2022; Williams et al., 2024; Alman et al., 2025). In this note, we address the optimization problem at the core of this approach and propose several improvements. First, we reformulate the optimization problem allowing us to solve it in a larger setting than was previously possible. Second, we leverage recent advances in machine learning to design a new optimization algorithm for this problem. Finally, we refine the resulting optimization algorithm with AlphaEvolve. Our combined approach yields an upper bound of $\omega$ < 2.371177, improving the previous best bound of 2.371339.

We show how to compile an arbitrary classical circuit into a fault-tolerant circuit, which performs the desired computation even when an almost-linear number of bits are adversarially chosen and corrupted in each timestep. Using a variant of this fault-tolerance scheme that only detects (rather than corrects) corruptions, we give a new construction of probabilistically checkable proofs (PCPs) for NP with polylogarithmic query complexity. This PCP construction from fault-tolerance presents a promising candidate for quantization by the work of Anshu, Breuckmann, and Nguyen (STOC'24), who provided a roadmap for constructing quantum PCPs via fault-tolerance.

We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on $\bar{N}$ logical qudits of depth $\bar{T}$, we construct a fault-tolerant circuit on $N=\text{poly}(\bar{N})$ physical qudits of depth $\bar{T}\cdot\bar{N}^{o(1)}$, which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number $N^{1-o(1)}$ of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.

We show that, on trees, any locally checkable labeling problem (LCL) $\Pi$ that can be solved by an $n^{o(1)}$-dependent distribution can also be solved by an $O(\log n)$-round deterministic LOCAL algorithm. The result is obtained through a rake-and-compress-style decomposition of the input tree, and local simulations of the bounded dependent distribution on the components of the decomposition. As a corollary to our result, any LCL problem on trees can either be solved by an $O(\log n)$ deterministic LOCAL algorithm, or requires $n^{\Omega(1)}$ rounds to solve by a quantum-LOCAL algorithm.

Budget-constrained advertisers commonly rely on two control mechanisms: pacing scales bids, whereas throttling randomizes participation. We prove that, in second-price auctions, these two different mechanisms share the same sharp approximation-hardness threshold. For pacing, computing a $\gamma$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $\gamma\in[0,1)$. For throttling, computing a $\delta$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $\delta\in(0,1)$. At parameter $1$, the complementarity requirement becomes vacuous and the all-zero solution is feasible. That is, approximation does not eliminate the fixed-point barrier at any nontrivial parameter value.

The tensor rank of a bilinear map is the least number of multiplications any bilinear algorithm needs to compute it; for the multiplication of an algebra it measures how cheaply the algebra can be multiplied at all. For the even-dimensional real normed division algebras it is $3$ for the complex numbers and $8$ for the quaternions, both classical, while for the octonions $\mathbb{O}$ only a range was known: at least $15$ (Fiduccia and Zalcstein, 1977) and at most $30$ (Cariow and Cariowa). We prove $$18 \le \operatorname{R}_{\mathbb{R}}(T_{\mathbb{O}}) \le 25.$$ The lower bound peels the eight slices of $T_{\mathbb{O}}$ down to two and bounds the rank of the surviving pencil through the octonion norm. Nothing in it is special to dimension $8$: the same steps give $\operatorname{R}_{\mathbb{R}}(T_A) \ge \frac{5}{2}n - 2$ for every real normed division algebra $A$ of even dimension $n$, sharp for $\mathbb{C}$ and $\mathbb{H}$ and the best bound we know for $\mathbb{O}$. The upper bound is a separate construction, an explicit rank-$25$ decomposition certified by a Krawczyk argument, in exact rational arithmetic, to sit within $10^{-6}$ of an exact one. The same two arguments pin down the rank of a smaller three-slice quaternion tensor $\tau$, giving $\operatorname{R}_{\mathbb{R}}(\tau) = 7$. The Lean 4 kernel checks the lower bounds and the Krawczyk existence principle; the accompanying scripts check the certificate's finitely many exact-rational inequalities.

In a world where valuable artifacts are increasingly created, completed, or processed by LLMs, the central economic question is not only what the LLM can produce, but what value remains in the inputs (i.e., the prompts) we provide to it. Given a prompt, hint, critique, problem statement, or partial solution that helps an LLM produce an artifact $z$—a proof, program, design, or scientific hypothesis—how should we measure the value of that input? Intuitively, an input is valuable when it makes the target artifact easier for the model to generate: either by increasing its sampling probability, or by reducing the thinking time needed to find it. We propose a computational Levin–Kolmogorov complexity approach to this problem, by appropriately replacing the universal Turing machine in the classical definitions by the LLM itself. Concretely, we introduce an LLM-relative notion of probabilistic Levin–Kolmogorov complexity $pKt$—treating the model's thinking as the random tape of the program, and charging logarithmically for it in Levin's manner—and define prompt value as algorithmic mutual information with respect to $pKt$. This captures the intuition above: a prompt having $b$ bits of value for an artifact $z$ makes $z$ $2^b$ times “easier to obtain”, by multiplying the success probability by $2^b$, by dividing the required computation by $2^b$, or by any corresponding tradeoff between probability and computation. In contrast to the classical notion of algorithmic mutual information, ours is efficiently estimable. We additionally show that, under a natural reproduction experiment, a prompt value of \(b\) bits means that reproducing \(z\) without the prompt has median token cost \(2^b\) times that of reproducing it with the prompt.

Input-convex neural networks permit globally tractable minimization over their inputs, so one might expect their global regularity to be tractable in low input dimension. We prove exact and accuracy-sensitive barriers to this expectation. Given a bias-free one-hidden-layer ReLU network $f(x)=\sum_{r=1}^n \mathrm{ReLU}(a_r^\top x)$ with unit positive output weights, deciding whether its global Euclidean Lipschitz constant is at least a rational threshold is NP-complete and W[1]-hard when parameterized by the input dimension $d$. The same holds on the unit ball and with integral first-layer weights having at most nine nonzeros. More sharply, no deterministic multiplicative approximation scheme runs in $g(d)\mathrm{poly}(\mathcal B,1/\varepsilon)$ time unless FPT equals W[1]. Under the Exponential Time Hypothesis, no such algorithm runs in $g(d)(\mathcal B+1/\varepsilon)^{o(d/\log d)}$ time. Thus accuracy cannot have a polynomial dependence separated from dimension. The exact result resolves the Euclidean case of an open problem posed at COLT 2025 and left open by the ICLR 2026 parameterized hardness theory for general two-layer networks. The approximation barrier is specific to generator-presented zonotopes, complementing known $(1/\varepsilon)^{O(d)}$-time schemes and an analogous barrier for halfspace-presented polytopes. Our lifted-selector reduction has an inverse-polynomial radial gap, proved through a quantitative theorem for rational cyclic zonogons. Equivalently, the results apply to Euclidean zonotope radius and positive-semidefinite binary quadratic maximization parameterized by rank. Convexity makes minimization easy, but it does not make global sensitivity fixed-parameter tractable or permit a dimension-separated fully polynomial accuracy guarantee.