Papers

We present a top-down depth-four circuit lower bound for Majority function by extending recent work of Göös, Riazanov, Sofronova, and Sokolov (FOCS 2023), who gave a top-down proof of a depth-four circuit lower bound for Parity which relies on the robust sunflower to construct a mirror set and the block unpredictability to find the local limits. The main challenge for the case of Majority is to construct a corresponding mirror set, the difference is that to flip the value of Majority function, one may have to flip many bits of the input Boolean string, while for Parity, flipping one bit suffices. We avoid this flipping by considering slices of the Boolean cube, that is, Boolean strings of fixed Hamming weight approximately $n/2$.

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$\Omega\left( \frac{\Delta L}{\epsilon^2} + \frac{\Delta L\sigma^2}{\epsilon^4} \right)$$ queries to find a point with expected gradient norm at most \(\epsilon\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.

Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, the *weak rank principle* (WRank) states the equation $XY = A$ is unsatisfiable when $m>n$ and rank of $A$ exceeds $n$. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP). As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, while still supporting analogous applications. *Generators for PCR$_{F_2}$*: We prove exponential size lower bounds for algebraic, perfect matching, and bamboo-tree encodings of WRank in PCR$_{F_2}$. The latter encoding is the most relevant for applications to circuit lower-bound formulas, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Using a standard iteration technique we amplify the stretch to exponential. This resolves the open problem concerning the construction of proof complexity generators with good stretch for PCR$_{F_2}$. *Generators for Sherali–Adams:* We develop a new size lower-bound technique showing that WRank, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a pseudoexpectation tailored specifically to the rank principle (and incompatible with WPHP). *Circuit lower bound formulas:* We show that PCR$_{F_2}$ does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits. This settles the open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR$_{F_2}$. *Strength of the weak rank principle:* Finally, we show that WRank is *necessary* for proving NC$^2$ circuit lower bounds and, for odd primes $p$, *sufficient* within the theory corresponding to AC$^{0}[p]$ for deriving AC$^{0}[p]$ lower bounds.

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform $\mathrm{AC}^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k \log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-OV and $(n/k)^{\Omega(k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth. For growing $k = n^{o(1)}$ and every fixed depth $d$, we obtain the unconditional floor $n^{\Omega_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{\Omega(k)}$ at depth two for both top-gate orientations, and at depth three for top-disjunction (OR-AND-OR) circuits, with no restriction on fan-in or polarity. The depth-three argument rests on a minterm bound for a single CNF: a fixed CNF is very unlikely to become true for the first time exactly when a randomly planted copy is completed. Assuming a pattern-uniform strengthening of the Li-Razborov-Rossman source lower bound, the same projections complete the $k = n^{o(1)}$ frontier with $n^{\Omega_d(k)}$ for the missing top-conjunction depth-three orientation and for every fixed depth $d \geq 4$. The framework is modular in the source bound, so improved source bounds pass directly to all three targets. All direct $k$-XOR bounds concern odd $k$; a black-box lift covers even $k$, and the $k$-SUM projection works for both parities. At the bit width $m = \Theta(k \log(\mathrm{e}n/k))$ used by our projection, a block-carry $\Sigma_3$ upper bound of size $(n/k)^{O(k)}$ matches the depth-three lower bound up to constants in the exponent. Gaps remain at depth two and for top-conjunction depth three.

We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[ \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \] Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.

We study per-colour independent (k)-rainbow domination and its connection with independent domination in generalized prisms. Building on the known prism identity and the trivial regime above the maximum degree, we focus on the boundary case where the number of colours equals the maximum degree. For every fixed (k\ge 3), we prove that the decision problem remains NP-complete even on a highly restricted class of graphs: (C_4)-free, bipartite, ((k,2))-biregular subdivision graphs arising from simple (k)-regular graphs. The reduction gives an exact correspondence between optimal rainbow-independent dominating functions on the subdivision graph and proper (k)-edge-colourings of the original graph. We also introduce an excess parameter measuring how far the domination number lies above its natural lower bound. For cubic graphs, this excess coincides with the classical edge-colouring degree and therefore with standard resistance parameters for subcubic graphs. These results reveal a sharp one-unit threshold: above the maximum degree the problem becomes trivial for every graph, while at the boundary NP-hard instances already occur within a very narrow structural family.

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{\Phi_k})$ is known, where $$ \Phi_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{\Psi_k})$, where $$ \Psi_k=\Phi_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$ The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.

Let \(G\) be a connected simple undirected graph. A vertex \(w\) is said to strongly resolve a pair of distinct vertices \(u, v \in V(G)\) if either there exists an isometric path (i.e.~a shortest path) from \(w\) to \(u\) that contains \(v\), or there exists an isometric path from \(w\) to \(v\) that contains \(u\). A subset \(S \subseteq V(G)\) is said to strongly resolve \(G\) if every pair of distinct vertices of \(G\) is strongly resolved by at least one vertex in \(S\). In the Strong Metric Dimension problem, the input consists of a graph \(G\) and a positive integer \(k\), and the objective is to determine whether there exists a subset \(S \subseteq V(G)\) of size at most \(k\) that strongly resolves \(G\). In this article, we show that Strong Metric Dimension is \NP-complete even on \((i)\) graphs of diameter two, and \((ii)\) graphs of constant pathwidth and constant feedback vertex set number.

Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). In this note, we resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires the $n$-qubit Fanout operation. Formally, let $\mathsf{QFT}_q$ be the gate acting on $n = \lceil \log q \rceil$ qubits that computes the QFT under modulus $q$. It is known that any $n$-qubit $\mathsf{QFT}_q$ can be implemented in constant depth using $\mathsf{FANOUT}_n$, i.e. $\mathsf{QFT}_q \in \mathsf{QAC}^0_f$. We prove the converse by using a $\mathsf{QFT}_q$ gate to construct a state of "non-negligible felinity". Consequently, $\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}$. In the case of $q = 2^n$, such as in Shor's, we approximate $\mathsf{FANOUT}_n$ using a single $\mathsf{QFT}_{2^n}$ gate and $O(1)$ two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.

