claims depot shelf
P versus NP
Formal claims (Lean)
-
The paper's central discovery is the exact complexity classification of portfolio regret. Given a portfolio $\Pi$ and a threshold $t$, deciding whether $R_{\mathrm{reg}}(\Pi)\le t$ holds — where $R_{\mathrm{reg}}(\Pi)=\sup_{u\in U}(V_u^*(s_\iota)-\max_{\pi\in\Pi}V_u^\pi(s_\iota))$ — is $\forall\mathbb{R}$-complete, and the hardness already holds for deterministic policies, acyclic $(s,a)$-rectangu
-
The paper's core claim is that Fortune's theorem can be made discoverable: students who know only basic programming can, in groups, find the two rules that turn an exponentially large self-reducibility tree into a polynomially large one. The first rule, drawn from the framework Fortune inherited from Berman, is to trim every node at a level whose S-label has already appeared to the left, keeping o
-
The paper claims Theorem 1: LA-MAPF is PSPACE-complete. Membership in PSPACE comes from storing only the current configuration and using the classical theorem that nondeterministic polynomial space equals deterministic polynomial space, avoiding the need to store the exponentially long configuration history. Hardness comes from a polynomial-time reduction from Restricted Sliding Tokens: contract e
-
On the paper's own terms, the main theorem is that Model-Consistency---given circuits $P$ and $Q$ over a query universe of size $2^{\ell(d+1)+d}$, is there a distribution $\mu$ over $n = 2^d$ Boolean variables with $\mathrm{Inc}_{P,Q}(\mu) \le \tau$---admits a polynomial-time interactive PCP. The verifier's protocol (Algorithm 6) runs one encoding-proximity test, two sum-checks, two marginal check
-
The paper's central claim is Theorem 1.1: every depth-4 circuit computing the n-bit Majority function requires at least $2^{n^{1/3-o(1)}}$ gates. The proof follows the three-step top-down template of the recent depth-four Parity lower bound: greedily choose a sub-circuit that maximizes the rejected zero-side set, construct a mirror set on the one-side, pass to the q-local limits, and reach a contr
-
The central claim is that standard derandomization hardness can replace the random oracle in proofs of space. Under the hypothesis that E=DTIME[$2^{{O(n)}}$] is hard for exponential-size nondeterministic circuits, together with a semi-universal SNARG for P, Construction 1 is sound against every time-τ prover storing at most n − C n log log n / √log n bits, with negligible accepting probability (Co
-
The central discovery is that the weak rank principle WRank_m^n(A)—the family of polynomial equations ∑_k x_{i,k} y_{k,j} = A_{i,j} with m>n and rank(A)>n—admits exponential PCR_F2 refutation lower bounds that are independent of m. In the strongest bamboo-tree encoding, every refutation of BTRank_m^n(A) has size $2^{{Ω(n)}}$, for every matrix A over F2; the algebraic encoding and a perfect-matchin
-
The central claim is that three algebraically different target problems share one witness-selection skeleton with colored subgraph isomorphism, and that the correspondence is computation-free: a depth-zero projection replaces every target input bit by a constant or a negated source bit, so any circuit computing a target would compute the source at the same depth and size. For a simple pattern $P$
-
The central claim is that three algebraically different target problems share one witness-selection skeleton with colored subgraph isomorphism, and that the correspondence is computation-free: a depth-zero projection replaces every target input bit by a constant or a negated source bit, so any circuit computing a target would compute the source at the same depth and size. For a simple pattern $P$
-
The central claim is Theorem 6: the aggregate language MIS belongs to NP but not to P. On the paper's own terms, MIS accepts a valid aggregate tuple $U_i = (u_1, \dots, u_m)$ over a stage domain $D_i$ exactly when at least one component is accepted by the stage language $C_i$. The non-P direction runs through the Bridge Theorem: a polynomial-time decider for MIS would let one construct, for every
-
On the paper's own terms, the central claim is a uniform 'one algebra, many classes' theorem family. Starting from $\mathrm{ACDL} = \mathrm{FAC}^0$, the schemas $\mathrm{ODE}^{\lor}$ (existential bounded search), $\mathrm{ODE}^{\land}$ (universal bounded search), and $\mathrm{ODE}^{\#}$ (summation) are the only ingredients needed to move up the polynomial and counting hierarchies: Theorem 5 states
-
Relative to a random oracle $H$, the countable collection $\mathcal C^*$ of graph languages $L_b=\{\langle\lambda,i,H(b,i)\rangle:i\in\mathbb N\}$, with $b\in\{0,1\}^\lambda$, has closure dimension zero almost surely. On that same oracle an unbounded generator makes zero mistakes on every target $L_b$ under every complete distinct enumeration, the empty-history output being secured by an infinite
-
On its own terms, the paper proves Theorem 1.1: there is no polynomial-time algorithm that always returns a cluster deletion set within a factor of $\sqrt{2}-\epsilon$ of optimal unless P = NP, and no algorithm within a factor of $2-\epsilon$ unless the Unique Games Conjecture is false. These match the existing 2-approximation, so the approximation threshold for Cluster Deletion coincides with tha
-
The central claim is that parity-based bit-counting classes B_{|0|⊕P} and B_{|1|⊕P} are Turing-equivalent to PP in the deterministic polynomial-time setting: P^PP = $P^{{B_{|0|⊕P}}$} = $P^{{B_{|1|⊕P}}$}. The paper proves this by showing a deterministic polynomial-time machine with either oracle can recover all bits of any #P value A(x). The recovery pads A(x) to X(x)=2^n + A(x), and for each bit p
-
The central claim is that parity-based bit-counting classes B_{|0|⊕P} and B_{|1|⊕P} are Turing-equivalent to PP in the deterministic polynomial-time setting: P^PP = $P^{{B_{|0|⊕P}}$} = $P^{{B_{|1|⊕P}}$}. The paper proves this by showing a deterministic polynomial-time machine with either oracle can recover all bits of any #P value A(x). The recovery pads A(x) to X(x)=2^n + A(x), and for each bit p
-
On the paper's own terms, the discovery is that identical numerical catalogues do not eliminate the hardness of numerical three-dimensional matching. A unary polynomial reduction replaces the three asymmetric source classes by three labeled copies of one weighted occurrence set, then forces, through a finite role filter and degree equations, exactly one main incidence per port; those main incidenc
-
The paper's central claim, stated in its own terms, is that a single argument shape — locate the silent assumption behind an accepted result, promote it to a variable, and prove what happens once it is allowed to vary — recurs across cryptography, the semantics of derivations, special relativity, the space of physical laws, and algorithmic randomness, and that in one instance it produces a contrad
-
The central discovery is that the function classes defined by median outputs and by k-th outputs (or witnesses) coincide up to a single adaptive oracle query: FP^#P equals FP^C[1] for every C among the multiplicity median class MedP, the set median class MidP, the witness median class MedP, and the corresponding k-th output classes KthWitness(FP), KthWitness(FP^#P), KthOutput(FP), KthOutput(FP^#P)
-
The central discovery is that the function classes defined by median outputs and by k-th outputs (or witnesses) coincide up to a single adaptive oracle query: FP^#P equals FP^C[1] for every C among the multiplicity median class MedP, the set median class MidP, the witness median class MedP, and the corresponding k-th output classes KthWitness(FP), KthWitness(FP^#P), KthOutput(FP), KthOutput(FP^#P)
-
An annulment structure numbers distinctions with a semidecidable manifestation predicate; an adjudicator annuls, exempts, or stays silent on each. The core result is a trichotomy: a fixed computable map d produces, for every index a, a distinction δ_a that manifests exactly when a annuls it, so every adjudicator fails exactly one of totality, exhaustiveness, or soundness at that point. Adding one
-
The central claim is Theorem 1: for any instance of MIQP whose objective is bounded below on the feasible region and any rational epsilon in (0,1], there is a Turing-machine algorithm that either proves infeasibility or finds an epsilon-approximate solution in time polynomial in the instance size, size(epsilon), and 1/epsilon, provided p and k_- are fixed. The paper also proves that, unless P=NP,
-
The paper establishes Theorem 1.1: Ashg-Strong-Popularity is PCW-complete. The membership direction is argued by encoding each agent's additive utility as a Boolean circuit, reducing the problem to Ckt-Condorcet. The hardness direction constructs an ASHG from an arbitrary Ckt-Condorcet instance, using assignment, gate, and And-gadgets with one-way replicas that serve as weight multipliers, so that
-
The central claim is Theorem 4: for any circuit architecture satisfying the standard average-case #P-hardness conjecture for ideal RCS, no polynomial-time classical sampler can approximately simulate noisy RCS within inverse-polynomial total variation distance at local depolarizing noise strength γ* = O(log n/(nd)), unless the polynomial hierarchy collapses to a finite level. The hardness is inher
-
The paper establishes that the expander-based INW generator with spectral expansion λ = ε/(32w^3) is an ε-PRG for permutation read-once branching programs of length n and width w, with seed length O((log(1/ε) + log w)·log n). The proof works by defining, for each interval of the program, a forward weight and a backward weight that measure how much the program's layers mix test vectors. The central
-
The paper establishes that the expander-based INW generator with spectral expansion λ = ε/(32w^3) is an ε-PRG for permutation read-once branching programs of length n and width w, with seed length O((log(1/ε) + log w)·log n). The proof works by defining, for each interval of the program, a forward weight and a backward weight that measure how much the program's layers mix test vectors. The central
-
For every listed function, the paper constructs a verifier machine that reads the input in unary, reads a witness string once from left to right, and accepts exactly the intended set of objects (subsets, Dyck paths, domino sequences, ballot sequences, partitions, tableaux, or a compressed representation of them). The main technical novelty is the treatment of the hook-length formula: using Legendr
-
The central claim is Theorem 1: if there existed a sound and complete exact algorithm whose expected bit-running time is polynomial in network size, bit complexity, and inverse noise level for every adversarial base instance with 2^{-B} ≤ σ, then NP ⊆ BPP. Equivalently, under NP not in BPP, no such verifier exists. The result already holds for one-hidden-layer ReLU networks on the unit box, hidden
-
The central claim is that, under the assumptions that the base theory T is true and contains enough arithmetic, that (A,B) is a NIWI pair, and that a p-time sequence of tautologies Ψ is hard for the proof system P(T*), the prover Prover[A,B,Ψ] is ZK relative to T. Concretely, for every c,e ≥ 1 and all sufficiently large n, there is no T-proof of size at most n^e of the sentence asserting that no c
-
There is a language in smart-E^{prMA}/1 that requires Boolean circuits of size Ω(2^n/n). Equivalently, there is an infinitely-often smart FP^{prMA}/1 algorithm that, given any polynomial-size circuit C:{0,1}^n → {0,1}^{n+1}, outputs a string outside the range of C.
-
When the number of allowed offers is known in advance, any set of buyer-price pairs should be executed in decreasing-price order; under that canonical order the expected-revenue objective becomes monotone and submodular subject to a partition matroid, so continuous greedy plus pipage rounding yields a (1-1/e)-approximation that is optimal unless P=NP. Parallel constant-factor and logarithmic-facto
-
Any admissible generator-verifier pair for a non-trivial semantic property of programs induces a total Turing-computable decider for that property; Rice's theorem therefore rules out every such pair. Applied to the two semantic properties that would constitute a formal settlement of P versus NP (or of cryptographic hardness), this yields the Double Bind: no admissible method settles either directi
-
Any admissible generator-verifier pair for a non-trivial semantic property of programs induces a total Turing-computable decider for that property; Rice's theorem therefore rules out every such pair. Applied to the two semantic properties that would constitute a formal settlement of P versus NP (or of cryptographic hardness), this yields the Double Bind: no admissible method settles either directi
-
The paper's central claim is a proposed exact converse to a known proof-complexity mechanism. It is known that if a weak base theory EA proves Con_S→Con_{S+φ}, then S has polynomial-size proofs of Con_{S+φ}(n), i.e., S simulates S+φ. The paper's Higher Relative Consistency (HRC) / Feasible Reflection principle asserts the converse: no polynomial-size proof family for a true extension exists withou
-
The paper's central claim is a proposed exact converse to a known proof-complexity mechanism. It is known that if a weak base theory EA proves Con_S→Con_{S+φ}, then S has polynomial-size proofs of Con_{S+φ}(n), i.e., S simulates S+φ. The paper's Higher Relative Consistency (HRC) / Feasible Reflection principle asserts the converse: no polynomial-size proof family for a true extension exists withou
-
The central claim is that simulation between arithmetic theories is governed by relative consistency as provable in the weak base theory Elementary Arithmetic. For sound finitely axiomatized sequential S, the paper proves unconditionally that EA⊢Con_S→Con_{S+φ} implies S n^{O(1)}-proves Con_{S+φ}(n), via the standard interpretability criterion for finitely axiomatized sequential theories and polyn
-
The central claim is that simulation between arithmetic theories is governed by relative consistency as provable in the weak base theory Elementary Arithmetic. For sound finitely axiomatized sequential S, the paper proves unconditionally that EA⊢Con_S→Con_{S+φ} implies S n^{O(1)}-proves Con_{S+φ}(n), via the standard interpretability criterion for finitely axiomatized sequential theories and polyn
-
The central discovery is a complexity cliff: directed acyclicity does not help. For p=1/2, DIFR is NP-complete on directed grids; for every rational p∈(0,1), p-DIFR is NP-complete and W[2]-hard parameterized by k on bipartite DAGs. Hence neither a polynomial algorithm on DAGs (unless P=NP) nor an FPT algorithm by k or by combined solution size plus distance-from-acyclicity parameters (unless FPT=W
-
On its own terms, the paper establishes that the semantically defined logics CK* and WK* — which interpret □* via the reflexive-transitive closure of the composed relation (≼;R) and ♢* as a constructive 'eventually' — are EXPTIME-complete and have the exponential-size model property. The upper bound follows from a validity-preserving translation τ into classical PDL, where □* becomes [(i*;m)*] and
-
The fractional-logarithmic Laplacian and its inhomogeneous counterpart generate logarithmic Bessel potentials whose associated function spaces embed compactly into L^{p*} (p* = np/(n-2sp)) whenever n > 2sp, recovering compactness at the borderline Lebesgue exponent—a phenomenon that does not hold for classical Sobolev or Bessel spaces.
-
The central claim is that NESTEDCOLLISION separates the adaptive and non-adaptive black-box closures of PWPP. NESTEDCOLLISION is defined by two shrinking functions f and g, with solutions being a collision (x,y) in f followed by a collision (u,v) in the restricted function g(x,y,·). Because the second collision depends on the first, the problem can be solved by two sequential adaptive queries to a
-
The central claim is Theorem 1.1: LOP is not in StrongAvoid^dt, meaning there is no polylog-complexity decision-tree reduction from the Linear Ordering Principle to Strong Avoid. The technical engine is Theorem 4.1: a degree n/300 Σ2-pseudo-expectation exists for the LOP axioms. By Lemma 3.4, such a pseudo-expectation precludes any degree-n/300 Σ2-unary-Sherali-Adams refutation; by the characteriz
-
On its own terms, the paper's discovery is that the feasible-graph machinery from the earlier framework can be turned into a closed, executable algorithm: the author defines explicit deterministic verifier machines for SAT (an input-dependent variant and a fixed-state variant) and Subset-Sum, gives improved definitions of cover/ex-cover edges and a queue-driven 'step-pendant' edge-removal procedur
-
The core discovery is a reduction: uniform effective interpolation of G*_1 forces the same property on every normal proof system. The mechanism is the .3-property, a modal splitting principle that lets one prove, for any two formulas, a disjunction of the two implications between their provability statements, with a polynomial-time witness when interpolation is assumed. The paper shows .3 transfer
-
The paper establishes exact complexity classifications for computing Strahler numbers. The central claim is that the decision problem St≥^term — given a binary tree as a term and a threshold k, is the Strahler number at least k? — is complete for uniform NC^1. The upper bound works by first balancing the input tree into a tree straight-line program of logarithmic depth using a known uTC^0-computab
-
The central claim is that the two optimal prover strategies for QSZK's complete problems—the Holevo–Helstrom measurement (GapQSD) and the Uhlmann transform (GapF²Est)—can be approximated to additive error 2^{-n} using only O(n) quantum space and 2^{O(n)} time. The approximations are built from space-efficient QSVT: a degree-2^{O(n)} sign-function polynomial whose coefficients are computable in O(n
-
The paper's central claim is that the bounded-depth monotone formula complexity of the colored isomorphism polynomial ColIso_H is governed exactly by a new graph parameter, λ_Δ(H). A baggy elimination tree for H is a rooted tree in which each node carries a bag of vertices of H and every edge of H has its two endpoints in the same bag or in ancestor-descendant bags; the product depth is the maximu
-
The central claim is Theorem 1.2: if u is a non-negative, non-trivial local weak solution to Delta_p u + u^{p^*-1}=0 in R^n with 1<p<n and u is bounded, then u equals one of the explicit p-bubbles of the form (1.2). The same rigidity holds if u belongs to L^q(R^n) for some q at or above the Sobolev exponent p^*=np/(n-p) (Theorem 1.3), and also under a moderate polynomial growth condition with a di
-
The paper's core discovery is that the semantic class UΣ2P, despite being unlikely to have complete problems, contains three robustly identifiable syntactic layers, and all three are strictly easier than the enclosing class. PTW is defined by reductions to the problem of finding a source in an exponentially large weak tournament whose edge relation is a Boolean circuit; PCW is defined by reduction
-
The central claim is that the linear preprocessing bound in the definition of CstPP is not a delicate parameter. Theorems 5 and 6 show the class is unchanged when preprocessing is relaxed to N^c for any fixed c>1 or tightened to N^epsilon for any epsilon>0, as long as the primitive operations include +, div, and mod. By contrast, Theorem 8 shows that reducing preprocessing to N^{o(1)} collapses th
-
The central claim is Theorem 21: for both para-AC⁰ and para-AC⁰↑, the classes of parameterized problems decided by linear-BD-uniform, logtime-D-uniform, and FO-D-uniform circuit families coincide. In other words, the three parameterized uniformity conditions — defined here for the first time in a unified way — are interchangeable at the level of complexity classes for shallow families. The paper a
Stated claims
-
The paper establishes that the Steady State Capacity Augmentation for Nash Flows over Time (SSCA) is weakly NP-hard on series-parallel networks but admits an exact pseudopolynomial algorithm (running in O(|E|·(u0·B)^2)) and an FPTAS that for any ε>0 returns a capacity allocation achieving the optimal steady-state travel time while using at most B + ε·max{B, u0} budget. On general networks (even DAGs), the problem is strongly NP-hard and, for any fixed ε∈(0,1), no polynomial-time algorithm can achieve the optimal travel time while exceeding the budget by a factor of $n^{{1-ε}}$ unless P=NP. These algorithmic boundaries are derived from a geometric characterization: the steady-state travel time ∆(ν) remains constant within each cell of a hyperplane arrangement defined by signed capacity balances across s-t-cuts; on series-parallel networks, ∆(ν) equals the length of the longest free-flow path in the support of a feasible static flow of value u0, and is monotone nonincreasing in capacities.
-
The central discovery is that binary direct token-count minimization cannot be efficiently approximated within any subpolynomial factor ($M^{{1-ε}}$) unless P=NP, even on restricted instances. This is paired with a deterministic algorithm that achieves an O(M/log M) approximation, showing that the problem is not entirely inapproximable. For compression savings, the authors give an EPTAS for fixed alphabets. They also resolve two open problems: unary bottom-up tokenization is APX-hard, and unary optimal pair encoding is strongly NP-complete.
-
The author proves two complementary spectral results for the model D(n,p,p'). Theorem 1 shows that under the mild condition n(p(1-p) + $3p^{2}$ p'(1-p')) → ∞, the empirical spectral distribution of the matrix H_n/s_n (where s_n = sqrt{nν}) converges weakly in probability to the semicircle law. This holds both for the centered matrix W_n and for the uncentered matrix H_n, as well as for the expected empirical measure. Theorem 2 gives the exact spectrum of the mean matrix M_n = E[H_n] via a cotangent formula (Lemma 1), and then shows that for sequences where np_n/log n → ∞ and p'_n tends to a limit r ≠ 1/2, the k-th largest eigenvalue λ_k(H_n) satisfies λ_k(H_n)/(np_n) → c^* / (θ^* + (k-1)π), with corresponding limits for the smallest eigenvalues. When r = 1/2, only λ_1/(np_n) → 1/2 and all other eigenvalues are o_P(np_n). Thus biased orientations create infinitely many eigenvalues on the scale np_n, while unbiased ones produce only one.
-
The main theorem (Theorem 3.4) states that if $r(n) \geq n$ is time-constructible, nondecreasing, unbounded, and satisfies $\log r(n+1) = (1+o(1)) \log r(n)$, then for every $\varepsilon > 0$, $\mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon})$. The proof combines the known two-way simulations between CoT transformers and Turing machines, $\mathrm{TIME}(r(n)) \subseteq \mathrm{CoT}(r(n)) \subseteq \widetilde{\mathrm{TIME}}(r(n)^2 + n^2)$, with the classical time hierarchy theorem to get a coarse separation $\mathrm{CoT}(t(n)) \subsetneq \mathrm{CoT}(t(n)^9)$. The heart of the paper is Lemma 3.1, a padding refinement: if the classes ever collapsed at a polynomial gap, $\mathrm{CoT}(r(n)) = \mathrm{CoT}(r(n)^{1+\varepsilon})$, then the padding construction forces $\mathrm{CoT}(r(n)^{1+\varepsilon}) = \mathrm{CoT}(r(n)^{1+2\varepsilon})$, and iterating propagates the collapse up to $\mathrm{CoT}(r(n)) = \mathrm{CoT}(r(n)^9)$, contradicting the coarse hierarchy. The technical content is implementing padding inside the log-precision, saturated-attention transformer model: a transformer $T'$ that simulates the original machine on a padded input while ignoring and verifying the padding tokens, and a transformer $R$ that emits the padding as its first chain-of-thought steps and then runs the assumed machine on the reconstructed padded input. If these constructions hold, increasing the CoT budget by any polynomial factor is provably a strict gain in computational power.
-
Theorem 5.9 states that mCSAT is mNP-complete under posFP many-to-one reductions, and Theorem 5.13 states the same for the Hamiltonian Cycle Problem. Theorem 5.5 states that if every monotone NP-complete problem A admits a positive encoding Ξ with Ξ(A) mNP-complete under posFP reductions, then P ≠ NP. If correct, the paper establishes a completeness theory for mNP under a reduction notion stronger than the monotone projection translations used previously, plus a new sufficient condition for P ≠ NP.
-
On the paper's own terms, the discovery is that the geometry of all time-bounded descriptions of a string, not just its shortest one, is machine-dependent in a way that is now fully quantified. The fragmentation half (Theorems 4.1, 4.9, 4.10 and Corollary 4.11) fixes a source machine whose mandatory descriptions an adjunction-universal machine $V$ is forced to run, and counts the programs needed to join them: at length $m+O_V(1)$, all but an $O_V(1/m)$ fraction of $m$-bit targets have disconnected fibers, and at the exact length $2m+3$, all but an $O_V(\log(m+1)/m)$ fraction have at least $2^{m-O_V(1)}$ components, at every deadline beyond one polynomial that depends only on $V$. The connectivity half (Theorem 5.2) builds one machine satisfying the three reference conditions — onto, simulation by adjunction, and interpretation — for which every target $x$ has a computable threshold $N_x \le 2^{|x|+2}+1$ such that every fiber of $x$ is empty or connected at every deadline above that threshold, with diameter at most $2N+4$; above the threshold every admitted program sits within three bit flips of a connected set of fastest programs. The two halves meet in Theorem 5.5: for every machine whose fibers eventually become empty or connected, more than three quarters of the $m$-bit targets need a threshold at least $2^{c_V m - 2}$, so the exponential threshold of the construction is not an artifact. The hardness results (Theorem 5.4, Corollaries 5.7 and 5.8) then give a full connectivity language that is PSPACE-complete while every fixed-target restriction lies in P, with a uniform $2^{2^{O(k)}}\ell^{O(1)}$ algorithm and no $2^{O(k)}\ell^{O(1)}$ algorithm unless P equals PSPACE.
-
On the same pixels one can ask for the number of spanning trees (a Laplacian determinant, in GapL) or the number of simple paths from corner to corner ($\#P$-complete), and three such twin families are built: binary images asking for the Euler characteristic versus component count, grid drawings asking for determinants versus $\#P$ counts, and Eulerian drawings with arrowheads on or off. Over 15 configurations of nine models, most Gemini models transcribe small drawings exactly (85% of scored calls, mean edge F1 0.994) and then fail at the arithmetic: for the primary model the odds of an exact answer fall 2.38-fold per decade of the true answer, while at equal answer size the $\#P$ member is harder only by about one decade of $m_{50}$ ($10^{3.8}$ for GapL against $10^{2.9}$ for $\#P$), a term that disappears if either spanning trees or simple paths is dropped from the regression. The conclusion is a two-regime answer to the title question: in chain of thought, accuracy is set mainly by answer magnitude, not by the question's complexity class, and naming the relevant theorem does not help; given code and an exact transcription, counting is solved even on $10\times 10$ grids, and reading large drawings becomes the failure, with single views missing 2.8% of horizontal edges against 0.8% of vertical ones.
-
The central claim is Theorem 1: Problem Cyclic-IP-Feasibility is NP-complete even when $(p_i,q_i)\in\{(2,3),(3,2)\}$ for every $i$ and $b_i\in\{-1,0,1,2\}$. In the language of matrix sparsity, this means integer linear feasibility is strongly NP-complete when the constraint matrix has exactly two nonzero entries per row and column, its support is a single cycle, every inequality is monotone, and no variable bounds are supplied. The theorem also has two direct consequences: it answers the open column-sparsity feasibility question, and it rules out polynomial time for bounded-coefficient, bounded totally $\Delta$-modular-treewidth integer programs and fixed-parameter tractability for integer bound propagation in the coefficient bound, unless $P=NP$.
-
Theorem 1.1 states the central result: there exists a classical oracle $O$ such that $\mathsf{StoqMA}^O \neq \mathsf{MA}^O$. The separating language is GPE, defined on graphs with $2^m$ vertices of maximum degree $d \le 2n$, with the promise $\lambda_{\max} \ge n$ (YES) or $\lambda_{\max} \le 4\sqrt{n}$ (NO). The YES instance $G_n$ is built by decorating an $n$-regular base graph of girth at least $100\,n^{5/2}\log n$ (Lemma 3.5) with copies of self-similar trees, then diluting with exponentially many isolated vertices so that classical algorithms must physically walk to see anything; since $G_n$ contains the regular base graph, $\lambda_{\max}(G_n) \ge n$. The NO instance $F_n(U)$, for a seed set $U$ of at most $2^{\sqrt{n}}$ vertices, is obtained by closing $U$ under short paths in the base graph and keeping only what lies within a large base distance of that closure; the result is 2-degenerate (Lemma 3.11), and the spectral-norm bound for degenerate graphs (Lemma 2.4) gives $\lambda_{\max}(F_n(U)) \le 4\sqrt{n}$. On the quantum side a block-encoding identity makes the Hadamard test accept a witness $|\psi\rangle$ with probability $1/2 + \langle\psi|A_{G,\pi}|\psi\rangle/(2d)$, so a stoquastic verifier certifies the YES case with the top eigenvector as witness and rejects every witness on the NO case (Proposition 3.4). The classical lower bound shows that no polynomial-query algorithm, even when given the witness, can distinguish the two families: a presampling lemma (Lemma 5.1) converts any witness into revealed labels of at most $2^{\sqrt{n}}$ vertices, after which the algorithm can only explore locally and must reach a boundary leaf to see a difference, an event whose probability is bounded by Lemma 4.3, quoted from the authors' preceding paper [HBS26] rather than proved here. A diagonalization argument (as in [Zha25]) lifts the query separation to the relativized class separation.
-
On the paper's own terms, the central discovery is Theorem 1: with no derandomization hypothesis, at least one of $\mathrm{NE}\not\subseteq \mathrm{SIZE}[2^n/(2n)]$ and $\mathrm{VP}^0_{\mathbb{Z}} \ne \mathrm{VNP}^0_{\mathbb{Z}}$ holds. The proof argues by assuming $\mathrm{VP}^0_{\mathbb{Z}} = \mathrm{VNP}^0_{\mathbb{Z}}$, which yields small constant-free circuits of polynomial formal degree for the partition polynomials $Z_{T_N}$; these polynomials encode 3-CNF satisfiability and are downward self-reducible, so the equality assumption combined with the new set-multilinear PIT algorithm (Theorem 5) yields a nondeterministic algorithm that decides unsatisfiability of Boolean circuits of size $2^{\rho n}$ in time $O(2^{(1-\rho)n})$. Through the algorithms-to-lower-bounds method [Wil13, MW18, Che25], such a satisfiability algorithm certifies truth tables of high circuit complexity at infinitely many input lengths, which forces $\mathrm{NE}\not\subseteq \mathrm{SIZE}[2^n/(2n)]$. The over-the-integers identity tests are what make the win–win unconditional: they run in deterministic time $m^{d-\lceil d/6\rceil}\cdot(dsL\log(2m))^{O(1)}$ on syntactically set-multilinear circuits, and every circuit produced along the way has coefficients short enough for the test to handle.
-
The paper proves that under the assumption that E is hard for exponential-size nondeterministic circuits, one can construct seedless extractors for samplable distributions with min-entropy as low as k = O(log n) (one bit, constant error), k = n^α (multiplicative extractor outputting k^Ω(1) bits with polynomially small error), and k = polylog(n) (additive extractor outputting almost all entropy with polynomially small error, under Σ₂ hardness). These results dramatically lower the min-entropy threshold compared to prior work such as [TV00], [BSS25], [Sha25a], while using weaker hardness assumptions. The constructions also work for distributions samplable with nondeterministic postselection, a generalization that captures leakage scenarios.
-
The paper shows that the 'Target PageRank' problem—determining whether exactly B edge additions can achieve a prescribed absolute PageRank vector on a target node set—is NP-complete. The proof uses a reduction from a generalized balanced partition problem via a gadget graph whose center nodes encode the target scores, exploiting linear relations between center PageRank and the total group mass from item nodes. For the ℓ1-minimization variant, the paper proves that no polynomial-time algorithm can achieve any finite multiplicative approximation factor unless P = NP, using a gap reduction that detects zero-error solutions. This strong inapproximability holds for all ℓ_k norms. Motivated by this hardness, the authors propose heuristics: simple exposure-bias matching (G1), greedy score-based selection (G2), and a random-walk Hungarian method (RWH) that incorporates node similarity. Experiments on Amazon product-review networks show that all heuristics reduce ℓ1 error, with RWH offering the best trade-off between error and edge relevance.
-
The central discovery, on the paper's own terms, is Theorem 4.8: for $3 \le w < k$, any width-$w$ monotone algebraic branching program computing a polynomial $f$ with $\operatorname{supp}(f) = \operatorname{supp}(\mathrm{imm}_{k,n})$ requires depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{1/(w-2)}\right\rfloor - 1}$. Since $\mathrm{imm}_{k,n}$ itself is computable in width $k$ and depth $n$, the bound yields the strict inclusion $\mathrm{mVBP}_w \subsetneq \mathrm{mVBP}_k$ for every $1 \le w < k$, hence an infinite constant-width hierarchy together with separations of classes whose widths grow slowly with $n$. The same machinery sharpens the position of monotone formulas relative to the hierarchy: $\mathrm{mVBP}_{O(1)} \subsetneq \mathrm{mVF} \subsetneq \mathrm{mVBP}_{O(\log n)}$, with $\mathrm{mVF}$ incomparable to $\mathrm{mVBP}_{k(n)}$ for $k(n) \in o(\log n/(\log \log n)^2)$. A second contribution generalizes the classical leaf-counting framework for monotone formulas to bounded multiplication depth $d^{\times}$, giving the tight leaf bounds $n \cdot k^{d^{\times}(n^{1/d^{\times}}-1)}$ for $\mathrm{imm}_{k,n}$ and $\left((e+o(1)) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.
-
The paper establishes two main theorems: (1) Computing a quasi-strict Nash equilibrium of a bimatrix game is PPAD-complete, and (2) For every fixed n ≥ 3, deciding whether an n-player strategic-form game with rational payoffs admits a quasi-strict Nash equilibrium is ∃R-complete, even for zero-sum games. The PPAD membership proof follows from a new existence argument that constructs a continuous piecewise-linear self-map on the product of strategy simplices using simplicial complexes derived from best-response regions and the barycentric subdivisions of the strategy simplices, together with the Euclidean projection. A polynomial-time oracle algorithm locates the cell containing a given point, making the map a polynomial piecewise-linear fixed-point problem in the sense of Etessami and Yannakakis, whose fixed points yield quasi-strict equilibria. The ∃R-hardness for three or more players is obtained by a reduction from the minmax-value decision problem for three-player games, leveraging known ∃R-hardness results.
-
Theorem 1 states that for any deterministic machine model and a fixed constant c covering wrapper overhead, there exists a threshold T such that no machine H_T can decide BH_T (whether a program halts within T steps) in at most T−c steps for every program-input pair. Corollary 1 sharpens this: for any fixed α < 1, no exact deterministic decider for BH_T can halt on all inputs within αT steps for sufficiently large T. Theorem 2 proves the same bound for stable nondeterministic deciders, and Corollary 2 extends it to randomized deciders that halt with probability 1. The paper also introduces three observable properties—fixed finite state set (Proposition 1), fixed deliberation bound (Proposition 2), and finite forgetting horizon (Proposition 3)—each of which alone obstructs universality. Applied to standard automata and Transformer models (Table 1), the tests show that a fixed finite-precision Transformer with fixed context fails all three tests and thus is not universal.
-
The central discovery is that the following four primitives are existentially equivalent: (1) everlasting-secure two-message quantum key exchange, (2) standard two-message quantum key exchange, (3) efficiently-verifiable state puzzles, and (4) one-time secure digital signatures with quantum signatures and quantum signing keys. The paper proves this by giving explicit constructions in both directions: from state puzzles to quantum signatures and then to everlasting-secure 2QKE, and from any 2QKE to state puzzles. The equivalence implies that 2QKE requires exactly the same assumptions as these other primitives, and because state puzzles can exist even if P=NP relative to an oracle, the result shows that 2QKE may be strictly weaker than one-way functions. Moreover, the paper shows that standard 2QKE implies everlasting-secure 2QKE, meaning everlasting security comes for free, and that one-shot signatures imply quantum public-key encryption with quantum public keys, providing a construction from assumptions incomparable to one-way functions.
-
The paper's core discovery is that the CNF encoding complexity of a Boolean function is governed by the product √(mb) rather than by m alone, when the function is computed by a nondeterministic RAM that reads at most b advice bits per input. This is captured by Theorem 2: enc(f) = Õ(t + √(mb)). The proof introduces a mass-production lemma (Lemma 11) that encodes b queries to an arbitrary function g with Õ(√(b·2^k)) clauses—far fewer than the b·2^k clauses that a naive scheme would require. This lemma relies on Teutsch's explicit expander to hash the b queries into slots, creating sparsity that is exploited by a separate sparse-function encoding (Lemma 13). The paper also sharpens the bound for sparsely supported functions (Theorem 6): enc(n,M) = Θ(n + √(M(n − lg M))), and it characterizes encoding complexity exactly as the minimum number of ∧-gate wires in a nondeterministic De Morgan circuit (Proposition 44).
-
The paper's central claim is that two quantum-advantage primitives are compatible, in relativized worlds, with the collapse of the nondeterministic classes they are widely believed to separate. Theorem 1.3 exhibits a classical oracle $O$ with $P^O = NP^O$ and $BQP^O = PSPACE^O$, together with a language in $IP^O \subseteq BQP^O$ that is hard on average against $P^O/poly$; from that language the authors derive a polynomial-round public-coin proof of quantumness and a two-message quantumly-verifiable proof of quantumness, while also proving that constant-round proofs of quantumness do not exist relative to the same oracle. Theorem 1.8 exhibits a unitary oracle $U$ with $BQP^U = QCMA^U$ relative to which a four-message quantum-verifier oblivious state preparation protocol, built from a claw-state generator, exists. The authors present both results as oracle evidence that the conjectures 'proofs of quantumness imply $BPP \neq NP$' and 'qv-OSP implies $BQP \neq QCMA$' fail relativized, and that no relativizing construction derives classical or quantum cryptography (one-way functions, commitments, efficiently verifiable one-way puzzles, oblivious transfer, and related objects) from these primitives.
-
The paper's central claim is Theorem 4.9: there exists a polylogtime-uniform family of constant-depth threshold circuits, indexed by the number of variables and the degrees of the input forms, which takes dense forms $F_1,\dots,F_m \in \mathbb{Q}[x_0,\dots,x_n]$ together with a string of random integers, and with high probability outputs integer multiples of the Chow forms of all equidimensional components of $V(F_1,\dots,F_m)$. The Chow form of a $k$-dimensional component is the single polynomial in auxiliary linear-form coefficients whose vanishing records exactly which $(k+1)$-tuples of hyperplanes meet that component, so the circuit family is a complete encoding of the decomposition. Since the family is polylogtime-uniform and constant-depth, the simulation lemmas convert it into CH membership for the associated languages, and the paper derives from it the announced results: CH decision procedures for Chow-form zeros and monomial support, for membership in a given equidimensional component, and for membership in the closure of the image of an irreducible variety under a polynomial map; $\mathrm{FP}^{\mathrm{CH}}$ computation of component degrees; and CH decision of approximate polynomial satisfiability over the larger field families. The proof has two stages: first, a deformation of the defining equations, read off from the trailing term of a perturbed resultant, produces for each $k$ an equidimensional over-variety $W_k \subseteq V$ containing the $k$-dimensional component; then, because any excess component must lie in a higher-dimensional component, a parallel pruning step using geometric resolutions and GCD computations removes them, and factor-lifting recovers the exact Chow form.
-
The central claim is Theorem 1.1: for one fixed, explicitly computed public family—labels are coordinatewise-rounded linear measurements summed modulo a prime $q$—any uniform quantum polynomial-time distinguisher that tells real from ideal LAR apart on polynomially many classical random examples with nonnegligible advantage yields uniform quantum polynomial-time algorithms for worst-case GapSVP and SIVP at approximation factor $\widetilde{O}(q)$. The reduction runs through Gaussian LWE; the worst-case lattice step is quantum, and the subsequent sample transformations are classical. Because the transport accuracy is chosen only after fixing the adversary's sample budget, the same family is hard for every polynomial number of samples, which is precisely the feature that standard polynomial-modulus learning-with-rounding reductions lack. From this the paper derives the first post-quantum weak PRF with joint key-and-input evaluation in $TC^0$ and hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, against quantum polynomial-time improper learners.
-
The paper establishes a complete complexity map for synthesis from a parameter multiset, with one row for each way a target can be supplied. With two labeled examples, exact feasibility is $\mathsf{NP}$-complete at cap one with positive integer inventory (Theorem 3.3). Exact agreement with a Boolean circuit on every Boolean input is $\Sigma_2^{\mathsf P}$-complete with four computational neurons, even when the target is a monotone threshold with positive coefficients (Theorem 4.12). Exact agreement with a supplied rational ReLU network on all real inputs lies in $\mathsf{DP}$ for every fixed cap and is $\mathsf{DP}$-complete at cap three, with cap two $\mathsf{coNP}$-complete under at-most-once use (Theorems 5.3, 5.4, 5.9). Uniform approximation within absolute error one on the unit box is $\Sigma_2^{\mathsf P}$-complete with one affine neuron and an inventory of identical positive rational values (Theorem 6.2). Deciding whether some network has expected squared loss at most a threshold is $\mathsf{NP}^{\mathsf{PP}}$-complete for uniform Boolean inputs (Theorem 7.1) and, under a binary-encoded accuracy gap that may be exponentially small, for continuous uniform and standard Gaussian inputs at cap two (Theorems 8.6 and 9.5). The organizing claim is that the numbers are not the bottleneck: each target is easy to realize when real weights may be chosen freely, and the hardness is created by the requirement to rule out every alternative legal placement of the same occurrences.
-
The central claim, Theorem 1.1, is that the circuit complexity $c(L)$ of every regular language $L \subseteq \Sigma^+$ — the asymptotic minimum number of non-input gates in an unbounded-fan-in AND/OR circuit family over subset-encoded inputs — satisfies exactly one of $c(L) \in O(1)$, $c(L) \in \Omega(\log n) \cap O(\log n \log\log n)$, or $c(L) \in \Omega(n) \cap O(n)$, with $\Omega$ the Hardy–Littlewood 'infinitely often' notion. The classification is driven by Theorem 1.3, a sublinear characterization with ten equivalent faces: $L \in \mathrm{SizeDepth}(O(\log^2 n), O(1))$; $L \in \mathrm{SizeDepth}(O(\log n \log\log n), O((\log\log n)^2))$; $L \in \mathrm{Size}(o(n))$; the syntactic morphism $\eta_L$ belongs to the new lm-pseudovariety $X$; $L$ is a union of $\simeq_k$-classes for some $k$; $L$ is a Boolean combination of finite languages and languages $uKv$ with $K$ a modular disjoint monomial or a modular threshold language; and $L$ is definable in $\mathcal{L}^1[\mathcal{B}[<,+^\omega],\Sigma,<,+^\omega,\bmod,\min,\max]$. The nontrivial lower-bound direction is proved contrapositively in Section 4: a violation of the identities that define $X$ produces words $u, v, w$ and an index $i$ such that the syntactic morphism separates $uv[i \leftarrow u_i]w$ from $uv[i \leftarrow w_i]w$, and from this single witness the authors build, for each input length $n$, a chain of $n-1$ word pairs of length $k(n+1)$ that any correct circuit must separate; since the pairs differ in one position each, any non-input gate can separate at most one pair that its non-input predecessors failed to separate, so $\Omega(n)$ gates are required. The upper bounds run through the logic-to-circuits translation, which reduces everything to computing the binary positions of a constant number of distinguished letters, realized by an $O(\log^2 n)$-size constant-depth circuit (via subpartition threshold schemes) and by an $O(\log n \log\log n)$-size, $O((\log\log n)^2)$-depth circuit (via error-correcting encoders with block recursion).
-
The central claim is an equivalence theorem: SH — the conjecture that CNF SAT has no $O(2^{L^{1-\varepsilon}})$-time algorithm on inputs of length $L$, for any constant $\varepsilon>0$ — is equivalent to Weak ETH, the assertion that 3SAT has no $O(2^{n^{1-\varepsilon}})(n+m)^{O(1)}$-time algorithm, for any constant $\varepsilon>0$. The same proof shows #SH is equivalent to Weak #ETH. The argument proceeds through two reformulations: a parsimonious Tseitin encoding (Lemma 2.1) equates input length with formula size $n+m$ at fixed clause width, and quantitative and disjoint sparsification with a variable-dependent parameter $\eta = n^{-\delta}$ (Lemma 2.2, Corollary 2.3) equates the size formulation with the variable-count formulation. On top of these, Theorem 3.1 transfers exponents through reductions: if 3SAT of size $s=n+m$ maps in $2^{O(s^\alpha)}$ time to instances with parameter $N \le s^{b+o(1)}$, then SH rules out $2^{O(N^{1/b-\varepsilon})}L^{O(1)}$-time algorithms for the target problem, for every $\varepsilon>0$. The paper derives concrete consequences: Max-3SAT gap hardness and approximation lower bounds under SH (Corollary 4.1), the exclusion of $2^{O((n+m)^{1-\varepsilon})}$-time algorithms for #2SAT even with constant degree under #SH (Corollary 5.1), and bounded-error randomized analogues of all of these (Theorem 6.1).
-
Stated the way the authors would state it: exact counting, not diagonalization, is what makes these extended-gate circuits provably weak. The proof runs through a transfer theorem (Theorem 6) that takes any deterministic exact-counting test of the form $\operatorname{poly}(n)\,2^{R + AU/a(U)}$, with $R$ a branch-count exponent and $a$ a slowly growing speedup function, and converts it into an infinitary $\Omega(m\,a(m))$ gate lower bound for a language in $\mathsf{E}^{\mathsf{NP}}$. Two counting interfaces instantiate the transfer. Interface I (Lemma 7) shows that the output-one preimages of a circuit over unbounded AND/OR and binary XOR form the difference of two ordinary 3-CNF model counts on at most $n+3g$ variables, with signed long-clause selectors and one parity chain handling every wide AND/OR gate; plugging in the exact-counting bound quoted from [2] gives Theorem 1. Interface II (Theorem 8) eliminates arbitrary-fan-in XOR gates by an exact affine-character expansion costing $2^r$ branches for a rank-$r$ subsystem, and eliminates each symmetric gate of arity $d_j$ by unit-separated interpolation into $d_j+1$ unary-weight factors costing $\log_2(d_j+1)$; the branch weights live in an extension ring of $\mathbb{Z}/2^p\mathbb{Z}$, and the contraction theorem adapted from [5] evaluates all branches within the stated time bound, which yields Theorem 2's $\Omega(m\sqrt{\log m})$ bound under a linear exceptional-gate budget.
-
For a CNF formula $F$ with $Z_F$ satisfying assignments, the paper defines a point distribution on the hypercube: one atom per satisfying assignment plus one auxiliary atom that keeps the mixture a probability measure when $Z_F = 0$, smoothed by unit Gaussian noise in dimension $n+1$. Because every atom has the same squared norm, all likelihoods coincide at the origin, where the posterior equals the prior; the Gaussian score identity $s_F(y) = E[A \mid Y = y] - y$ then yields the exact formula $h(F) = (2Z_F - 1)/(2Z_F + 1)$ for the first score coordinate — a value of $-1$ for unsatisfiable formulas and at least $1/3$ for satisfiable ones. A deterministic polynomial-time algorithm outputting this coordinate to absolute error $1/4$ exists if and only if $P = NP$: the error budget cleanly separates the two cases by the sign of the output, and conversely a SAT decider supplies the value by bounded witness enumeration with blocking clauses (Theorem 4.2). Compressing the atoms by rational factors into a ball of squared radius at most $1/2$ preserves the gap while forcing the negative log density to be $\frac{1}{2}$-strongly convex and $1$-smooth, with the same constant-accuracy equivalence and with the SAT signal persisting throughout a query ball of radius $1/24$ independent of dimension (Theorem 6.1 and Corollary 6.2). The paper anchors the equivalence in the formula-access model: with independent samples instead of the formula, the same value becomes a dimension-independent mean with exponential concentration, and any formula-to-sampler algorithm would collapse NP into RP. The existence of a general efficient formula-access evaluator is left open.
-
The central claim, Theorem 1.1, is that factor complexity is polynomially bounded in product complexity: from a size-s circuit for f of degree at most D, every factor g in any identity f = gh has a circuit of size O($sD^{3}$), and every central factor g in f = agb has one of size O($sD^{6}$), with the circuits constructible deterministically once a maximum-degree word of the cofactor, its coefficient, and the coefficients of all its proper suffixes are supplied. The proof defines a single linear map T that removes a specified right cofactor: built from the cofactor h, the map satisfies T(gh) = g for every left factor g. T is implemented by substituting block matrices M_x for the variables, which turns any circuit for f into a circuit for g; reversing words handles left factors, and two substitutions handle central factors. Theorem 1.2 extends the statement to formulas (O($s^{2}$) one-sided, O($s^{4}$) central), to VP^nc, and to VNP^nc, because the fixed linear map T commutes with the Boolean sum that defines VNP verifiers. The same map gives ABP closure, and over finite fields the size theorems feed algorithms that output complete irreducible factorizations as formulas, as succinct ABPs with polynomial-time edge queries, or as circuits via an $FP^{{\Sigma_2^P}}$ search or a zero-error randomized search with an NP oracle.
-
On the paper's own terms, the central claim is Theorem 1.3: APS belongs to the Counting Hierarchy, for rational polynomials given by arithmetic circuits (with division gates allowed under a denominator promise, and extending to number fields and finite fields), sharpening the earlier $\mathsf{PSPACE}$ upper bound. The reduction first cuts the input map down to a dominant map $F : \mathbb{A}^n \to \mathbb{A}^{n+1}$ and applies a finite Noether normalization $\pi : Y \to \mathbb{A}^n$ to the image closure $Y$, so that $0 \in Y$ holds exactly when $0$ lies among the finitely many points of $Y_0 = Y \cap \pi^{-1}(0)$. Each point $y_0 \in Y_0$ is then shown to be the $t \to 0$ limit of solutions of the one-parameter system (4.1) obtained by pulling back a generic line $\{t\alpha\}$ through the origin, with all $y$-coordinates integral over $\mathbb{C}[t]$ (Proposition 4.5), so the possible output limits are exactly the points of $Y_0$. A generic linear form $\ell$ separates those points, and the polynomial $Q_{Y_0,\ell}(T) = \prod_{y \in Y_0}(T - \ell(y))$ records whether $0 \in Y$ through the vanishing of its constant term. The paper computes a proxy for $Q_{Y_0,\ell}$ as $R_\ell(T) = TC_t\,TC_w\,TC_\varepsilon R$, the nested trailing coefficient of the resultant $R = \mathrm{Res}(\hat{G}_1,\ldots,\hat{G}_N,H_{T,w})$ of the homogenized, $\varepsilon$-perturbed equations with the quadratic form $H_{T,w} = Tz_0^2 - z_0\ell(y(z)) + \sum_j w_j z_j^2$, and proves (Theorem 5.3) that $R_\ell$ and $Q_{Y_0,\ell}$ have the same roots, so APS is decided by $R_\ell(0) = 0$. Because individual coefficient bits of the resultant are accessible at a fixed level of the Counting Hierarchy, the three trailing-coefficient operations and the final vanishing test cost only a fixed number of quantifier blocks over polynomial-length indices.
-
At the center is Theorem 1.1. The paper builds one fixed family $T^*$ and proves that for $n$ written in binary, the function counting translation-only tilings of the $n\times n$ square is complete for #EXP under polynomial-time metric reductions and lies in #E. The side length encodes a #EXP-complete accepting-path counting problem through an injective self-delimiting map $E_{side}$; a fixed one-head machine $M^*$ then realizes the encoded computation. In the Wang stage, which uses open tilings with unconstrained boundary colours, an open-square counter gives $a_{prod}(n)=Q^{4n-4}(1+C_U(x))+Junk(n)$ on encoded lengths, with $0\le Junk(n)<Q^{4n-4}$, so the accepting count is recovered by integer division. In the geometric stage, carriers anchored on a $P_s$-spaced grid realize each Wang tiling, and the exact sum over rectangular partitions of the macro-grid has a dominant one-block term, yielding the same floor-recovery identity for the polyomino count. Composing the two reductions proves the theorem.
-
The paper's central claim is Theorem 1: under polynomial-time Turing reductions, deciding whether a planar graph of maximum degree 3 has treedepth at most $k$ is NP-hard, so unless P = NP no polynomial-time algorithm for it exists. This answers two previously open questions — whether treedepth remains hard on planar graphs, and whether it remains hard on bounded-degree graphs — in the stronger combined form, and the degree bound is best possible because graphs of maximum degree 2 are disjoint unions of paths and cycles whose treedepth is easily decided. The proof reduces from Weighted Tree Search, a strongly NP-hard problem (quoted from the literature) in which a hidden vertex of a weighted tree must be located by paying for edge queries. Each tree vertex becomes a wall-based gadget with attached anchors, and each weighted edge becomes that many strand vertices between gadgets; a search strategy of cost at most $K$ becomes an elimination tree of height at most $B = 2K+1+A$, and the converse direction is forced by a potential-function induction showing treedepth at least $B+1$ when the search cost exceeds $K$, where $A = \mathrm{td}(W_a)$ is the treedepth of a wall. Because $A$ is not known to be computable, the reduction first recovers it from the oracle by binary search, which the paper identifies as the single obstacle to making the reduction a Karp reduction.
-
The paper proves (Theorem 4.1) that weighted directed distance admits a sublinear CLP algorithm (catalytic logspace with sublinear catalytic space and polynomial time): given an $n$-vertex directed graph with polynomially bounded integer edge weights and no negative cycle, and vertices $s,t$, the minimum weight of an $s$-$t$ walk is computed in catalytic space $O(n/2^{\Theta(\sqrt{\log n})})$ with logarithmic workspace and polynomial time. Correctness is deterministic: every seed's compressed graph $G_\sigma$ has distance at least the true distance, the hitting argument shows at least one seed's graph has distance at most it, and the algorithm returns the minimum over all seeds. The paper further claims this is the first simultaneous sublinear-space and polynomial-time bound for weighted distance even when the catalytic requirement is dropped, and that any improvement to it would improve reachability. As a byproduct, the determinant of an $n\times n$ integer matrix is computed in near-linear catalytic space $O(n\log^{O(1)} n)$ with polynomial time through the identity $\det(A) = [t^n]\exp\bigl(\sum_{k=1}^{n} (-1)^{k+1} \mathrm{tr}(A^k)/k \cdot t^k\bigr)$ combined with logspace interpolation. The same bounds transfer to the Pfaffian and to planar perfect matching: decision and search run in near-linear CLP, and for bipartite planar graphs in sublinear CLP.
-
On its own terms, the paper's central claim is twofold. First, the crossover point of the recursion of [1] — the input size from which its proved bound beats the best known algorithms for the same problem — can be made explicit and lowered by proved changes: least admissible group sizes per level, the numeric constant $c = 30$ for the equality-test pieces of [1, Theorem B], a contraction-tree base case with exponent $0.2554$, the exact edge-bit total $U = 2(km-n)$ in place of the preprint's bound $U < 2km$, and a clustering lemma for the top level that lowers the balancing exponent $q$ from $9$ toward $2$. These move the main-term threshold for #3-SAT at clause density one from about $2^{33858}$ to roughly $2^{420}$ clauses (Table 4 gives 417 in column U+C), the general-3-SAT estimate from about $2^{2.2\cdot 10^{12}}$ to about $2^{8.6\cdot 10^9}$ variables, and the Max-3-SAT spectrum crossover from about $2^{68364}$ to about $2^{1016}$ clauses — each value a lower bound on where the proved bound wins, since lower-order terms are dropped. Second, the distance is structural, not a matter of constants: the paper defines a rewrite-and-merge class containing the recursion and all its constructions, proves every grid algorithm in it has exponent at least $1/\log_2 K$ per edge bit — so through the reduction of [1] no such algorithm gains for general 3-SAT below about $2^{6000}$ variables — and proves that balanced homogeneous two-merge algorithms pay at least $(\log_2 K)^{-3}$ per edge bit, which excludes running times of the form $2^{n^{1-c}}$. Independently of SAT, it formalises the method of [1] as Signed Network Sums, a model strictly containing rank-one methods and contraction trees, and shows that at $K = 4$ nodes one-level constructions contract the complete-graph tensor network in $N^{23/6}$ operations if $\omega = 2$ and in about $N^{3.93}$ on the current (preprint) matrix-multiplication curve, below the $N^4$ floor that binds every rank-one method and every contraction tree.
-
Within the process matrix formalism the paper proves two inclusions. Theorem 1.1 states that $\mathrm{NP} \subseteq \mathrm{BQP}_{\ell\mathrm{CTC}}$, the class of polynomial-time computations that may query linear closed timelike curves, and that the inclusion survives two further restrictions: the valid queries describe purifiable processes, and the generated channels are unitary. The engine is Lemma 5.1: from a polynomial-size circuit preparing the Choi state $|J_V\rangle = 2^{-n/2}\sum_x |x\rangle \otimes V|x\rangle$ of an isometry $V$, a classical algorithm constructs a process matrix generator whose connected channel is exactly $\rho \mapsto V\rho V^\dagger$; the feedback consistency condition $r = r \oplus j$ admits only the trivial teleportation outcome $j = 0^{2n}$, and explicitly measuring the feedback registers inside the generating circuit makes the trace-preservation calculation work with no input-dependent normalization. Applying this construction to the unique witness of a Boolean circuit, and to a permutation, yields unique-witness search and coherent permutation inversion, and the randomized unique-witness reduction converts the former into $\mathrm{SAT} \in \mathrm{BQP}_{\ell\mathrm{CTC}}$. Theorem 6.2 then constructs, for a unique-sink orientation with outmap $s$, an explicit unitary generator whose generated channel is $T_s|y\rangle = |s^{-1}(y)\rangle$, so one query on $|0^n\rangle$ returns the unique sink with probability one; the paper also proves the converse direction, showing that for this concrete generator the circuit is a valid process matrix generator if and only if $s$ is the outmap of a unique-sink orientation.
-
The central claim is Theorem 5.8: for any oracle $O$ and any $\varepsilon$-robust oracle circuit $C^O$ with $n$ input bits, $m$ output bits, $S$ gates, and oracle queries of polylogarithmic length, the relation $C^O(x)=a$ admits a relativizing rewindable interactive proof with preprocessing whose soundness error is $2^{-\sigma}$, whose verifier runs online in $\widetilde{O}(\sigma(n+m+1/\varepsilon))$ time and makes $O(\sigma\min\{q_C,1/\varepsilon\})$ oracle queries, and whose honest prover runs in $O(\sigma N')+\widetilde{O}(\sigma/\varepsilon)$ field operations with $N'=S+n+m$. The argument has four steps: the prover supplies the answer to every oracle gate, turning the oracle circuit into an ordinary one; an encoded-witness IOP proves that the de-oraclized circuit outputs the claimed answer, with the witness encoded so that the verifier can later recover individual entries; $\varepsilon$-robustness guarantees that a false output forces more than an $\varepsilon$ fraction of the supplied answers to be wrong, so the verifier needs only $O(1/\varepsilon)$ random spot-checks against the oracle; and the IOP is compiled into an RIP by rewinding the prover to the moment each proof string was fixed, so that answers cannot adapt to the verifier's other queries. Sequential repetition of the rewound protocol drives the soundness error to $2^{-\sigma}$. The paper's claim, stated to a fair reader, is that this yields the first relativizing proof for robust oracle computations that assumes no truthful prover, uses no cryptography, and still achieves a linear-time prover and a succinct verifier, with the caveat it acknowledges that soundness presumes the prover has no non-rewound external storage.
-
The central claim is Theorem 1.1: for every sufficiently large $n$ and every $k$ with $\omega(1)\le k\le O(\log n)$, a random width-$k$ CNF formula on $n$ variables with $M = n2^k$ independent uniform signed clauses is, with probability $1-o(1)$, unsatisfiable but requires polynomial calculus degree strictly greater than $n/2 - 4n/\sqrt{k}$ to refute, over every field. The proof verifies two expansion conditions — every subformula with fewer than $s = n/\sqrt{k}$ clauses is satisfiable, and every subformula with between $s$ and $2s$ clauses has more than $D + |A|$ neighboring variables, where $D = n/2 - 4s$ — and converts them, through matching deficiency and clause-set closures, into a degree-$D$ pseudo-reduction operator, a certificate that no degree-$D$ refutation exists. The degree bound then transfers, through a size–degree tradeoff reproduced and extended in the appendix, to a size lower bound of $\exp(\Omega_p(\sqrt{k}\log n))$ for depth-2 $\mathsf{AC}^0[p]$-Frege refutations (Corollary 1.2). Complementing both, Theorem 1.3 shows the same formulas can be refuted in degree $n/2 - n\ln(k)/(2k) + O(n/k)$ over every field, which the author reads as evidence that random $k$-CNF formulas cannot yield higher-depth $\mathsf{AC}^0[p]$-Frege lower bounds through the same tradeoff.
-
The paper's central claim is that in $G(n,p)$ with $C/n\le p\le 1-\kappa$, the half-optimality barrier for induced matchings is realized exactly in both online and low-degree algorithmic frameworks. The achievability of greedy rests on a maximality principle: with high probability, every maximal induced matching has size at least $(1/2-\epsilon)L$, where $L=\log_{1/(1-p)}(np)$. Since greedy outputs a maximal induced matching, its guarantee follows without tracking the algorithm's dynamics. The matching impossibility result shows that any online algorithm in the adaptive-inspection model finds an induced matching of size at least $(1/2+\epsilon)L$ with probability at most $\exp(-\epsilon^2 L \log(np)/2)$. In the sparse regime $p=d/n$, a constant-degree polynomial achieves $(1/2-\epsilon)\Phi$ with high probability, where $\Phi=n\log d/d$, while no degree-$D$ polynomial satisfying a second-moment normalization and rounding condition can exceed $(1/2+\epsilon)\Phi$ unless its success probability is exponentially small in $D\log n$.
-
Stated as Theorem 1, the central claim is that for a fixed decider $M$ there are rational polynomial maps $F_M(h,z)$ and $c_M(x,h)$, a compact box, an exponent $K\ge 256$ and constants so that every execution $z_{k+1}=z_k+\eta_k F_M(h,z_k)+\eta_k\xi_k$ with $0<\eta_k\le 1$, divergent step sum and $\|\xi_k\|_\infty\le h^{2K}$ stays in the box and outputs the machine's answer within $1/4$ after physical time $O(s(T+s))$, with the data at internal cycle sections within $r_*h$ of the successive encoded configurations. The agreement between the three runs is an agreement of logical traces read at each run's own cycle sections, not of states at common physical times, and the same section guarantees hold for the continuous system with any measurable forcing of norm at most $h^{2K}$. From this realization the paper derives that polynomial physical time at unit step, equivalently at every admissible mesh, characterizes $\mathrm{P}$ (Theorem 8); that robust eventual decision with noise tolerance $h^r$, with no stabilization horizon supplied, characterizes $\mathrm{PSPACE}$ (Theorem 9); that a fixed rational polynomial field has a $\mathrm{PSPACE}$-complete robust prediction problem whose hard instances agree across all temporal interpretations (Theorem 10); and that every safe member of a robust safety family has one rational polynomial certificate for all Euler steps and the flow, where uniformly polynomial certificate length would imply $\mathrm{NP}=\mathrm{PSPACE}$ and bounded degree would imply $\mathrm{P}=\mathrm{PSPACE}$ (Theorem 20).
-
The paper's main claim is that universality, visible closure, and maximality form a triangle for spin ML models: any two imply the third. Visible closure is the ability, up to polynomial-size simulation, to turn a chosen subset of visible spins into hidden spins; it is what allows visible simulations to be composed without losing the visible-hidden split. Because DBMs of depth at least three are strictly visible closed and are known to be v-universal, Theorem 16 and Corollary 17 make them (v,p)-maximal, meaning they can efficiently simulate every target that any model can efficiently simulate. Shallow models cannot be maximal on complexity grounds: with small weights, a function efficiently simulated by a shallow k-local system is a linear combination of polynomially many degree-(k−1) polynomial threshold functions, and such functions have low communication complexity, while the k-party inner product modulo two, IP_k, has linear communication complexity. Hence shallow k-local models cannot simulate IP_k, whereas shallow (k+1)-local models can simulate IP_{k−1}; this yields the infinite hierarchy and separates RBMs from 3-body RBMs.
-
The central claim, stated on the paper's own terms, is that exact threshold comparison of expected cover times is #P-hard in a very constrained setting. Theorem 1 says that deciding $C_G(s) \le r$ is #P-hard under polynomial-time Turing reductions when $G$ is a connected simple undirected unweighted graph with a universal hub $z$, diameter two, every non-hub vertex of degree at most five, and $G - z$ planar and bipartite. Theorem 2 says the same for the maximum-start language $M(G) = \max_s C_G(s)$, where a fixed cube attachment with marker leaves makes the maximizing starts known. Theorem 3 gives the complementary upper bound that both problems belong to $\mathrm{P}^{\mathrm{NP}^{\mathrm{PP}}}$ for general graphs. Corollary 4 states that even truncating an expected cover time to its integer part plus the first $2m$ fractional bits is #P-hard on the same graph class, so the hardness extends from exact decision to exponentially fine numerical output.
-
The paper's central claim is that explainability by node labels can be a first-class constraint of correlation clustering rather than an afterthought. In ExplainCC the feasible clusterings are exactly the partitions induced by label trees, and the goal is to minimize the usual correlation-clustering disagreement count; $k$-ExplainCC further limits the tree to $k$ leaves. The paper proves that $k$-ExplainCC has no polynomial-time multiplicative approximation unless P = NP, and that ExplainCC is NP-hard to approximate within $(1-\varepsilon)\log n$ for any $\varepsilon>0$ even on unweighted graphs, while on the positive side a polynomial algorithm solves the zero-disagreement case and yields a trivial $O(n^2)$ approximation in unweighted graphs. Against this hardness the paper proposes a reference-free greedy heuristic: rather than fitting a tree to a precomputed clustering (a baseline it shows can double the mistakes even under optimal inputs), Expand builds the label tree directly, splitting whatever leaf yields the largest cost improvement. The experiments support the heuristic's practical value: on planted graphs the pruned tree recovers the ground-truth communities, and on benchmark co-authorship networks the label trees place broad topics near the root and specific ones deeper.
-
The paper's central claim is that the known modular depth lower bound for exact maximization by restricted-weight ReLU networks can be proved inside the weak arithmetic theory $\mathbf{VTC}^0$ with a refuter attached: for each separately fixed prime $q$ and hidden-depth cap $K$, there is a chosen $\mathbf{FTC}^0$ function (a uniform constant-depth threshold computation) which, on any rational network with $n > q^K$ inputs, at most $K$ hidden layers, and nonbias weights whose reduced denominators omit $q$, returns a rational $n$-vector $\mathbf{x}$ of length polynomial in the network code for which $N(\mathbf{x}) \neq \max(\mathbf{x})$, with $\mathbf{VTC}^0$ proving the guarantee. The proof makes the obstruction finite. In the fixed dimension $d = q^K$ it builds a finite cone calculus whose central operation is the cone product, an intersection product of a piecewise-linear function with a weighted polyhedral cycle that lowers dimension; iterating it $d$ times produces an integer, and the network-specific locality and rectification identities force that integer to be divisible by $q$, while the maximum family normalizes the same product to the value $1$. Denominator clearing scales the maximum by $a^d$ with $a$ coprime to $q$, so the impossible equality $qz = a^d$ is detected at finitely many rational probes per chamber, one of which must be a genuine error once biases are dominated by a scale factor. The bulk of the paper is the arithmetic internalization: every cone operation, integer quotient, and probe must be given by explicit parallel formulas, with sequential scans replaced by parallel histories and greedy basis scans executed in a fixed number of stages, so the refuter is genuinely a uniform constant-depth threshold computation. The construction side is proved in the same theory: local certificates label each maximum gadget by the input coordinates it aggregates, yielding full evaluation histories in parallel, and the certified balanced family of depth $\lceil\log_2 n\rceil$ meets the prime-two refuter exactly at the sharp threshold $n \le 2^K$, while a certified rational family achieves polynomial total length and depth $O(\log n/\log\log n)$.
-
On the paper's own terms, the contribution is Theorem 1.2 (equivalently Theorem 7.1): for every $d$, the bounded integer halfspace matrix $HS_{M,d}$ has sign rank $\Theta(d)$, while for $M\ge 2^{cd}$ its two-fold conjunction has sign rank $e^{\Omega(d)}$. This is the first explicit construction in which a cheap unbounded-error problem becomes exponentially expensive under double evaluation, ruling out closure of $\mathsf{UPP}^{\mathsf{cc}}$ under intersection. The lower bound is obtained by first solving a continuous analogue: any measurable unit-norm maps $f,g$ on $(S^{d-1})^2$ that correctly sign the AND of two inner-product tests away from the coordinate bands $|\langle x_i,y_i\rangle|\le 2^{-Cd}$ must satisfy $\mathbb{E}[|\langle f(X),g(Y)\rangle|]\le e^{-cd}$. That exponentially small average margin transfers to the discrete halfspace matrices through a rounding argument, so the average-margin theorem converts it into the sign-rank lower bound. The authors present the continuous argument as a new way to lift polynomial sign-degree obstructions to sign-rank lower bounds.
-
Relative to a classical Boolean oracle $O$, there is a total unary language $L$ with three properties at once: $L \in \mathsf{EQP}^O$ (uniform polynomial-size quantum circuits with oracle gates accept exactly the strings of $L$, with certainty), $L \notin \mathsf{PH}^O$ (no polynomial-time machine with any fixed number of alternating polynomial-length quantifiers decides it), and $L$ has a public-coin interactive proof system whose classical verifier and quantum honest prover run in polynomial time, with perfect completeness and soundness error at most $1/4$ against every prover, classical or quantum. The language is built from a recursive Fourier sampling variant: an instance is a tree of tables in which each node hides a secret $s$, a code table encodes $s$, the node's value is the entry $R_s$ of an unconstrained data table at that secret, and every table entry is itself the value of a subtree, with only the leaves stored in the oracle. The quantum algorithm decodes the secret at every node exactly, recovering each phase state by a Hadamard transform for the Hadamard code, and the verifier checks the prover's claimed secrets recursively against random code entries, using three code checks per claim so that soundness loses a factor of four per level of the recursion. The exclusion from $\mathsf{PH}^O$ rests on a new switching theorem for the correlated random projections of the recursion: once the instance height is large enough, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-\Omega(n)}$ when the answer of a random instance is flipped by changing a single leaf.
-
The paper's central claim is a double complexity classification of $\mathsf{SparseIrred}_{\mathbb{Z}}$, the problem of deciding irreducibility in $\mathbb{Z}[X]$ for polynomials presented sparsely, where the input size charges only the logarithms of exponents and coefficients. Theorem 4 states that the problem is coNP-hard under deterministic polynomial-time many-one reductions: an exact-3-CNF formula $\Phi$ is encoded as a polynomial $F = A + X^M(X^N - 1)$ whose $N$-th roots of unity correspond, via the Chinese remainder theorem, to truth assignments of $\Phi$, and a gap theorem (a specialization of a simultaneous-approximation and polynomial-lifting argument) forces $F$ to be irreducible in $\mathbb{Z}[X]$ exactly when $\Phi$ is unsatisfiable; equivalently, reducibility is NP-hard, and irreducibility is NP-hard even under one-query Turing reductions. Theorem 10 states that the problem is in $\mathsf{PP} \subseteq \mathsf{PSPACE}$: the weighted modular-root count $A_f(X) = \sum_{p \le X}(\nu_f(p) + \mu_f(p))$ detects repeated as well as distinct factors, the average $A_f(X)$ approximates $\rho(f)\pi(X)$ with an error controlled by a zero-free half-plane $\operatorname{Re} s > 31/32$ for Dedekind zeta functions and by an effective prime-ideal counting estimate, and the inequality $2A_f(X) < 3\pi(X)$ at an explicit cutoff $X = 2^{32k}$ (with $k = O(L)$) decides irreducibility. The $\mathsf{PP}$ membership is realized by a majority machine whose accepting-minus-rejecting path count equals $2(3\pi(X) - 2A_f(X))$, and the same criterion yields a deterministic streaming algorithm that runs in polynomial space.
-
The core discovery is a density statement at a precise interval scale. Theorem B says that under the fixed zero-free strip, for every sufficiently large center $x$ and every length $h$ with $x^{3/4}\le h\le x$, the count $\Psi(x+h,y)-\Psi(x,y)$ of $y$-smooth integers (all prime factors at most $y$) in $(x,x+h]$, with $y=\exp(\sqrt{\log x\,\log\log x})$, satisfies $$\Psi(x+h,y)-\Psi(x,y)=\$\alpha$\,\frac{h}{x}\,\Psi(x,y)\left(1+O_\delta(1/u)\right),\qquad u=\sqrt{\frac{\log x}{\log\log x}},$$ and in particular $\Psi(x+h,y)-\Psi(x,y)\ge (h/4)\exp(-3\sqrt{\log x\,\log\log x})$. The proof adapts the contour method of [You24] — a central vertical segment, logarithmic arcs attached to zeta zeros, a right-envelope path, and a remainder line — to the fixed-strip hypothesis, using a local shift to dominate $|x^{\sigma+it}Z_y(\sigma+it)|$ and zero-density bounds to absorb the contribution of the retained zeros. Feeding this density into the genus-two construction of [Zha26] — a marked quintic family whose Jacobian orders over $\mathbb{F}_p$ are counted by the theorem of [LPP02], with charged positive certificates making a constructed integer divisible by every prime whose Jacobian order lands in the target interval — the transfer theorem converts smooth-order density in $I_p=[p^2-\tfrac12 p^{3/2},\,p^2+\tfrac12 p^{3/2}]$ into a program for $m_k k!$ of length $\exp(C\sqrt{\log k\,\log\log k})$, and every parameter and gate cost is included in that length.
-
Theorem 1 states that, for any fixed deterministic γ_T-mean-based learner with γ_T T = o($T^{{1-ζ}}$), unless P=NP, no polynomial-time optimizer that outputs explicitly represented mixed strategies can guarantee total reward within cT of the reward of the optimal pure-action sequence, for an absolute constant c>0. This holds on a family of explicit rational games. For zero-sum games, Proposition 5 shows that a pure myopic best-response strategy already approximates the optimal mixed trajectory within the learner's regret bound, achieving reward at least T·Val(A). Further, under the regularized FTRL model, Theorems 2 and 3 prove that deterministic pure play retains both the passive and active surplus rates that were previously established only for mixed play, up to rounding losses proportional to the support size.
-
The paper establishes that MEE is Σ_2^p-complete under polynomial-time many-one reductions. The key technical innovation is a reduction from Succinct Set Cover that avoids Turing reductions by precomputing the weight threshold K explicitly. Given an SSC instance, the reduction outputs a formula φ_w and an integer K such that SSC is positive iff L_w(φ) ≤ K. The right-to-left direction relies on a syntactic argument that any minimum-weight formula equivalent to φ can be rewritten as α ∨ (r ∧ β) without increasing weighted size, where α ≡ δ and β encodes a candidate cover. The weight constraints force β to mention at most k of the p_i variables, and then a contradiction argument shows that the corresponding θ_i form a cover.
-
For every constant α ≥ 1, there is an algorithm that, given an n-point metric space with aspect ratio Δ, runs in Õ(n² log Δ) time and outputs an α-navigable graph G satisfying two simultaneous bicriteria bounds: (i) |E(G)| ≤ 5 · OPT_{2α+12}, where OPT_β is the minimum edges in a β-navigable graph, and (ii) |E(G)| ≤ O(log n) · OPT_{α+7}. The algorithm first constructs two candidate graphs—one via separated ball covers (constant-factor guarantee) and one via greedy ball covers (logarithmic guarantee)—and returns the one with fewer edges. The construction uses a multiscale cover hierarchy with radii r_i = (1+1/α)^i and a fundamental geometric fact: if d(c,v) < d(c,u)/(α+1) then edge (u,c) is an α-navigation from u to v. The runtime is Õ(n² log Δ), optimal up to polylog factors for explicit metrics. A hardness result shows that for every constant η ∈ (0,1), no polynomial-time algorithm can achieve an (α, 2α-η)-bicriteria o(log n)-approximation unless P=NP, proving the factor-2 bicriteria threshold is tight.
-
The paper discovers a mapping between algebraic circuit lower bound statements and proof complexity hardness, establishing a three-tier hierarchy. On the upper tier, the strongest result is that the existing rank-method lower bounds against constant-depth circuits are provable in VNC² (and hence in NC²-Frege), meaning they do not require deep logical resources. On the middle tier, PCR—a proof system that combines polynomial calculus with resolution—is shown unconditionally incapable of efficiently proving any superpolynomial algebraic circuit lower bound, regardless of the polynomial f. This is achieved by a polynomial-time reduction from the iterated weak rank principle (IRankPE) to the algebraic circuit upper bound formula AlgCircuit(f, s, ℓ). On the lower tier, if diagonal tensor rank instances require large constant-depth IPS refutations, then constant-depth IPS cannot efficiently prove constant-depth algebraic circuit lower bounds. The paper thus provides the first unconditional proof-complexity lower bound for algebraic circuit lower bound statements and, under a reasonable assumption, extends the barrier to constant-depth algebraic proof systems.
-
The paper's central discovery has three parts. First, the image of the cube under the transformation $P$ that inverts stereographic projection, which is the feasible set for Spherical-Linear Bayesian Optimization, is essentially the sphere cut by a polyhedral cone: Theorem 1 gives the explicit inequalities $|y_d| \le \ell(1-s)$ with $\|(y,s)\| = 1$, and Corollary 1 identifies the region as $(H+n) \cap S^D$ minus the north pole. Second, because a Thompson draw maximizes a ratio of two quadratics, its maximizer over the cube can be found globally and quickly by Dinkelbach iteration, whose subproblems split into independent one-dimensional clipping problems; in the paper's experiments the iteration never took more than eight steps. Third, plain Thompson sampling degrades as dimension grows because the sampled noise vector's norm concentrates at a growing value, so the draw asymptotically ignores the posterior mean, and the paper repairs this by drawing $\tilde\beta = m + \kappa S^{1/2}\epsilon/\|\epsilon\|$, placing the sample on a fixed Mahalanobis-radius ellipsoid around the mean; this is Surface Thompson Sampling. Finally, Theorem 2 shows that an exact global solver for EI or UCB on this model class would solve MAXCUT, an NP-complete problem, so the paper concludes, subject to the P-versus-NP caveat it states, that no similarly efficient global algorithm for those acquisitions exists.
-
In its own terms, the paper's central claim is that arbitrary precedence DAGs are nearly free in this model. After compressing each job's release time and deadline into an effective window — $R_j=\max_{i\preceq j} r_i$, $D_j=\min_{j\preceq k} d_k$ — the edge-only problem becomes a minimum-cost flow on a network of interval nodes and job nodes, and Lemma 5 asserts that any window-feasible schedule can be reordered, keeping the server busy on exactly the same intervals, so that every ancestor finishes before every descendant without increasing cost. That gives the exact polynomial algorithm of Theorem 3. Cloud outsourcing is NP-hard even for independent jobs sharing a release time and deadline with zero local carbon cost, via a 0-1 knapsack reduction, but the paper constructs a reduction to preemptive scheduling with rejection penalties: dummy jobs encode each interval's capacity, with rejection penalties equal to the carbon cost of the released capacity, and Lemma 8 proves the optimal penalty equals the optimal cloud-outsourcing cost, so the FPTAS of Pruhs and Woeginger yields Theorem 4. Finally, Theorem 9 shows the single-server assumption is essential: two unit-speed edge servers without migration have no polynomial-in-$n$ approximation under unrestricted carbon-cost variation, unless P=NP.
-
The central claim, Theorem 1.2, is that an absolute constant $C>0$ exists such that for every integer $k\geq 2$ some positive integer $m$ satisfies $\tau(mk!)\leq \exp(C[\log(16k^2)]^{2/3}[\log\log(16k^2)]^{1/3})$, and consequently $\mu(k)\leq \exp(O((\log k)^{2/3}(\log\log k)^{1/3}))=k^{o(1)}$ as $k\to\infty$. The proof is constructive in principle: sample $J$ parameter vectors from a fixed five-dimensional integer grid of size $H=10k$; for each vector fix, from rational data alone and before any prime is tested, one integer circuit of length $O(\log k)$; a probabilistic transfer from a published counting theorem for genus-two Jacobian orders shows that with positive probability the sampled circuits are jointly divisible by every prime $p\leq k$; and repeated squaring converts that multiple of the primes up to $k$ into a multiple of $k!$. Every parameter construction, including the scalar, the discriminant and the retained inverses, is charged to the circuit length.
-
The central claim is Theorem 2: for generic (nondegenerate) two-player zero-sum games between a defender and an attacker, when the attacker is at least as powerful as the defender and both are limited to problems in $\mathrm{DET}$, three desiderata cannot hold at once — Maximal helpfulness (the AI's advice lets the defender compute her maximin strategy in every game), Non-maximal harmfulness (for at least one game the advice does not let the attacker compute his minimax strategy), and No situational awareness (the advice is public and recipient-independent). The engine is Lemma 1: computing a minimax strategy is $P$-hard, but given a maximin strategy the minimax strategy is computable in $\mathrm{DET}$, because for generic games it is the unique solution to a non-singular bordered linear system. Public advice that unlocks the defender's maximin computation therefore unlocks the attacker's minimax computation as well. Conditional on $\mathrm{DET}\subsetneq P$ the three axioms are independent, with each pair attainable by a suitable policy, and a security-game variant built on the Partition problem reproduces the trilemma under the $P\neq NP$ separation. In the information model, the paper shows that in a symmetric zero-sum game public advice cannot help the defender at all even when exclusive information would (Proposition 5), that partial disclosure can be maximally helpful to the defender and useless to the attacker where full disclosure helps neither side (Proposition 6), and that in general-sum games a competent informed AI can strictly lower the defender's utility, with private signals (Proposition 7) or with public verifiable signals (Proposition 8), because the attacker anticipates the AI's behavior and silence is not a credible commitment.
-
The paper's engine is the observation that zero energy is a list of vanishing sums of $\pm 1$ products. A group with an odd number of terms can never vanish; a two-term vanishing condition $s_i s_j + s_k s_\ell = 0$ is equivalent to one affine equation $x_i + x_j + x_k + x_\ell \equiv 1 \pmod 2$ over $\mathbb{F}_2$; and a single four-term gadget $\{A,B\},\{A,i\},\{A,j\},\{A,\ell\}$ vanishes exactly when one of the three variables is true. Consequently, instances whose groups or rows contain at most three terms reduce to a linear system decidable by Gaussian elimination, while four-term rows can encode exact-one or two-plus/two-minus constraints; reductions from Distinct Positive 1-in-3-SAT (satisfiability with exactly one true variable per clause, pairwise distinct and unnegated) and from 2-2 Set Splitting (every four-element set must split two-plus/two-minus) establish NP-completeness for Pair-Set-LABS, Masked-LABS, and single-window Masked-LABS (Theorems 4.5, 4.11, 5.4). When every active lag keeps its full correlation, odd sequence lengths admit an exact parity classification via skew-symmetric sequences: zero energy holds exactly when every active lag is odd, while even lengths with only even active lags become exactly the selected-lag complementary-pair feasibility problem (SLCP), whose complexity the paper leaves open.
-
The paper's central claim is that Rabin's research created or fundamentally reshaped nearly every major branch of theoretical computer science. The author supports this with a chronological tour anchored on specific results: the Adian–Rabin theorem turning undecidability into a general obstruction to classifying finitely presented groups; a theory of computable algebraic structures, including a computable algebraic closure for every computable field; the Rabin–Scott theory of finite automata, which introduced nondeterminism and proved $\mathrm{1NFA} = \mathrm{1DFA} = \mathrm{REG}$; the decidability of the monadic second-order theory of the infinite binary tree ($\mathrm{S2S}$), a foundation of verification and model checking; an axiomatic theory of computational complexity and early advocacy of polynomial time as tractability; randomized algorithms from primality testing and fingerprinting to pattern matching; cryptographic primitives such as oblivious transfer and public-randomness beacons; and probabilistic protocols for dining philosophers, mutual exclusion, and Byzantine agreement. The survey openly declares itself selective and shaped by the author's own knowledge and taste, and it states that Rabin's ideas became so embedded in the field's culture that their origin is easy to forget.
-
The paper establishes lower bounds matching previously known membership results: the reachability relation of a robust real-valued dynamical system is exactly as hard as polynomial-space computation, in two formally different settings. In the classical computable-analysis setting, the problem is $\mathsf{PSPACE}$-hard by reduction from a polynomial-space Turing machine: configurations are encoded as real numbers with radix-4 digits $1$ and $3$, the machine's transition function becomes a composition in the algebra $\mathsf{LDL}^\circ_{\mathrm{light}}$, and the Gap and Auto-correction lemmas show that every perturbed trajectory starting from the initial configuration stays within a small ball of the exact configurational trajectory, so perturbed reachability of the accepting configuration is equivalent to acceptance. In the second-order setting, with oracle Turing machines, the discrete problem $\mathsf{DRRL}$ is $\mathsf{PSPACE}^2$-hard under $\le_{2m}$-reductions, and the continuous problem $\mathsf{CRRL}$ inherits that hardness by simulating the discrete dynamics with a continuous ODE. The paper also proves that cosine may be dropped from the basis of the algebra $\mathsf{RCD}$ without losing its characterization of $\mathsf{FPSPACE}$. Membership in the relevant classes is taken from the earlier results [5, 7].
-
The central discovery is that the presence of backward steps in a random clock's transition kernel can strictly increase the observation class from polynomial to exponential time, even when the backward steps are rare and supported on a density-zero set of indices. For gated clocks whose only large forward jumps are doublings at powers of two, every forward-only member has class within P, whereas a step back by one from the landing indices gives EXP (Theorem 6.13). For a parity-dependent clock, deleting backward steps reduces the class from EXP to P (Theorem 6.6). These results are proved by analyzing the crossing probabilities of the underlying held walk and relating them to language recognition via the reachability dictionary (Lemma 2.18). The paper also classifies iid clocks by the tail of their jump distribution, showing that one computable law gives exactly EXP, one gives 2EXP, and a family gives QP_k for each k, with all classes independent of the confidence level.
-
The authors develop a new precision-boosting framework for relative approximation of positive arithmetic circuits. Unlike earlier work on substochastic matrix powering, the framework handles general degree-two positive polynomial maps by recursively propagating and cancelling first-order errors across layers via a Taylor-expansion correction (eq. (3.2)). For very high precision they simultaneously refine the gate-value vector and an approximate inverse of the global Jacobian, achieving quadratic convergence in each round. Applications rest on parsimonious reductions: a Cook-style decomposition turns acceptance of a BPAuxPDM into a counting circuit of algebraic degree 3T+1, and a local-table encoding parsimoniously places the acceptance-count function of a read-k machine in #L. Both reductions feed through the Allender-Jiao-Mahajan-Vinay depth-reduction theorem to yield an L-uniform #$SAC^{1}$ circuit, to which the approximation theorems apply.
-
The central claim is that the complexity of $m_\lambda(x_1,\dots,x_n)$ is governed by the number $D(\lambda)$ of distinct parts of the partition $\lambda$. If a p-family has $D(\lambda_n)\ge n^\epsilon$ for some $\epsilon>0$, and if the variable count $v_n$ is at least the degree $d(\lambda_n)$, the family is VNP-complete under c-reductions; if $D(\lambda)=t$ is constant, $m_\lambda$ is computable by a circuit of size $\mathrm{poly}(d)\cdot n^{O(t)}$. The genuinely new ingredient is a hardness statement about matching polynomials of blow-up graphs: the ordinary perfect matching polynomial of $K_t$ c-reduces to the perfect matching polynomial of any blow-up $K_r^{(w)}$ with arbitrary positive integer multiplicities $w_i$ and even total vertex count (Lemma 3.1). This is what lets repeated parts enter the reduction: repetitions behave as vertex blocks, and the forced pairings among copies of selected parts become exactly the perfect matchings of the blown-up graph. The two ends together leave only the subpolynomial regime open, and the authors record in Section 5 that the variable-count condition is a limitation, not a formality.
-
The paper shows that the function family G_n = 1 - Cheat-Shape_n has quantum communication complexity O($log^{3}$ N_n) and Merlin–Arthur communication complexity Ω($N_n^{{1/12}}$ / $log^{{1/6}}$ N_n). Since G_n ∈ BQP^cc but G_n ∉ MA^cc, it follows that BQP^cc ⊈ MA^cc.
-
The paper discovers that by treating catalytic space as a set of registers that can be temporarily modified and then restored, one can evaluate low-depth circuits of symmetric gates and low-multiplicative-depth arithmetic circuits with only logarithmic clean space and little time overhead. For symmetric circuits, a combinatorial trick allows a layer of gates to be evaluated using two recursive calls and O(w) work per layer, leading to time O( w 2^d ). For arithmetic circuits, the approach separates linear and multiplicative layers, so that only multiplicative layers incur recursion, yielding time O( w 3^d T ) for d multiplicative layers over a uniform ring. These circuit evaluations directly yield catalytic algorithms for sorting, FFT, and matrix multiplication that match (up to subpolynomial factors) the best known runtimes, while using O(log n) clean space and poly(n) catalytic space.
-
The central discovery is that optimistic SLMF problems admit an equivalent bilevel reformulation (Theorem 3.2), while pessimistic SLMF problems are equivalent to optimistic trilevel problems (Theorems 4.2 and 4.4). Under rational linear data, these reformulations preserve linearity and have polynomial encoding length. Consequently, the decision problem for optimistic SLMF is NP-complete, for pessimistic SLMF it is $\Sigma_2^p$-complete, even without coupling constraints (Theorems 5.1, 5.3). This complexity gap does not appear in single-follower settings.
-
The paper's central claim is the $\mathrm{P}$ versus $\mathrm{NP}$-complete dichotomy for discrete temporal CSPs. Theorem 69 and Corollary 70 assert that for every finite-signature first-order reduct $\Gamma$ of $(\mathbb{Z},<)$, $\mathrm{CSP}(\Gamma)$ is in $\mathrm{P}$ or is NP-complete. The proof funnels every reduct into one of four normal forms (Theorem 20): homomorphically equivalent to a finite structure; to a first-order reduct of $(\mathbb{Q},<)$; to a first-order reduct of $(\mathbb{Q}\times\mathbb{Z},<)$ that primitively positively defines (can simulate as a constraint) the successor relation; or to one that pp-defines every distance relation $\mathrm{dist}_n$. The first two cases inherit known classifications, the all-distances case is NP-hard by a short reduction, and the successor case is the one the paper reworks, replacing a false lemma in the earlier proof with the trichotomy of Proposition 67. The paper also proves a uniform-algorithm statement (Theorem 73): unless $\mathrm{CSP}(\Gamma)$ equals the CSP of a finite structure, the promise problem $\mathrm{PCSP}(\Gamma|_{[n]},\Gamma)$ is solved by the single algorithm $\mathrm{CSinglAC}\wedge\mathrm{SinglAIP}$ for every $n$. The same reduction machinery yields complete dichotomies for first-order reducts of the triangular lattice graph and of infinite regular trees (Theorems 77 and 83).
-
In the paper's own framing, the main claim is that Symmetry of Information for nondeterministic measures is a real computational phenomenon, not a formal curiosity. The paper proves that $rnKt$ and $pnKt$ satisfy average-case SoI over all samplable distributions, while worst-case SoI for $nKt$ or $rnKt$ would imply TAUT not in AMTIME[$2^{{log^d n}}$] and the collapses FewEXP subset BPP^NP and $EXP^{{parallel NP}}$ subset NP/poly cap coNP/poly, placing the failure of SoI at the same level as the non-collapse of the polynomial hierarchy. The central equivalence states that SoI for $rnKt$, membership of Gap-MrnKtP in pr-BPTIME[$n^{{polylog n}}$]^{parallel NP}, the existence of a natural property against $rnKt$, and explicit constructions for dense pr-BPTIME[.]^{parallel NP} properties are quantitatively equivalent. From this correspondence the paper derives unconditional lower bounds: MnKtP is not in NTIME[$2^{{eps n}}$] cap coNTIME[$2^{{eps n}}$] with a dense-language version for thresholds gamma > 1/2, and Gap-MrnKtP is hard for exponential Arthur-Merlin time and quasi-polynomial circuits. It closes with an unconditional failure of conditional SoI for $nKt$ at every polylogarithmic error bound.
-
The central claim is that the implication DistPH⊆AvgBPP ⇒ PH⊆BPP is equivalent to the implication Gap-MINpKT^PH ∈ prBPP ⇒ Mild-Gap-MINpKT^PH ∈ prBPP. This is proved by two separate equivalences: DistPH⊆AvgBPP ⇔ Gap-MINpKT^PH ∈ prBPP, and PH⊆BPP ⇔ Mild-Gap-MINpKT^PH ∈ prBPP. Thus, the average-case versus worst-case complexity of PH reduces entirely to a comparison between two approximation regimes for probabilistic time-bounded Kolmogorov complexity with PH oracle access.
-
The central finding is that imposing per-color page budgets on already fixed-spine-order stack and queue layouts jumps the decision problem from polynomial time to NP-complete, sharply separating the capacitated from the ordinary case unless P=NP. Specifically, Fixed Order Capacitated 2-Page Stack Layout and Fixed Order Capacitated 2-Page Queue Layout are NP-complete even when every connected component of the conflict graph has at most five vertices and the instance is balanced and tight. For queue layouts, the problem remains NP-complete for monochromatic (single-color) instances with any number of pages, implying W[1]-hardness parameterized by the number of pages. The paper also provides matching fixed-parameter tractable algorithms for combinations of parameters such as number of pages, number of colors, and component size.
-
The paper's central claim is that inclusion-wise extremality splits the two properties that classical knapsack enjoys together. A weight-indexed dynamic program still solves both problems in pseudo-polynomial time, $O(nc)$ for the packing side and $O(nd)$ for the cover side, but the value-indexed dynamic program that underlies the classical FPTAS cannot exist unless P=NP, because on unit-value instances it would be a polynomial-time algorithm for an NP-hard problem. The mechanism behind every hardness gap is exact filling: once items are sorted by weight, maximality and minimality are decided by a single extremal item, and a unit-weight item that is excluded from a maximal packing, or included in a minimal cover, forces the load to equal the capacity or the threshold exactly, turning knapsack inequalities into subset-sum equalities. This yields, for any polynomial $p$, a $2^{p(n)}$ inapproximability bound with positive values, and, by scaling up the number of unit-weight items, an $n^{1-\varepsilon}$ lower bound in the unit-cost and unit-profit cases, tight against the trivial factor $n$. The positive half identifies what restores approximability: a fixed lower bound on item weights makes both problems exactly solvable in polynomial time; on the cover side a shifted weight condition gives a scheme polynomial in $1/\delta$; the proportional case $v_i = w_i$ yields an FPTAS for the Greedy Boss Problem, improving the known factor 2; and a bounded value-to-weight spread $\kappa$ yields a $(1+\varepsilon)\kappa$-approximation for both problems.
-
The paper proves that for a broad class of activation functions (including threshold, ReLU, GELU, and sigmoid), a single time‑invariant autoregressive neuron can simulate any $\sigma$-circuit (feedforward network) of size $s$ on $n$ inputs. The simulation uses dimension $d = O(ns + s^2)$ and $T = O(s^2)$ generation steps, both independent of circuit depth. For threshold activations this yields a depth‑independent simulation of Boolean threshold circuits, and consequently of polynomial‑time Turing machines. For real‑valued activations that satisfy either a zero‑region condition (exact simulation) or a decay‑to‑zero condition (approximate simulation), the result covers feedforward neural networks with the same activation. The construction is based on a novel connection to Sidon sets from additive combinatorics, which prevents weight collisions in the shared parameter vector.
-
The paper establishes two hardness results. First, for every fixed rational c>0, computing a $2^{{-n^c}}$-approximate Nash equilibrium in an n-player two-strategy anonymous game is PPAD-complete. This holds even when one strategy always pays 1/2 and, for all but two players, the other strategy's payoff is constant outside at most five opponent counts. Second, computing an exact Nash equilibrium in a three-strategy anonymous game is FIXP-complete, and approximating within epsilon in ℓ∞ distance to an exact equilibrium is FIXPa-complete. Both reductions use the fact that anonymous count distributions can encode individual mixed strategies through carefully designed coefficients and polynomial roots.
-
The paper establishes that learning, compression, and meta-complexity are not merely analogous but are formally interconnected through reductions, equivalences, and characterizations. It defines five "learning paradises" (extrapolation, distribution learning, agnostic learning, PAC learning with membership queries, heuristic learning) and places them within Impagliazzo's computational worlds via meta-complexity. Key results include: the average-case easiness of Gap-MINKT implies efficient extrapolation (and thus all weaker paradises); heuristic learning implies the non-existence of one-way functions; distribution learning implies agnostic learning through a white-box learning argument; and PAC learning with membership queries is equivalent to the existence of a natural property, which can be used to derive learning speedups. The survey also presents an arithmetic-coding transform from next-bit prediction to compression, and connects universal extrapolation to a time-bounded version of Solomonoff induction.
-
The paper establishes that minWSPD in fixed-dimensional Euclidean spaces and doubling metrics admits a bicriteria PTAS: for any constant $\delta>0$, one can compute a $(1+\delta)\varepsilon$-separated family of dumbbells whose size is at most $(1+\delta)$ times the minimum possible for $\varepsilon$-separation, in time polynomial in $n$ (with an exponential dependence on $d$ and $\delta$). The algorithm combines shifting over scales with the local-growth technique of Nieberg, Hurink, and Kern, applied to a compatibility graph whose vertices are the point pairs. Rounding to a grid (or net in doubling metrics) makes each local subproblem finite and solvable by brute force. Conversely, the paper shows that in general metric spaces this bicriteria guarantee cannot be achieved for $\tau<2$ unless P=NP, via a reduction from clique cover that uses block metrics padded with copies of an input graph.
-
The paper proves, as its headline theorem, $\exists\mathbb{R}\subseteq\mathsf{BPP}^{\mathsf{C}_3\mathsf{P}}\subseteq\mathsf{C}_4\mathsf{P}$: the existential theory of the reals lies in the fourth level of the counting hierarchy, decided by a randomized polynomial-time machine with a $\mathsf{C}_3\mathsf{P}$ oracle. The reduction first converts ETR into a feasibility test for a weighted quartic objective $J$: the instance is feasible exactly when $J$ has a real critical point with value below a threshold $T$, and the critical system $X_i^5+X_i+1+(Q_0/w_i)\partial_i F=0$ is engineered so that Hensel lifting over the two-adics yields $D=5^m$ simple points with pairwise distinct critical values. Each real root of the norm polynomial $q(z)=\mathsf{Norm}(z-J)$ receives an integer label $r_i=S_i+(D-1)/2$ obtained from limiting half-plane signs of a rational normalizer; a random affine hash on the $\ell=\lceil\log_2 D\rceil$ labels isolates one qualifying root, and a $\beta$-identity phase test recovers the sign of the resulting integer from short-modulus residues. The whole computation runs over one shared formal homotopy in an unramified Galois ring, with the final Fourier sum deliberately retained as an unreduced counting representative to save an oracle level. The same machinery, with the arithmetic ledger shown level by level, yields $\Sigma_w\mathbb{R}\cup\Pi_w\mathbb{R}\subseteq\mathsf{C}_{9w+17}\mathsf{P}$ for each fixed $w$, and the applications section derives the SDP, PosSLP, square-root-sum, geometric-counting, and Nullstellensatz bounds stated in the abstract.
-
On the paper's own terms, the discovery is a precise threshold in the expressiveness of arithmetic term bases for $\mathcal{E}$. Theorem 1 shows that $S = \langle x+y, \lfloor x/y \rfloor, 2^x \rangle = \langle x+y, xy, \lfloor x/y \rfloor, 2^x \rangle$ is a proper subclass of $\mathcal{E}$: multiplication is already definable in $S$, so the gap is not arithmetic weakness but the inability to lower exponents, and no unary $S$-term satisfies $T(2^n) = n$. Theorem 14 and Corollary 15 extend the failure uniformly to every fixed integer base $b \geq 2$. Theorem 2 shows that allowing the base to depend on the input restores completeness: $\langle x+y, \lfloor x/y \rfloor, x^y \rangle = \mathcal{E}$. Theorem 3 shows the weak class is still truth-complete: $\mathrm{Pred}(S) = \mathrm{Pred}(\mathcal{E})$, and every elementary function with fixed finite range belongs to $S$.
-
The central claim is that a standard cryptographic assumption transfers the classical natural-proofs barrier from Boolean circuits to quantum state preparation. The paper constructs a family of states, built from a complex-Gaussian sampler fed by a pseudorandom function, whose full finite-precision amplitude lists are indistinguishable from those of Haar-random states to any polynomial-time classical algorithm, yet whose individual members can be approximately prepared by polynomial-size circuits at level $MH_{8d_F+20}$ of the magic hierarchy. Any natural property that is useful against those circuits would give an efficient classical distinguisher between the two ensembles, contradicting pseudorandomness. Consequently, proving superpolynomial state-preparation lower bounds at that level cannot be done by any natural argument without breaking the cryptographic assumption.
-
The discovery, stated as Conjecture 1, is that FACTORING does not lie in $BPP^{\mathrm{Samp}\ \frac{1}{2}\mathrm{BQP}_1}$, where the superscript records polynomially many adaptive requests to the interface with randomized polynomial-time classical post-processing, and FACTORING asks for one specified bit of the smaller prime factor of an $n$-bit semiprime. As evidence, the paper proves two structural facts. Theorem 10 shows that for any single-call circuit $A = N O_\pi V$ — a computationally tractable preparation $V$, one call to an arithmetic permutation oracle $O_\pi$ such as modular exponentiation, and a normalizer postprocessor $N$ such as a Fourier transform — the first-qubit outcome on every basis input, and the complete transcript of $T$ adaptive requests, is classically sampleable to total variation error $\delta$ in polynomial time. Theorem 11 shows that the natural counterattack is closed off: if rational reconstruction were in $\mathrm{NC}^1$, then FACTORING would already be in $BPP^{\mathrm{Samp}\,\mathrm{DQC1}} \subseteq BPP^{\mathrm{Samp}\ \frac{1}{2}\mathrm{BQP}_1}$, and since rational reconstruction lies in P, a proof of the conjecture would separate P from $\mathrm{NC}^1$. The same two theorems frame a finite-size security regime and a candidate application that distinguishes $\frac{1}{2}$BQP$_1$ from DQC1 through weighted infinite-temperature traces.
-
The paper's central claim is that one can isolate a unique small quantum witness in logspace. For a yes-instance of a FewQUMAL$_1$ protocol, the perfectly accepting witnesses form a subspace of polynomial dimension; releasing randomness and giving the decider oracle access to a UQUMAL$_1$ problem, such a protocol can be decided (Theorem 1.1). The obstruction is that the natural reduction, sending the antisymmetric product of all $k$ basis witnesses, spans $k$ registers and $k\cdot w$ qubits, which a space-bounded verifier cannot materialize. Instead, the paper applies randomized perturbations drawn from a robust subspace design to the circuit-to-Hamiltonian matrix of the verifier. By the kernel peeling lemma, some perturbation $H + Q_i^*Q_i$ has kernel of dimension one with an inverse-polynomial spectral gap, and the unique $O(\log n)$-qubit kernel state of that perturbed Hamiltonian is the isolated witness, verifiable through the already known kernel-verification procedure for well-conditioned singularity. Along the way the paper proves that poly-conditioned FewSINGULAR is FewQUMAL$_1$-complete, that pc-NULL$_k \in \text{coRL}^{\text{QUMAL}_1}$ and pc-FSLE $\in \text{BPL}^{\text{QUMAL}_1}$, and that ordinary subspace designs give NULL $\in \text{C}_=$ through a simpler reduction than the classical one.
-
The central claim is Theorem 1.1: assuming quantum commitments exist, either there is no polynomial-time solution to the unitary synthesis problem (unitaryALL ≠ unitaryP^ALL), or BPP ≠ NEXP. This is derived from Lemma 7.4, which states that for every language L and every unitary U ∈ unitaryPSPACE^L, either U ∉ unitaryP^ALL or U ∈ unitaryP^FNEXP^L[poly] — every polynomial-space-computable unitary is either impossible to synthesize efficiently relative to any classical oracle, or reducible to NEXP witness search. Along the way the paper proves that unitaryPSPACE equals the set of unitaries whose entries are approximable to error ε in space poly(n, log 1/ε) (Theorem 6.17); that garbage can generically be erased in polynomial space (Theorem 6.19) but provably not relative to unitary oracles (Theorem 6.23); and that the with-garbage and garbage-free definitions are interdefinable (Theorems 5.20–5.22). A corollary of independent interest is that any single classical oracle separating unitaryP^PSPACE^L from unitaryPSPACE^L would imply a non-relativized breakthrough, namely NC ≠ NP or AM^L ≠ NEXP^L.
-
The paper's central claim is Theorem 4 together with its conversion to a fixed oracle (Theorem 7). Two distributions over tables $O : \{0,1\}^q \times C \to \{0,1\}$ are defined, with $C$ a univariate multiplicity code over $\Sigma = \mathbb{F}_q^\lambda$ and $\lambda^5 < q \le 2\lambda^5$. Under $\mathsf{YES}_\lambda$ a pair $(y,v)$ is marked exactly when $v \in C$ is a preimage $H(v) = y$ of a target padded as $y = u \parallel 0^{q-\lambda}$, with hash entries independent Bernoulli($\lambda^{-4}$); under $\mathsf{NO}_\lambda$ each pair is marked independently with probability $\delta = 2^{-\lceil \lambda/12\rceil}$. The QMA verifier samples a padded target, decodes a codeword from the fixed quantum witness $\lvert \Psi_H\rangle$, and makes one classical query: for every sufficiently large $\lambda$ there is a witness accepted with probability at least $1-2^{-\lambda}$ on all but a $2^{-\lambda}$ fraction of YES oracles, and on all but a $2^{-\Omega(\lambda)}$ fraction of NO oracles every witness is accepted with probability at most $2^{-\Omega(\lambda)}$. Conversely, for every QCIP protocol that accepts with probability at least $2/3$ on a $1-\varepsilon$ fraction of YES oracles, some cheating prover makes it accept with probability greater than $1/3$ on at least a $1/3-\varepsilon$ fraction of NO oracles. Restriction and diagonalization convert this into a fixed classical oracle $\mathcal{O}$ with a unary language $L \in \mathsf{QMA}^{\mathcal{O}} \setminus \mathsf{QCIP}^{\mathcal{O}}$.
-
The central claim is that static properties of quantum impurity models are classically computable in polynomial time, with no assumptions on geometry or spectral gap beyond the bath being noninteracting. Concretely, for any impurity Hamiltonian $H = H_0 + H_{\mathrm{imp}}$ on $n$ fermion modes with constant impurity size $m$, there is a classical algorithm computing the ground-state energy to additive error $\delta$ in time $\mathrm{poly}(n,\delta^{-1})$, and — at any inverse temperature $\beta$ — the partition function $Z = \mathrm{Tr}(e^{-\beta H})$ to relative error $\delta$ and expectation values of fermionic Gaussian observables to additive error $\delta$ in time $\mathrm{poly}(n,\beta,\delta^{-1})$. The technical core is a compression lemma: there exists a classically constructible subspace of dimension $\mathrm{poly}(n,\delta^{-1},\omega^{-1})$ carrying a ground state to weight $1-\delta$, with $\omega$ the bath spectral gap, and analogously a subspace of dimension $\mathrm{poly}(n,\beta,\delta^{-1})$ for the thermal state when $\beta\omega \ge 9\log n$; the dimension is independent of the impurity interaction strength and the impurity–bath coupling. On the dynamics side, the paper shows the two-time Green's function $G_\beta(t,t') = \langle \gamma_j(t)\gamma_k(t')\rangle_\beta$ of a time-dependent impurity Hamiltonian is DQC1-complete for $\beta = 0$ and BQP-complete for $\Omega(1)\le\beta\le\mathrm{poly}(n)$, proved via a single-ancilla universal encoding that avoids the exponential attenuation of prior encodings and via algorithmic cooling at finite temperature.
-
The paper's central discovery is that the many-copy W-test of Grier, Morris, and Wu can be made exact. For a fixed promised weight $k$, the probability that at least one of $m_k$ parallel W-tests rejects a string of weight $k$ depends only on $n$ and $k$, so a controlled rotation chosen to make this overlap exactly $1/4$, followed by a single reflection, perfects the test: weight-$k$ strings land on the 'some test fails' branch with certainty while weight-$n/2$ strings are left unchanged; taking the AND over all $k\neq n/2$ with $O(n^2)$ copies yields exact EX$_{n/2}$, hence exact threshold and TC$^0$ computation. The companion discovery is a finite gate set: a coherent Bernoulli sampler encodes any real single-qubit gate as a non-negative linear combination of $\pm Z,\pm X$, and one round of oblivious amplitude amplification (the all-zero ancilla branch has amplitude exactly $1/2$) turns the approximate block encoding into an $\epsilon$-approximation using only Hadamard, Toffoli, and $S$ gates.
-
Correctness and privacy conflict irreconcilably in oracle-aided verification. The paper exhibits a computation $C^\star_f(0^n,w)=1$ iff the first bit of $f(w\|i)$ is zero for every $i\in[m]$, a table with $2^m$ rows and $m$ columns whose witnesses are the labels of all-zero rows; under a uniformly random oracle a witness cannot be found except by querying the row whose label is that witness. The proof switches between the real oracle $f$ and a modified oracle $f'$ that zeroes one row $w$: completeness forces the honest verifier, in the world with $f'$, to query row $w$ with high probability, because otherwise it could not distinguish the honest execution from a cheating one in the real world, and making that query means the verifier learns the witness $w$ on its own. Lemma 4.4 packages this as $\alpha + \beta(pq, O(pt+pq\cdot t(n))) + \varepsilon_{\mathrm{WH}}(O(vq\cdot t(n)), O(vt+vq\cdot t(n))) \ge (1 - 1/2^{t(n)})^{2^{t(n)}} > 0.36$, so error bounds of $1/10$ each sum to $0.3 < 0.36$ and are impossible, with no succinctness assumption used anywhere. Folding the honest, witness-less opponent of a debate into the verifier reduces a witness-hiding debate to a single-prover argument, extending the impossibility. The positive construction has the oracle sign each answer, $\hat f(q)=(a,\sigma)$ with $\sigma\leftarrow\mathrm{Sign}(sk,(q,a))$, and the prover then proves the NP statement that it holds an accepting, correctly signed execution trace of $D$ on $(x,w)$, an ordinary zero-knowledge argument of knowledge that hides the queries themselves.
-
The central claim is that the algorithmic complexity of strong odd coloring splits cleanly: the problem is hard in the worst case and in approximation, yet becomes optimally solvable in linear time on block graphs. The paper proves STRONG ODD k-COLORABILITY is NP-complete on perfect elimination bipartite graphs for every k ≥ 3 (Theorem 1), and that χ_so cannot be approximated within O(n^(1/2-ε)) for any ε > 0 unless P = NP (Theorem 3), a transfer of Zuckerman's inapproximability of the chromatic number through a construction where the approximation factor's exponent halves because the reduction is size-quadratic. Against that hardness, Algorithm 1 computes an optimal strong odd coloring of any block graph in O(|V|+|E|) time (Theorem 4): it walks the cut-tree in breadth-first order, reusing the parent's colors in the child blocks while pairing each reused color across blocks so that parity flips from even to odd exactly when the final block is colored. In parallel, the paper establishes that the problem is FPT by treewidth with running time O(n^O(1) · (k·9^k)^tw), that this dependence cannot drop to (k-ε)^tw for k ≥ 3 under SETH, that no polynomial kernel exists parameterized by feedback vertex set, and that the problem is W[1]-hard parameterized by clique-width.
-
The paper's central claim is that the structural count of bad vertices is exactly the resource that separates small certificates from space-hard instances. On the upper side, any run induces a set $\Gamma$ of summary functions, and the authors bound $|\Gamma|$ by $\left(1 - |P(G)| + \sum_{v\in P(G)} |N^*(v)|\right) \cdot \prod_{v\in B(G)} |N^*(v) \cap N[B(G)]|$, independent of run length; because a run with few distinct summaries yields a polynomially verifiable certificate (Lemma 5), this gives nondeterministic time $|I|^{O(b+1)}$ and membership in NP for every class with at most $b$ bad vertices (Corollary 11). On the lower side, a bad counter can be turned into a testing gadget that nondeterministically guesses a counter value and, through cyclic shifts, verifies the guess while any wrong guess permanently contaminates a counter so no invalid run reaches the final marking (Propositions 32-34). For any transfer graph with $b$ bad vertices these gadgets encode acceptance of a Turing machine on $b^{O(1)}$ tape cells, so every polynomial-time constructible family with linearly many bad vertices is PSPACE-hard (Corollary 20). The same count that bounds witnesses in the upper bound is the count that stores tape cells in the hardness direction, which is the sense in which the transfer patterns are responsible for the complexity increase.
-
The central claim is Theorem 7.3: for any theory G containing quantum theory in the sense of Definition 5.4 (composites of qubits are the ordinary quantum composites, all CPTP maps are allowed channels, and the quantum gates are present), every quantum verifier V and every input x satisfy val_G(V_x) = val_quantum(V_x). The proof shows that any prover strategy of G induces a quantum comb on the message registers: positivity on all extensions together with Choi's theorem gives complete positivity, causality gives the normalization constraints, and the realization theorem for quantum combs supplies a purely quantum prover with identical acceptance probability. A complementary pair of results fixes the boundaries: for classical messages, Lemma 6.2 reduces any prover to a classical randomised prover and Fact 6.4 to a deterministic one, giving GIP_cl(G) = PSPACE for every theory satisfying (T1)-(T4); while Theorems 8.1, 8.5 and 8.7 construct theories G_v and G^Q_v that contain quantum theory and classical theory and are isomorphic to quantum theory with classical systems, yet in which a single prover message lets the verifier estimate a real parameter v encoded in the state-space geometry, so the interactive-proof class strictly exceeds PSPACE for noncomputable v and even for a computable v built from the unary space hierarchy theorem. In these theories every gate has integer or dyadic entries; only the state cone, which assumption (T4) leaves unconstrained, carries the noncomputable or hard number.
-
The central claim is Theorem 1.1: for any symmetric positive definite matrix M with positive entries, Pl-GH(M) is #P-hard unless, after a simultaneous permutation of rows and columns, M = λ ⊗_{i=1}^{d} [[a_i, b_i], [b_i, a_i]] with λ > 0 and a_i > b_i > 0, and in exactly those cases the problem is polynomial-time computable. Moreover, category (2) of the general non-negative dichotomy — P-time over planar graphs but #P-hard over general graphs — consists precisely of the problems that involve the FKT algorithm together with a holographic transformation. The theorem closes the gap left after the n=3 and n=4 classifications by a structural analysis that replaces gadget-by-gadget chase with an algebraic object: the entrywise logarithms of every realizable matrix form a finite-dimensional R-algebra whose polynomial homomorphism forces a metric, whose distance-regular classification yields Hamming coordinate graphs, and whose binary cube geometry pins down the Ising tensor form of M, with a_i > b_i forced by positive definiteness.
-
The paper's central claim is Theorem 1: for $k=\mathbb{Q}$ or $k=\mathbb{F}_q$, the problem ${\rm APS}_k$ lies in the counting hierarchy. The argument treats a positive instance as a witness curve $x^*(\varepsilon)$ in the valued field $\mathbb{K}(\varepsilon)$ over which all coordinate polynomials have positive $\varepsilon$-valuation, then encodes the possible values of the last coordinate at the finitely many prescribed solutions as the roots of a resultant $R(Z)$. A root with positive valuation exists exactly when the Gauss valuation of $R(Z)$ is smaller than the valuation of $R(0)$, and this inequality is turned into a query to the multivariate resultant valuation problem, whose coefficient tests belong to the counting hierarchy. Along the way the paper proves that Hilbert's Nullstellensatz over $k$ reduces in polynomial time to ${\rm APS}_k$, and that ${\rm APS}_{\mathbb{Q}}$ reduces to the existential theory of the reals.
-
The central claim is that permutation-invariant, all-to-all k-local quantum dynamics, including disorder-averaged Dicke, quantum Hopfield, and short-time Sherrington–Kirkpatrick models, can be simulated using only O(log N) qubits and logarithmic classical workspace in polynomial time, and that this regime is conditionally hard for classical algorithms. The compression is made constructive: entries of the compressed Hamiltonian and observable on the symmetric subspace are computed on the fly in logarithmic space (Lemmas 2 and 3), the compressed operators are expanded into Pauli strings that are never stored but generated one at a time (Lemmas 4 and 5), and the time evolution is realised as a gate stream emitted by a logarithmic-space classical controller (Theorem 1). Complementing the algorithm, the authors prove that simulating such dynamics is at least as hard as running an arbitrary logarithmic-qubit quantum circuit under polynomial-time, logarithmic-space reductions; a classical algorithm meeting the same time and space bounds would therefore imply BQL ⊆ SC (or BQL = BPL for log-space randomised algorithms), as stated in Theorem 2. For short evolution times the situation differs: sampling is classically simulable up to t = O(log N/N) and expectation values to constant accuracy at t = O(1), and the same bounds cover fixed-rank disorder through the ancilla-dilation reduction of Lemma 1. The claim, in one line: disorder averaging compresses N-spin dynamics into logarithmic space, and no classical algorithm is known to match that compression in both time and space simultaneously.
-
The central claim is Theorem 1: with rational plant data, SOF stabilization is ∃R-complete under deterministic polynomial-time many-one reductions, and it remains ∃R-complete when restricted to minimal integer plants with two inputs. In the paper's own terms, deciding whether a real gain makes the closed loop Hurwitz is polynomial-time equivalent to deciding whether a system of polynomial equations and inequalities over the reals has a solution; consequently, unless P = NP, no exact algorithm can decide all SOF instances in polynomial time, and this difficulty survives for controllable and observable plants with only two inputs. The reduction starts from the ∃R-complete problem ETR-INV, encodes the residuals of its equations as coefficients of the closed-loop characteristic polynomial, and then uses a quantitative separation bound so that any stabilizing gain forces exact feasibility of the source instance. The companion results are Theorem 2, a deterministic exact algorithm with bit complexity $(L+1)^{c}(n+1)^{c(\kappa+1)}$ that also returns a rational stabilizing gain whenever one exists, and Theorem 3, which shows SOF stabilization is NP-hard for minimal single-input integer plants, with feasible instances admitting gains in $\{-1, 1\}$ that tolerate simultaneous perturbations of magnitude at most $1/16$.
-
The central claim is Theorem 1.1. Let \(\psi\) be a fixed two-qubit state with maximally mixed marginals, used by two noncommunicating provers who share arbitrarily many copies of \(\psi\) and nothing else. If \(\psi\) is separable or \(\rho_{\max}(\psi)<1\), then \(\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]=\mathsf{NEXP}=\mathsf{MIP}\); if \(\psi\) is entangled and \(\rho_{\max}(\psi)=1\), then \(\mathsf{MIP}^{\psi}[\mathrm{poly},\mathrm{poly}]=\mathsf{RE}\). The proof removes the constant-answer restriction of the prior work [DFN+25] and completes the remaining case, where maximal correlation one does not by itself decide the power because even a shared classical random bit has maximal correlation one. The decisive distinction at \(\rho_{\max}=1\) is entanglement: the authors show that any entangled boundary state \(\Psi_\$\lambda$\) contains an exact maximally entangled component of weight at least \(\$lambda^{2}$\) in every finite dimension, extractable by a Hamming-partition relabeling followed by bilateral Pauli twirling, so that constant-answer EPR protocols for \(\mathsf{RE}\) survive with a fixed transmission loss and can be amplified back to a constant completeness–soundness gap.
-
The central claim, proved as Theorem 3.5 and promoted to a diagonalized oracle separation in Section 3.4, is that relative to a constructed classical oracle $O$, $\mathsf{BQP}^O \not\subseteq \mathsf{QIMA}^O$, and hence $\mathsf{QIMA}^O \neq \mathsf{QMA}^O$. Because CLH is complete for QIMA, this is relativized evidence that the general commuting local-Hamiltonian problem is neither BQP-hard nor QMA-complete. The proof works by showing that any verifier satisfying the reflection normal form and deciding the Forrelation promise problem must make exponentially many queries: after the classical preprocessing is frozen on a perfect Forrelation pair built from a bent function, the dimension of the accepting subspace becomes a multilinear polynomial in the oracle truth-table whose degree is bounded by the number of quantum queries; Minsky-Papert symmetrization turns it into a univariate polynomial that is nonzero at the perfect pair but vanishes on $\beta 2^n - O(1)$ integer no-instances, forcing a matching degree lower bound.
-
For each fixed depth $d$ there is a constant $\epsilon_d > 0$ such that $\mathrm{KW}(\mathrm{Parity}_n)$ has no $d$-round protocol of cost $m$ when $m \le \epsilon_d n^{1/(d-1)}$, with the consequence that any depth-$d$ unbounded fan-in De Morgan circuit computing the $n$-bit parity function requires more than $2^{\epsilon_d n^{1/(d-1)}}$ wires (Theorem 3). The lower bound is essentially tight, matching the known optimal exponent up to the constant. The proof is completely top-down: it maintains an invariant, a limit condition asserting that elements of one side of the current rectangle are geometrically surrounded by the other side, meaning a random small coordinate set reaches a neighbour in the opposite colour, and on each round supplies the adversary's next move directly from that invariant, never by assuming a protocol exists and deriving a contradiction from a prior circuit lower bound. The invariant is propagated by mirror-set lemmas showing that a one-sided limit condition forces a quantitatively weaker two-sided version after a cheap protocol message, with the hardest step being a lemma bounding how many light patterns a high-entropy variable can exhibit under random projection (Lemma 10), whose proof turns on a new harmonic mean transform inequality (Lemma 12).
-
On the paper's own terms: RIT for rational circuits, with no correctness promise on the input, lies in PSPACE. The mechanism is a three-part assembly. First, the Hrubes–Wigderson linearization of a rational formula is extended to circuits by unrolling, so that each gate's subcircuit becomes a formula of at most $2^s$ nodes and hence a pencil of dimension $2^{O(s)}$; the entry oracle (Lemma 4.9) computes any single entry of this pencil in workspace $O(s^2)$ without materializing the matrix. Second, a recent theorem — that deciding whether a homogeneous symbolic matrix has full noncommutative rank is in logspace-uniform $\mathrm{NC}^2$ — is used as a black box for the rank test. Third, the succinct-simulation theorem (Theorem 2.5 and Corollary 2.6) shows that a uniform $\mathrm{NC}^i$ procedure run against an input of length $2^{\Theta(s)}$ presented by a polylogspace bit oracle takes workspace $O(s^i)$. The zero criterion (Theorem 4.8) ties the value question on a correct formula $F$ to fullness of the wrapper pencil $L(F) = A_{F^{-1}}$: $\widehat F = 0$ if and only if $L(F)$ is not full, so identity testing becomes a rank test on a succinctly presented pencil. The main theorem (Theorem 6.2) states the decision procedure for correctness, returning an offending inversion gate when one exists, and for identity, and Remark 6.4 extends the statement to finite fields.
-
On its own terms the paper proves a three-way tradeoff: any covert task from a specific family must be paid for with model capacity, CoT length, or information-theoretic leakage $I[X_{\mathrm{covert}}, \mathrm{CoT}]$, where capacity and length enter only polylogarithmically and depth enters exponentially. Rearranging the bound shows that when the CoT is polynomially long, the mutual information between covert input and CoT is near-linear in the input length, giving three regimes: no CoT, agnostic CoT (uninformative, necessarily super-polynomial), and informative CoT (near-linear leakage). The paper also proves a covert-computation length tax: hiding a private task behind an unrelated public task costs extra CoT tokens unless the two inputs are correlated, in which case the correlation itself leaks information. Finally, assuming an NC0 pseudorandom generator, a one-layer Transformer can XOR its hidden trace with a short private seed, keeping the information-theoretic footprint but making it computationally intractable for any polynomial-time monitor to predict any property of the covert input.
-
The paper proves Theorem 1.1, that Almost-⊕P equals BP·⊕P, which in turn equals $BPP^{{⊕P}}$. Almost-⊕P collects the languages L for which L ∈ ⊕P^R holds with probability one when R is chosen by flipping each bit independently, while BP·⊕P is the bounded-error probabilistic class over ⊕P. The forward inclusion, Almost-⊕P ⊆ BP·⊕P, converts a ⊕P machine that is almost surely correct against a random oracle into one that is correct with probability 0.89 over a seed of polynomial length: by the degree lemma the machine is an $\mathbb{F}_2$-polynomial of degree at most T in the oracle bits, and the new generator fools all such polynomials with error 0.1. The reverse inclusion, BP·⊕P ⊆ Almost-⊕P, is a Borel-Cantelli argument: a BP·⊕P machine errs with probability summable over inputs, so relative to a random oracle it errs only finitely often and a finite table patches the remainder. The paper then combines Theorem 1.1 with the random-oracle collapse $\mathrm{PH}^R \subseteq \oplus\mathrm{P}^R$ (Theorem 5.1, credited to Regan and Royer) to obtain Corollary 6.1, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P} \subseteq \mathrm{P}^{\#\mathrm{P}}$, the first half of Toda's theorem, proved with no probabilistic quantifier ever moved through an oracle. The distinctive feature is the trade the author draws between this route and the elementary 2009 proof: here the collapse of the hierarchy becomes straightforward and all of the difficulty is concentrated in a single hardness-versus-randomness step.
-
The central claim is that a single Clifford–Pauli reachability relation, $U_T(e) P U_T(e)^\dagger = \pm P'$, exhibits a complexity landscape whose sharpest transition is governed by whether exponents are binary or unrestricted integers. For commuting templates with unrestricted integer exponents (Theorem 3), decision CTC lies in $\mathrm{NP}\cap\mathrm{BQP}$ for arbitrary template size, and search CTC is solvable in quantum polynomial time, returning a particular solution together with a basis of the full relation lattice; the proof promotes the target vector $b$ to an operator $C_b$ on the orbit span $W$, so that $b = F^e a$ holds exactly when $C_b = B^e$, converting the orbit-membership condition into constructive membership in the finite Abelian matrix group generated by the restricted symplectic maps. Restricting every exponent to $\{0,1\}$ removes that Abelian closure and makes decision CTC NP-complete for variable $k$ (Theorem 1), even for exactly commuting CNOT-only operations and X-type Paulis. A one-operation template already makes search CTC discrete-logarithm hard over $\mathbb{F}_{2^r}^{\times}$ (Corollary 1), and without commutativity decision CTC is NP-complete already at $k=3$ (Theorem 2). For commuting self-inverse actions, binary feasibility and recovery of one solution are classically polynomial-time, while imposing a bound on total repetition count is NP-complete (Theorems 4 and 5).
-
Under Hypothesis 1.2, that a single deterministic polynomial-time algorithm compares every SAT tuple of arity at least c0 λ(n)^d, the paper proves (1) UniqueCircuitSAT is decidable deterministically in time $2^{{O(λ(n)^d)}}$ and SAT lies in RTIME($2^{{O(λ(n)^d)}}$); (2) PH ⊆ BPTIME($2^{{O(λ(n)^{d^2}}$)}), with the exponent independent of the level of PH; (3) PH = S^NP_2 ⊆ S^p_2[$2^{{O(λ(n)^d)}}$], a symmetric verification with polynomial-length certificates and an oracle-free deterministic predicate of exponent d; and (4) the fixed unconditional diagonal language G belongs to BPTIME($2^{{O((λ(n) log λ(n))^{d^2}}$)}), yielding BPP ⊊ BPTIME($2^{{O(λ(n)^{d^2+ε}}$)}) for every fixed ε > 0 without advice. The randomized consequences come in two regimes: an inverse-polynomial relative saving below the uniform-guess error $2^{{-t}}$ transfers all conclusions except the uniform deterministic promise-unique solver and UEXP = EXP, while a saving of only $2^{{-O(λ(n)^d)}}$ retains randomized SAT exponent d and fixed-level PH exponent d^k. A layered oracle construction shows the randomized SAT exponent d is optimal among relativizing arguments, since relative to that oracle comparability holds, NP^A = coNP^A, yet NP^A needs time $2^{{δ λ(n)^d}}$.
-
The central claim is Theorem 3.1: the optimal contract problem with explicitly represented OXS rewards is APX-complete under PTAS reductions, and since every OXS function is gross substitutes, no PTAS exists for gross-substitutes rewards unless P = NP. The companion results map the landscape inside and outside this class: weighted matroid rank functions admit an EPTAS (Theorem 4.1) but no randomized FPTAS in general (Theorem 4.3), partition matroid rank functions admit an FPTAS (Theorem 4.5), and ultra rewards admit no $2^{{o(n)}}$-approximation in expectation using polynomially many value queries (Theorem 5.1). The paper also improves the constant-factor approximation for submodular rewards from 258 to 3.287 with value and demand oracles and to 6.128 with value oracles alone. The unifying message is that gross substitutes contains qualitatively distinct computational regimes, and moving beyond them to ultra rewards collapses approximability entirely.
-
The paper's central claims are three. First (Theorem 1), for every fixed break length x ≥ 2, deciding whether k machines suffice is NP-complete even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard; the reduction maps a restricted satisfiability form — each variable appears exactly three times, twice with one sign and once with the other — to 9p jobs arranged in variable, literal, and clause gadgets whose machines realize a truth assignment exactly when the safe pairings force a consistent sign. Second (Theorem 2), for x = 1 the problem is exactly solvable in O(n² log n) time: a machine has an idle gap of length one exactly when its jobs do not tile the horizon, so the only decisions are which touching jobs hand off on one machine, and a flow network with a binary search over the machine budget decides feasibility. Third (Theorem 3), for every x there is a deterministic polynomial-time algorithm returning at most OPT + 1 machines: jobs are labeled early or late, the minimum chain cover under that labeling is the machine count, an LP over the labels is solved and rounded through total unimodularity, perturbing every elementary-interval depth by less than one, which costs at most one extra machine. Corollary 1 states that this is best possible: unless P = NP no polynomial algorithm guarantees OPT machines for any fixed x ≥ 2.
-
On the paper's own terms, the core discovery is that binary membership comparability, where a comparator only rules out one of the four membership vectors of a pair, carries enough structure for exact polynomial-time verification with fixed linear advice. The proof builds an oriented graph on true signed literals, in which each excluded vector becomes a valid two-literal clause and two implication edges. A Chvátal–Lovász independent two-step cover takes the place of the tournament king used for selectors, and a dichotomy controls the remaining literals: either at most two unforced covering literals survive and are advised, or at least three of them predict every membership bit by exact majority. Verification then needs at most six comparator calls and witnesses of length $5n+12$, with the same $3n+5$-bit advice working for both $b=0$ and $b=1$, giving the common-advice containment $2\text{-}mc \subseteq \mathrm{NP}/(3n+5) \cap \mathrm{coNP}/(3n+5)$. For selectors the paper establishes tight $\Theta(n)$ average-case and $\Theta(n^2)$ worst-case ordinary-advice orders, the quadratic lower bound coming from a hidden-core distribution that is lifted to randomized procedures by amplification.
-
On the paper's own terms, the discovery is that the conjectured lower bound $\widetilde{\deg}(f\circ g) = \Omega(\widetilde{\deg}(f)\,\widetilde{\deg}(g))$ holds unconditionally for all total Boolean functions, so that together with the upper bound of [31], $\widetilde{\deg}(f\circ g) = \Theta(\widetilde{\deg}(f)\,\widetilde{\deg}(g))$. The proof takes an approximating polynomial $Q$ of degree $D$ for $f\circ g$ and a dual witness $\psi$ of the inner function $g$ — a signed weighting of inputs certifying $\widetilde{\deg}(g)$ — and builds a one-parameter family of probability measures $\rho_\theta$ whose value and derivative at $\theta = 0$ encode the conditional distributions of $g$ on its zero and one inputs. Averaging $Q$ over independently sampled blocks turns it into a trigonometric polynomial $R$ of total frequency at most $D$, and the squarefree extraction $S(R)(z/\kappa)$ recovers an approximation to $f$ on a cube scaled by $1/\kappa$, where $\kappa = 2\lambda$ and $\lambda = \|P_0 A P_1\| \in [d/3, d/2]$ is the coupling between zero and one inputs of an operator $A$ built from the dual witness. Since $\kappa = \Theta(\widetilde{\deg}(g))$, any $D$ below a constant multiple of $\widetilde{\deg}(f)\,\widetilde{\deg}(g)$ would allow the truncation step to output a polynomial of degree below $\widetilde{\deg}(f)$ that still approximates $f$ to error $1/3$, a contradiction.
-
The paper claims that diverse representation, when formalized through cohesive voter groups, is computationally demanding in general and tractable only under structure. It proves that the decision versions of the Semi-Strong JR and Strong JR maximization problems are NP-complete, that no polynomial-time algorithm approximates the optimal (S)SJR score within a ratio better than $1-1/e$ for committee size $k \in o(n)$ unless P=NP (Theorem 17), and that greedy selection attains exactly that ratio (Theorem 18). On the Candidate Interval domain, where each voter's approved candidates form an interval in a linear candidate order, exact maximization becomes polynomial via an equivalence to Interval Maximum Coverage (Theorem 20), and an FPT algorithm exists when a small candidate-deletion set is given. For the new Distinctive Representation axiom — a committee satisfying JR in which every elected candidate has exactly $\lceil n/k \rceil$ supporters — the paper proves the decision problem NP-hard via a reduction from Exact 3-Cover (Theorem 26), and shows the local-search variant Local DR is satisfiable in polynomial time.