For a homogeneous polynomial f of degree d, the degree-k restricted strength C_k(f) is the least number of products needed to write f with factor degrees k and d-k. We introduce a two-cut coherence parameter C_{k,l}(f): the least r such that f = sum_{i,j=1}^{r} p_i m_{ij} q_j with deg p_i = k, deg m_{ij} = l-k, and deg q_j = d-l. This requires two degree interfaces to be realized by a single common factorization. We show it equals the minimum common endpoint width of a three-block compressed transfer network, and equivalently the minimum, over all tensor lifts of f through commutative multiplication, of the larger of the two tensor-train endpoint ranks. In particular it lower-bounds homogeneous ABP width. Our main result is an extraction-completeness theorem for quintics at cuts (1,3). Let D(f) be the largest polynomial slice rank C_1 of a second directional derivative of f, and let t = C_3(f). Over an algebraically closed field of characteristic zero, ceil(D(f)/3) <= Cbar_{1,3}(f) <= C_{1,3}(f) <= t*D(f) + 2t^2, where Cbar denotes border complexity. Hence when C_3 is bounded, ordinary and border two-cut coherence are equivalent up to constants to a one-cut obstruction exposed by a second derivative. We also prove a border-stable lifting separation. For coprime nonzero cubics A and B, the quintic L = abA + cdB has ordinary and border local values C_1 = C_3 = 2, while ceil(max{C_1(A), C_1(B)}/3) <= Cbar_{1,3}(L) <= C_1(A) + C_1(B). Taking A to be a Fermat cubic in n variables, for which we show C_1 = ceil(n/2), gives an unbounded gap between separately optimal local interfaces and a common interface, even in border complexity. This refutes any universal bound of the form C_{k,l} <= C_k + C_l.

For sufficiently large $N$ which is a power of 2, we prove that changing at most one percent of the entries of the $N\times N$ Walsh-Hadamard Transform cannot reduce its rank over $\mathbb{F}_3$ to $\lfloor \log^2 N/80\rfloor$ or below. To the best of our knowledge, this is the first constant-fraction rigidity lower bound for an explicit matrix family at a superlogarithmic target rank over any choice of field, inching toward the parameters in Razborov's program for communication complexity lower bounds.

The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than $\Omega(n)$. Prior works bypass this lower bound by relaxing the online model through recourse, random arrival order, or seeding the algorithm with an offline sample of the underlying input. We instead ask whether additional structure in the input itself can overcome this lower bound. We study weighted correlation clustering under probability constraints, where $w^+_{uv}+w^-_{uv}=1$ for every $uv$ edge, and triangle inequality constraints, where the negative weights $w^-$ satisfy triangle inequality. While this version of correlation clustering is well-studied in the offline setting, we initiate its online study and give a deterministic online algorithm that maintains a clustering whose total weighted disagreement cost is within an $O(1)$ factor of the offline optimum, against adversarial arrival order. This is the first constant-competitive online algorithm for a natural minimization variant of correlation clustering in the fully online model, and shows that metric consistency on the edge weights separates tractable from intractable online instances.

For every $\varepsilon > 0$, it is NP-hard to $n^{1-\varepsilon}$-approximate Max Independent Set in $n$-vertex graphs [Hastad '96, Zuckerman '07]. In triangle-free graphs, a simple argument gives a polynomial-time $n^{1/2}$-approximation algorithm, whereas, for every $\varepsilon > 0$, an $n^{1/4-\varepsilon}$-approximation algorithm would imply that NP $\subseteq$ BPP [Bonnet, Thomassé, Tran, Watrigant; ESA '20]. In this note, we close this gap by proving the corresponding hardness against $n^{1/2-\varepsilon}$-approximation algorithms. The reduction is very simple and uses the Moser-Tardos resampling algorithm to make the constructed graphs triangle-free. The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates. We generalize this scheme and show that, for any nonempty finite family $\mathcal F$ of graphs, each containing at least one cycle, for any $\varepsilon > 0$, an $n^{\mu(\mathcal F)-\varepsilon}$-approximation algorithm for Max Independent Set in graphs excluding every member of $\mathcal F$ as a subgraph implies that NP $\subseteq$ BPP, where $\mu(\mathcal F) := 1 - \max\limits_{H \in \mathcal F}~\min\limits_{U \subseteq V(H), H[U] \text{contains a cycle}} (|U|-2)/(|E(H[U])|-1)$.

The red-blue pebble game is a well known two-player game on graphs that has been used in the past as a tool to analyze complexity measures in several computation models as well as proof systems. We define a new way to measure the cost of the game, the blue cost, which only counts the number of pebbles that are colored blue during the game. This new measure characterizes exactly several space bounds in tree-like and negative Resolution. In particular we prove that for any unsatiafiable formula $F$, the clause space requirements of the formula in tree-like Resolution, exactly coincide with the minimum blue pebbling cost of the game played on a refutation graph of $F$ (not necessarily a tree). This exactly parallels the known result for general Resolution in terms of the standard black pebble game, and improves the existing approximated characterization of tree-like space in terms of reversible pebbling. We show that the blue pebbling cost is also well suited for analyzing the space requirements of the lifted pebbling formulas $Peb_G[\vee]$ and $Peb_G[\oplus]$ in the two Resolution restrictions. In the case of tree-like Resolution, the clause space of $Peb_G[\vee]$ asymptotically coincides with the blue cost of the underlying graph $G$. For the case of negative Resolution, we obtain almost matching upper and lower bounds for the space in the two classes of lifted formulas, similar to the ones existing for general Resolution. We also prove a close to optimal space separation between tree-like and negative Resolution, presenting a class of formulas with $n$ variables that require clause space $\Omega(\frac{n}{\log n})$ in negative Resolution, but have constant space tree-like refutations. This contrasts with the fact that negative Resolution can simulate tree-like Resolution with only a small increase in size.

The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems. However, a recent sequence of counterexamples shows that low-degree indistinguishability does not, in general, rule out efficient noise-tolerant distinguishers; see Buhai et al. (2025) and Mao (2026). Motivated by these developments, Hsieh et al. (2026) initiated the study of rigorous consequences of the low-degree heuristic. In this work, we continue this program for planted-graph problems. Let $Q_n=G(n,c/n)$, and let $P_n$ be obtained by planting a uniformly random copy of a deterministic graph $\Gamma_n$ into an independent sample from $Q_n$. In the supercritical regime $c>1$, we show that if $P_n$ is degree-$D_n$ indistinguishable from $Q_n$ and $\operatorname{tw}(\Gamma_n)=o(D_n/\log n)$, then a noisy version of $P_n$ is asymptotically indistinguishable from $Q_n$. Here $\operatorname{tw}(\Gamma_n)$ denotes the treewidth of $\Gamma_n$, a measure of how efficiently the graph can be decomposed into tree-like pieces. In the critical and subcritical regimes $0<c\leq 1$, the same conclusion holds whenever $D_n=\omega(\log n)$, without any treewidth assumption. Our proof has two main ingredients. First, we uncover a correspondence between the subgraph-count and automorphism factors in the Fourier expansion and counts of isomorphism triples. Second, we cut the decomposition tree into subtrees, breaking each large Fourier support into low-degree pieces that meet at only a few interface vertices, and use noise to absorb the cost of reassembling them. At and below criticality, the low-degree assumption rules out short cycles, while noise destroys the remaining long cycles.

We obtain exponential upper bounds on approximate generalized weight and generalized sparsity in terms of the deepest transition depth D(F), and show that these bounds are optimal up to constant factors in the exponent. We further characterize approximate generalized sparsity, establish a dual lower-bound framework based on exponential restriction profiles, and derive a Paturi-type characterization relating approximate generalized weight to quantum query complexity.

In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the number of violated pairs (edges across different clusters plus non-edges within clusters). In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandating certain pairs to be in the same cluster and certain pairs to be in different clusters. In this work, we identify Constrained Correlation Clustering as a variant of Correlation Clustering for which optimal approximations might be within reach, and make progress towards this front. Constrained Correlation Clustering is APX-Hard, and the optimal approximation factor is known to lie in $(\frac{24}{23},3]$. We significantly tighten this gap, by showing that the optimal approximation factor lies in $[2,\frac{16}{7}-\gamma)$ for a small constant $\gamma>0$. Our lower bound of $2$ shows a separation between Correlation Clustering (which admits an $1.485+\epsilon$ approximation) and Constrained Correlation Clustering\footnote{The same hardness result was obtained independently by Cao and Xu~\cite{cao2026clusterdeletionhardapproximate}.}. Our upper bound of $\frac{16}{7}-\gamma$ uses the Sherali-Adams relaxation and goes beyond straightforward Triangle-Based analysis; more precisely, our algorithm belongs to a natural class of pivoting algorithms for which we prove that a straightforward Triangle-Based analysis cannot prove a better-than-$\frac{16}{7}$ approximation. Finally, as a byproduct of our techniques, we completely resolve the approximability of Cluster Deletion. Cluster Deletion is a well-studied special case of Constrained Correlation Clustering for which a $2$-approximation algorithm is known. We show that this is optimal, as our lower bound holds even for this special case.

We introduce a hierarchy consisting of stage machines, stage domains, and stage languages generated by semantic operators. The central result is a Predictor Impossibility Theorem (PITT), which shows that no effective predictor family can uniformly determine all stage languages of our hierarchy. The proof makes use of a pseudo-complement construction to obtain a language that yields a contradiction with every language in P. We then define an aggregate language MIS and establish a formal Slice Theorem connecting aggregate inputs to individual stage languages. This provides a rigorous Bridge Theorem from polynomial-time decidability of MIS to the existence of an effective predictor family. By utilizing succinct representations, the aggregate language is shown to be undecidable in deterministic polynomial time. Under the aggregate growth condition defining valid aggregate objects, MIS is shown to belong to NP. Combining these two results yields our main theorem: MIS in NP setminus P. The paper is organized so that PITT stands independently as a theoretic result, while the complexity-theoretic consequences are derived from the aggregate-language framework. The method does not relativize, algebrize, or naturalize.

We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounded number of input permutations (Fischer et al., ESA '25). Our result is tight, since an Ulam median of three permutations can be computed in polynomial time (Chakraborty–Das–Krauthgamer, SODA '21).

This paper presents a high-level report on an ongoing project aiming to leverage implicit approaches based on discrete ordinary differential equations (ODEs) to study multiple complexity classes, even beyond small circuit and polynomial-time classes. Stimulated by recent ODE-based characterizations of polynomial-time functions (FP) and classes over the reals, the research project outlined here pushes this investigation further into counting and alternation. Specifically, we present a uniform framework, built upon a single base algebra and a unified family of schemas, where complexity levels, such as those of the polynomial and counting hierarchies, are captured simply by the nesting depth of ODE operators. Crucially, our approach starts from a base class much weaker than FP, thus strengthening existing recursion-theoretic treatments and establishing a natural connection to descriptive complexity. Moreover, by isolating three elementary schemas, our framework makes the computational content of linearity restrictions completely transparent while extending ODE-based implicit complexity to previously unaddressed counting classes, such as oplusP. More generally, this work establishes a clear bridge between differentiation and counting, offering a fresh perspective on the relationships between different complexity classes, which remains the object of ongoing and future research.

Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$. We obtain a polynomial time algorithm that achieves a $(k/2^k)$-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, due to Makarychev and Makarychev (arXiv:1206.3603). Assuming the Unique Games Conjecture, De and Mossel (arXiv:1202.5258) showed that achieving an approximation ratio better than $(k+1)/2^k$ for odd $k$ and $(k+2)/2^k$ for even $k$, is NP-hard. The main technical ingredient is an extension of a recently established Gaussian comparison inequality, used to resolve the Weak Simplex Conjecture in coding theory (arXiv:2607.14087).

Slime Trail is a two-player combinatorial game in which the players alternately move a shared token to an adjacent vertex, permanently removing each vertex the token leaves, while attempting to reach a goal node. Ferland and Burke (2017) proved that Slime Trail is PSPACE-complete on arbitrary planar graphs and asked whether the same holds for the grid version actually used in play. We resolve this open problem by proving that Cardinal Grid Slime Trail, that is, Slime Trail on a square grid with four-directional movement, is PSPACE-complete. We adapt their QBF reduction to the grid setting, designing grid-compatible gadgets that respect the degree-4 bound and the parity constraints of the integer lattice. We further show the construction extends, under a 45-degree rotation, to the eight-directional variant.

Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimension characterizes stronger information-theoretic guarantees [RLT25]. Neither restricts per-output computation. The cumulative-mistake objective in mistake-bounded generation makes finite failure prefixes quantitative [KPR26], and a per-output query budget exposes their computational source. Polynomial-time algorithms are known for parities, conjunctions, and monotone functions with polynomially many maxterms [JKO26]. We ask whether information-theoretic ease can coexist with bounded-access computational hardness. Relative to a random oracle $H$, we answer yes by constructing a countable collection $C^\star$ of infinite languages with closure dimension zero. Almost surely on the same $H$, an unbounded generator makes zero mistakes on every target and every complete distinct enumeration. Yet, writing $\lambda$ for the target-seed length, every fixed uniform generator $G$ with polynomially many oracle queries in $\lambda$ and the output index $i$ has a constant $c_G>0$ such that, for every sufficiently large $\lambda$, some target incurs more than $2^{c_G\lambda}$ expected mistakes within its first $2(\lceil 2^{c_G\lambda}\rceil+1)$ canonical outputs. Infinite accidental agreement enables exhaustive search; sparse queries hide fresh target values. Thus, in the random-oracle model, zero-mistake information-theoretic generation coexists with a generator-dependent exponential lower bound on worst-case expected mistakes under polynomial-query access.

Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than-$2$ approximations for Cluster Deletion. We rule out this possibility under the Unique Games Conjecture: Cluster Deletion is NP-hard to approximate within a factor of $2-\epsilon$ for every fixed $\epsilon>0$, matching the known $2$-approximation [Veldt et al., WWW 2018]. Our approximation-preserving reduction from Vertex Cover also implies NP-hardness of approximation within $\sqrt2-\epsilon$. We also show that better-than-$2$ approximations are possible in restricted settings. We close the paper with a brief discussion of the relationship between Cluster Editing and Bad Triangle Transversal. In particular, we give a $31$-vertex graph~$G$ for which the two optimal values differ, answering an open question of Adriaens and Tatti [ICML 2026].

We ask whether asymptotic recursion depth determines the expressive strength of a bounded recursive algebra, and prove that it does not. We replace ordinary predecessor recursion by generalized-inverse descent along a fixed iterate $g_n^{[l]}$ and obtain classes $H^m_{n,l}$, where $m$ measures initial-function strength, $n$ the growth row, and $l$ the traversal stride. For all rows $n,n'\ge2$ we prove an exact inclusion criterion. At a fixed row $n\ge2$ three regimes occur: below the critical basis ($m<n$), equal-row inclusion is exactly reverse divisibility $l'\mid l$; at $m=n$ every stride collapses to one class; and from $m=n+1$ this class is ordinary bounded recursion $E^m$. Hence pairwise $\Theta$-equivalent descent depths can induce infinite descending chains, infinite antichains, and copies of every finite partial order. The separation is therefore controlled by traversal alignment rather than by growth rate or recursion depth alone. The proof combines exact-depth simulation, trace sparsity, and selected dependency chains. The exceptional doubling row has the same reverse-divisibility order at basis zero, but all strides collapse from basis one onward; from basis three it equals ordinary bounded recursion, while at basis two $H^2_{1,l}\subsetneq FP$. At basis zero the doubling-row classes are proper subclasses of deterministic functional logspace, so the same dual-divisibility order already occurs inside $FL$.

We study several additional properties of parity based bit-counting complexity classes ${\bf B_{|0| \oplus}P}$ and ${\bf B_{|1| \oplus}P}$. We first prove that ${\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$ and since ${\bf C_=P}={\bf ES}={\bf MNS}$ is already known, we establish that ${\bf C_=P}={\bf ES}={\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$. We then prove that ${\bf PP}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}$ and ${\bf PP}\subseteq{\bf P}^{{\bf B_{|0|\oplus}P}}$, which consequently yields ${\bf P}^{\bf PP}={\bf P}^{\bf B_{|0|\oplus}P}={\bf P}^{\bf B_{|1|\oplus}P}$. We then demonstrate that the same method can be used to prove ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|1|\oplus}P}}$ and ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|0|\oplus}P}}$. We also show that the parity based bit-counting hierarchies contain ${\bf CH}$.

Multi-head attention layers produce vector representations that support multiple downstream tasks. We establish bounds on the number of heads required in two simple and concrete multi-task scenarios. In the first scenario, a vector representation is sought so that linear predictors can compute both the smallest and largest numbers in a given list. In this case, it is known two attention heads with small embedding dimension and bit precision level suffice. We prove that a single attention head requires exponentially higher embedding dimension or precision level. In the second scenario, a vector representation is sought so that a polynomial threshold function can compute the XOR of a given string of $n$ bits. This scenario is analogous to the first one for $n=2$, since XOR is readily computed by a linear function using a vector representation that encodes both the AND and the OR of the two bits. We observe that $n$-bit XOR requires the product of the number of heads and the polynomial degree to be at least $n$, and we construct multi-head attention layers that match this lower bound. These results generalize to arbitrary (symmetric) Boolean functions, where the bound is given in terms of the threshold degree.

This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.

The direct sum problem in computational complexity asks whether solving $n$ independent instances of a computational task inherently requires $n$ times the resources needed to solve a single instance. In this paper, we resolve a central form of the direct sum conjecture in randomized communication complexity. Specifically, we prove that the "amortized expected randomized communication complexity" of any function is exactly equal to its "zero-error information complexity"—a measure of the precise amount of information the communicating parties must reveal about their inputs to compute the function without error. This result also provides a tight characterization of the amortized "worst-case" randomized communication complexity up to a constant factor. To achieve our exact characterization, we introduce a new single-instance protocol embedding equipped with a prefix-verification mechanism to accurately localize global errors. Furthermore, we apply our new structural theorems to the fundamental Set-Disjointness problem. Our resulting exact asymptotic bounds for Set-Disjointness successfully refute a conjecture in DFHL18 regarding its scaling behavior.