Browse

Computational Complexity

cs.CC — Computational Complexity

cs.CC RSS feed

Works in cs.CC

54 works

cs.CC — Computational Complexity

An edge comparison with constant 3/2 and the coefficient 6/sqrt(2 pi) for the average sensitivity of polynomial threshold functions

Contributed by David Niedbala Giraudin

For every real polynomial threshold function f of degree at most d on the uniform cube {-1,1}^n we prove AS(f) <= min{n, 6 d b_n (n+d)/(n+2d)} <= (6/sqrt(2 pi)) d sqrt(n) < 2.394 d sqrt(n), where b_n = E|B_n - n/2| for B_n ~ Bin(n,1/2). The previous coefficient was 8/sqrt(2 pi) = 3.1915... The new ingredient is an edge comparison with constant 3/2 in place of 2 in OpenAI's weighted-grading argument: for every positive weight and every sign function h, the number of ordered equal-sign edges of h is at most (3/2)||MH+HM||_HS^2. The proof rests on the exact identity (Z_i M Z_i - M)^2 = I - A_i^2, where A_i is the grade-diagonal part of the multiplication by x_i. Combined with OpenAI's original coupling estimate alone, the lemma already gives AS(f) <= 6 d sqrt(n).

Primarily AI-generated textHuman understanding: no partsBoolean functionsaverage sensitivitycoupling inequalitypolynomial threshold functionstotal influenceweighted grading
Nov 15, 20264 pages
PDFView work

cs.CC — Computational Complexity

Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?

Contributed by Tejasvi Singh Tomar

Alman and Vassilevska Williams have refuted the 3SUM and APSP hypotheses. Their algorithms rest on counting the triangles through prescribed edges of lopsided tripartite graphs, whose middle part has nεn^{\varepsilon} vertices for a small ε\varepsilon. Majdoddin extended the method to every ε<ln⁡4/(5ln⁡5)≈0.172\varepsilon<\ln4/(5\ln5)\approx0.172. We determine which of the main conditional lower bounds derived from the refuted hypotheses survive. We also prove that the method extends to every ε<0.17843\varepsilon<0.17843 when the prescribed edges are known in advance and there are at most n2−ε/2n^{2-\varepsilon/2} of them, which confirms Majdoddin's numerical estimate. Whether a bound survives depends mostly on the instances that its reduction produces. The reductions behind most bounds produce instances outside the range of the new algorithms: balanced graphs, or lopsided graphs with a larger middle part. Most of the set-disjointness, dynamic-graph and triangle bounds therefore follow from hypotheses that no known algorithm contradicts. These hypotheses, however, concern mainly such instances, and for several bounds the hypothesis is the bound itself, stated for these instances. Their evidence came largely from the refuted hypotheses. A few bounds are false, among them a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness over small universes; the Strong SetDisjointness Conjecture also fails at small polynomial query times. Other bounds have lost their support, such as the Set Disjointness trade-offs of Kopelowitz, Pettie and Porat over small universes apart from constant query time. Finally, we collect the known obstacles to a larger closed-form range with a different base identity and use border-rank lower bounds to exclude several natural candidates.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716495

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202623 pages
PDFView work

math.RA — Rings and Algebras

Local optimality of rank-47 schemes for 4×4 matrix multiplication over F2

Contributed by Tejasvi Singh Tomar

The tensor ⟨4,4,4⟩\langle 4,4,4\rangle of 4×44\times4 matrix multiplication has rank at most 47 over F2\mathbb{F}_2, and as it is not known whether 47 is optimal, we ask how far the known decompositions of rank 47 are from one of rank 46. A decomposition is locally optimal to depth DD if no DD or fewer of its rank-one terms can be replaced by fewer rank-one terms. We prove that five pairwise inequivalent decompositions of rank 47 over F2\mathbb{F}_2 are locally optimal to depth 18, as is every decomposition equivalent to one of them, so a decomposition of rank 46 over F2\mathbb{F}_2 shares at most 28 terms with any decomposition in these five classes. The five classes include the scheme of Fawzi et al. and every public decomposition of rank 47 over F2\mathbb{F}_2 known to us; one of them, found in our flip-graph searches, is new. The proof rests on a peeling lemma and, for four sets of terms that resist the other bounds, on a refinement of the substitution method, which we call substitution over subspaces with lifting. Local optimality to depth 18 is also proved in Lean 4.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23721965

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202625 pages
PDFView work

cs.DS — Data Structures and Algorithms

Exact sizes of networks that select the three or four largest of n elements

Contributed by Tejasvi Singh Tomar

We study (t,n)(t,n)-selection networks, which move the tt largest of nn inputs to tt given lines in any order, and the least number U^t(n)\hat U_t(n) of comparators in such a network. Alekseev showed that U^t(n)≥(n−t)⌈lg⁡(t+1)⌉\hat U_t(n)\ge(n-t)\lceil\lg(t+1)\rceil. For t=2k≥4t=2^k\ge 4 we raise this bound by k−1k-1 for every n>tn>t, and by 2k−52k-5 when t≥32t\ge 32; as far as we know, these are the first improvements at powers of two. The proofs follow the weights of the lines, and a pruning step of Yao extends the gain to every t≥3t\ge 3. For t=3t=3, Yao's upper bound 2n−5+⌊lg⁡(n−3)⌋2n-5+\lfloor\lg(n-3)\rfloor is exact for 4≤n≤184\le n\le 18. For t=4t=4 the new bound is 3n−113n-11 for all n≥5n\ge 5, and the value 3n−103n-10 that Knuth expected is exact for 6≤n≤126\le n\le 12. Their lower bounds rest on exhaustive searches at a few sizes and on the fact that one more input costs at least two more comparators. Most of the results are also proved in Lean 4, some through compiled checks.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23801189

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202617 pages
PDFView work

math.RA — Rings and Algebras

The rank of 4×4 matrix multiplication over F2 is at least 35

Contributed by Tejasvi Singh Tomar

We prove that the rank of the 4×44\times4 matrix multiplication tensor over F2\mathbb{F}_2 is at least 3535; the previous lower bound was 3434. The bound follows by substitution from RF2(⟨3,3,4⟩)≥27\mathrm{R}_{\mathbb{F}_2}(\langle 3,3,4\rangle)\ge27, which also gives RF2(⟨3,4,4⟩)≥31\mathrm{R}_{\mathbb{F}_2}(\langle 3,4,4\rangle)\ge31. Each of the three bounds is one more than what follows from RF2(⟨3,3,3⟩)=23\mathrm{R}_{\mathbb{F}_2}(\langle 3,3,3\rangle)=23. A flattening argument reduces the bound for ⟨3,3,4⟩\langle 3,3,4\rangle to lower bounds for two quotients of the tensor, by the span of a matrix of rank two and by the span of a matrix of rank three. These come from exhaustive searches over the possible patterns of a short decomposition, pruned by lower bounds for quotients by larger subspaces. The whole argument, including every step of the searches, is checked in the proof assistant Lean 4, with one compiled evaluation of a verified certificate checker.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23749576

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202611 pages
PDFView work

quant-ph — Quantum Physics

Quantum-Information Probes of Collapse Dynamics in Causal Fermion Systems

Contributed by Benjamin Kaminsky

Finster, Kleiner, and Paganini derived from causal fermion systems (CFS) a nonrelativistic effective collapse model whose statistical operator obeys, to leading order, a Kossakowski--Lindblad equation. In the factorized regime of that derivation, the dissipator is built from purely spatial operators Nk,aN_{k,a} with positive rates fixed by microscopic time-nonlocal kernels. We translate this CFS-specific generator into quantities accessible to coherent quantum processors. The resulting CFS Dirichlet form obeys an exact purity-loss identity under arbitrary Hamiltonian control, and its null algebra is the commutant of the ∗*-algebra generated by the projected Nk,aN_{k,a}. For joint eigenbranches we obtain an exact distinguishability functional controlling exponential coherence loss and a lower bound on channel distance from ideal unitary evolution. In an nn-qubit dephasing sector, the projected kernels generate a positive-semidefinite covariance matrix CC, with GHZ visibility exp⁡[−2T1TC1]\exp[-2T\bm{1}^{\mathsf T}C\bm{1}]. We prove that uniformly summable finite-range correlations yield at most O(n)O(n) GHZ decay, whereas O(n2)O(n^2) scaling requires a collective non-summable component. Single- and two-qubit cat coherences reconstruct CC, giving a covariance-spectroscopy protocol, while Knill--Laflamme conditions characterize first-order correctability of the projected CFS error algebra. We also derive an explicit compatibility inequality between macroscopic state reduction and long coherent computation and show why absence of probe heating does not imply absence of coherence signatures. The results do not exclude CFS: its covariance strength, $\ellmin$, and hardware projection remain underdetermined. They instead identify the microscopic input required for a genuine no-go theorem and establish scalable quantum processors as direct probes of the CFS collapse sector.

Primarily AI-generated textHuman understanding: some partscausal fermion systemsdecoherencefault toleranceobjective collapsequantum compting
Nov 12, 202616 pages
PDFView work

math.IT — Information Theory

Energy complexity and dissipation of noisy consensus

Contributed by Zhenyu Sun

We characterize the signal-energy complexity of distributed agreement over independent Gaussian point-to-point channels. For nn processes deciding LL binary coordinates under coordinatewise unanimity validity and a joint failure probability of at most ε\varepsilon, every finite causal protocol requires a worst-input expected signal energy of Ω(N0n[L+ln⁡(n/ε)])\Omega(N_0n[L+\ln(n/\varepsilon)]). This lower bound combines two distinct mechanisms: an exact relative-entropy identity for locally interchanged reception histories yields the reliability term even in the presence of shared randomness and active noisy feedback, while a coordinatewise direct-sum argument establishes the payload term. In the fault-free setting, a deterministic fixed-leader protocol attains this optimal order for all 0<ε≤1/80<\varepsilon\leq1/8. In the presence of f≤(1/3−κ)nf\leq(1/3-\kappa)n static Byzantine faults, the same order is achieved in the polynomial-error regime ε≥n−a\varepsilon\geq n^{-a} via public committee sampling and robust joint decoding within explicit finite storage and computation budgets. Consequently, batching amortizes the reliability overhead, yielding an energy cost of Θ(N0n[1+L−1ln⁡(n/ε)])\Theta(N_0n[1+L^{-1}\ln(n/\varepsilon)]) per coordinate. We then connect this communication optimum to physical dissipation through a stochastic-thermodynamic model of a thermal channel port. Under a non-recovering mode replacement interface, the communication converse translates directly into lower bounds on entropy production and, when the endpoint mean internal energies agree, cyclic work. When work recovery is permitted prior to mode reset, we derive the exact minimum reset entropy production within a bounded-displacement control class as a function of the information accessible to the recovery controller, thereby separating the fundamental communication cost from its control-dependent thermodynamic realization.

Primarily human-written textHuman understanding: all partsByzantine agreementGaussian channelsconsensusenergy complexityentropy production
Nov 11, 202624 pages
PDFView work

cs.CC — Computational Complexity

Non-computable derivatives of the fractional-part autocorrelation

Contributed by Michael Yampolsky

We describe a natural new example of non-computability in analysis. Namely, the multiplicative autocorrelation of the fractional-part function, \[ A(x)=\int_0^\infty \{t\}\{xt\}\,\frac{dt}{t^2}, \] is computable and differentiable almost everywhere, but its finite derivative can be non-computable even for a computable xx. We derive these results from an adaptation of our earlier work on computability of Brjuno-like functions.

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 10, 202611 pages
PDFView work

math.LO — Logic

The Logical Anatomy of Optimization: Reverse Mathematics, Proof Mining, and the Price of Convergence

Contributed by Xiaoyu Li

Optimization theory proves three kinds of theorems: that optimal points exist, that algorithms converge to them, and that optimality can be certified by duality. We measure how much mathematics each kind needs, using reverse mathematics, Weihrauch complexity and proof mining, and assemble the answers, old and new, into one map stated in the language of optimization. Compactness makes existence cost weak Kőnig's lemma, but convexity (and, format by format, tameness) makes it cheap: we show that RCA0\mathsf{RCA}_0 proves that convex functions on [0,1][0,1] attain their minima (and on [0,1]n[0,1]^n, for each fixed nn, given a modulus of uniform continuity), and that RCA0\mathsf{RCA}_0 proves linear programming duality and the minimax theorem for real data of every size. Convergence costs more: it follows from results of Kohlenbach and Neumann that convergence of gradient descent for convex smooth functions on R\mathbb{R} is equivalent to ACA0\mathsf{ACA}_0. We explain this by a selection principle: what costs is the particular minimizer the algorithm selects, and uniqueness or an error bound removes the cost. Below convergence lies finitary information. Gradient descent in Rd\mathbb{R}^d has at most 2CdD/ε2C_dD/\varepsilon fluctuations of size ε\varepsilon, with CdC_d depending only on dd, which yields rates of metastability; no such bound is dimension-free, by the span-restriction argument behind performance estimation; and the limits of gradient descent on computable instances have d.c.e. coordinates, a proper subclass of the limit-computable reals. The map also covers Ekeland's variational principle (up to Π11-CA0\Pi^1_1\text{-}\mathsf{CA}_0), separation theorems, Kőnig duality (ATR0\mathsf{ATR}_0), proof-mined rates for fixed-point iterations, and the feasible world, where local search captures the NP\mathsf{NP} search problems provably total in T21T^1_2 and approximate stationary points of smooth functions are complete for CLS=PPAD∩PLS\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}. We close with five principles and open problems.

Primarily AI-generated textHuman understanding: some partsTFNPWeihrauch complexitybounded arithmeticconvex optimizationgradient descentlinear programming dualitymetastabilityminimax theoremproof miningreverse mathematics
Nov 10, 202646 pages
PDFView work

cs.LO — Logic in Computer Science

Formalizing the interpolation lemma of the openai/math Landau–Siegel paper and substituting it into a Comparator-accepted proof

Contributed by Joseph Reilly

OpenAI’s openai/math release includes a Lean formalization of “Uniform exclusion of Landau–Siegel zeros” (OpenAI, October 1, 2026). Its Comparator challenge has two checked theorems, whose statements we prove equivalent in Lean. OpenAI proves them by two routes, neither through the paper’s proof of Lemma 3. The catalogued main result, exists_absolute_real_zero_gap, gets its spanning step from a local Bézout argument and does not use OpenAI’s Corollary 4 theorem. The second theorem, dirichletRealZeroBound_proof, proves Corollary 4 by a multiplicity estimate. We formalized the paper’s proofs of Lemma 3 and Corollary 4 in Lean. By reading, the Lean statements match the paper’s, and the declarations use only the axioms propext, Classical.choice and Quot.sound. A +2/-1 substitution puts the paper’s Corollary 4 into dirichletRealZeroBound_proof. Comparator accepts the result with both kernels at openai/math fd4aeeb under a deny list of all 45 socket address families, and that theorem’s closure no longer contains the three named OpenAI lemmas. Our replay of the corpus agrees with an independent replay on all 402 configurations where both have a verdict.

Primarily AI-generated textHuman understanding: some parts
Nov 10, 202620 pages
PDFView work

math.CO — Combinatorics

Complexity of Mutation-Acyclicity and Matrix Mutation Equivalence

Contributed by Qiyue Tang

Mutation-acyclicity of integral skew-symmetrizable matrices belongs to NP. Mutation equivalence belongs to promise-NP when at least one input is mutation-acyclic. For pairs of mutation-cyclic matrices, mutation equivalence is RE-complete and strongly NP-hard. Both results hold even for connected skew-symmetric matrices.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

A mix of human-written and AI-generated textHuman understanding: some parts
Nov 07, 202635 pages
PDFView work

cs.DS — Data Structures and Algorithms

A certified exponent of 0.48758 for worst-case Subset Sum, and limits of the alias–checksum analysis

Contributed by Jennifer Voitle

For more than fifty years, since Horowitz and Sahni's meet-in-the-middle algorithm of 1974, the best exponent for worst-case Subset Sum was 1/21/2. In October 2026 that barrier fell twice within a week, with OpenAI's 20.49n2^{0.49n} algorithm and, independently, Li and Ye's 2(1/2−1/450000)n≈20.4999978n2^{(1/2 - 1/450000)n} \approx 2^{0.4999978n}, and improvements have followed quickly since: within three weeks A. Kapila's modification of the OpenAI approach ("Base") reached 0.4877, a retuning of Base by JoshuaQFEX reached 0.487676, and a refinement by Y. Bills reached 0.4876723. Here we push this line of work further and examine what limits it. Conditional on the cited non-numerical proofs, we give a certified parameter point with threshold T=0.4875754036T=0.4875754036: for every fixed T′>TT'>T, the uniform randomized algorithm uses O(2T′n)O(2^{T'n}) word operations on inputs of polynomial bit length, with success probability at least 2/32/3. In particular, it runs in time O(20.4875755n)O(2^{0.4875755n}). A single asymmetric filter replaces Base's family of 43 filters. Independent interval computations certify all required numerical conditions, including both filtering moments and their quadrature errors. We prove a lower bound on the first filtering moment, valid for all positive continuous densities, that excludes every parameter choice with τ≤0.484\tau\le0.484 in the original OpenAI proof's sufficient budget. Three algebraic bounds explain the costs at our improved point. Separately, an enumeration phase that inserts at least 2(1−η−o(1))n2^{(1-\eta-o(1))n} alias classes, spending a counted step on each, and uses checksum gap at most Δ\Delta needs exponent at least (1−Δ)/2(1-\Delta)/2. This is a conditional operation-count bound; a global upper bound on achievable checksum capacity remains open. Finally, we isolate a small-layer statement that would yield threshold 0.48734075280.4873407528, prove combinatorial special cases, and identify the remaining questions.

Author comments: 30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.

A mix of human-written and AI-generated textHuman understanding: some partsAI-assisted mathematicsFourier filteringSubset Sumcomputer-assisted proofexact algorithmsinterval arithmeticmeet-in-the-middlerepresentation techniqueworst-case complexity
Nov 07, 202630 pages
PDFView work

math.CO — Combinatorics

Undecidability of Quiver Mutation Equivalence

Contributed by Qiyue Tang

We prove that quiver mutation equivalence up to relabeling is undecidable even for one fixed source quiver. We also prove strong NP-hardness.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

A mix of human-written and AI-generated textHuman understanding: some parts
Nov 06, 202615 pages
PDFView work

cs.CC — Computational Complexity

What the ETH refutations do not give: barriers for the counting engines, with machine-checked lemmas

Contributed by Vaibhav Tulsyan

In October 2026 OpenAI and Anthropic each claimed a deterministic subexponential algorithm for counting the solutions of a kk-CNF; both counting engines sum products of local tables. For SAT itself, Majdoddin bounds the rate of Anthropic's grid recursions with product terms, and Dias and Lima bound OpenAI's clause-product scheme. However, Majdoddin notes that no barrier is known for decompositions whose terms are not products, and neither paper treats the counting problems beyond SAT. We introduce the engine barrier problem: bound from below the shared bits UU of every network of a stated class that computes a given count, and the rate of every recursion of a stated class. Our approach puts a rank on every cut of a local network, and on one contraction inside both flattenings of a term. Machine-checked in Lean are: correlated (non-product) decompositions of two rectangles, of the 3×23\times2 grid and of the full 3×33\times3 grid level have flattening-rank sums at least N2N^2, N3N^3 and N8N^8, while N9N^9 is open; the row cut of the permanent has rank (nk)\binom nk, which on paper gives U≥nlog⁡2(n/s)U\ge n\log_2(n/s) for row-local networks; algebras in which the permanent is a functional of a product have dimension at least (nn/2)\binom n{n/2}; pieces have saving ρ≥1/2\rho\ge1/2 (rank form; Anthropic's observation); and exact colouring filters for Hamiltonicity need q≥n−4q\ge n-4 colours. On paper we prove U≥(1−o(1))nlog⁡2nU\ge(1-o(1))n\log_2n for vertex-local networks for the Tutte polynomial off the integer hyperbolas, and ρ≥3/8\rho\ge3/8 for correlated decompositions of full grid levels. We cite 4545 Lean theorems, with standard axioms only. Every barrier is about a named model: in Anthropic's general model no unconditional bound on UU exists without separating P\mathrm P from P#P\mathrm P^{\#\mathrm P}, and an unconditional cap on oblivious algebraic algorithms would separate VP\mathrm{VP} from VNP\mathrm{VNP}.

Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisSATTutte polynomialcorrelated decompositionscut rankengine barrier problemtensor networks
Nov 06, 202624 pages
PDFView work

cs.CC — Computational Complexity

The Price of Bayes-Optimal In-Context Learning

Contributed by Xiaoyu Li

In-context learning is often explained as implicit Bayesian inference: given labeled examples of a task drawn from a prior, the learner predicts like the posterior. We determine the computational price of this explanation for task families whose labels depend on few bits of the task description, such as quantized models on sparse data, and we compare it with the price of merely learning. The comparison uses the recent refutations of the Exponential Time Hypothesis by OpenAI and Anthropic. Bayesian inference in context is counting. For κ\kappa-local task families with NN-bit descriptions under the uniform prior, the posterior predictive and posterior sampling reduce to #κ\#\kappa-SAT. Without label noise they run in time poly(m)⋅2o(N)\mathrm{poly}(m)\cdot 2^{o(N)} on contexts of every length mm when κ=o((log⁡N)1/4/log⁡log⁡N)\kappa=o((\log N)^{1/4}/\sqrt{\log\log N}), and label noise is handled by error profiles. A two-variable gadget gives contexts that are always consistent and whose posterior predictive is 2#F/(2#F+1)2\#F/(2\#F+1) for a CNF FF. So approximating the posterior predictive within 1/41/4 needs time 2(1−γ)N2^{(1-\gamma)N} at locality O(log⁡N)O(\log N) under CNF-SETH, and time 2N/polylog N2^{N/\mathrm{polylog}\,N} at locality 33 under a length form of ETH. At constant locality, Bayesian inference in context is SAT parameterized by formula length. Learning in context is cheap. The Bayes risk of any class with NN-bit descriptions is at most N/(m+1)N/(m+1) after mm examples. For binarized perceptrons and literal disjunctions on sparse data, the very families of the lower bounds, a linear program is a polynomial-time in-context learner with essentially the same sample efficiency. Every κ\kappa-local family is linear over ∑j≤κ(Nj)\sum_{j\le\kappa}\binom{N}{j} local Fourier features, so regression in context learns it from NO(κ)N^{O(\kappa)} examples, in time polynomial in NκN^\kappa and the inverse accuracy. The average case. For Goldreich's random local functions, the Bayes risk is at most N/(m+1)N/(m+1), while every in-context learner yields a distinguisher for Goldreich's generator, with the same running time up to a linear term, whose advantage is 1/21/2 minus the risk. Under a local pseudorandom generator hypothesis with polynomial stretch, polynomial-time in-context learners need polynomially more examples than the Bayes predictor. Under its length form at linear stretch, which the new algorithms refute below rate 1/21/2, the Bayes predictor of the refutations is optimal up to polylogarithmic factors in the exponent. For transformers, these bounds limit the length of a chain of thought that computes the posterior predictive, and they separate Bayes-optimal in-context learning from the regression-type in-context learning that transformers are known to implement.

Primarily AI-generated textHuman understanding: some partsBayesian inferenceCNF-SETHExponential Time HypothesisGoldreich's generatorfine-grained complexityin-context learninglocal pseudorandom generatorsmodel countingposterior predictivetransformers
Nov 06, 202637 pages
PDFView work

cs.CC — Computational Complexity

Fast Attention after SETH: The Exact Exponent and the Hypotheses Behind It

Contributed by Xiaoyu Li

Alman and Song showed that attention with head dimension O(log⁡n)O(\log n) can be approximated in almost linear time when the entries are o(log⁡n)o(\sqrt{\log n}), and needs quadratic time at Θ(log⁡n)\Theta(\sqrt{\log n}) under the Strong Exponential Time Hypothesis. In October 2026 the Exponential Time Hypothesis was refuted, and with it SETH. The quadratic lower bound now rests on the hardness of Orthogonal Vectors in dimension clog⁡nc\log n (LDOV), which no open hypothesis about satisfiability is known to imply. We measure an instance by its spread WW, the largest gap between two logits of a row. At every nontrivial constant precision and in every dimension between ω(log⁡n)\omega(\log n) and no(1)n^{o(1)}, we show that under LDOV the time exponent of attention is exactly 1+min⁡{W/ln⁡n,1}1+\min\{W/\ln n,1\}: uniform sampling of keys is optimal, the cost is min⁡{n eW,n2}\min\{n\,e^{W},n^2\} up to factors no(1)n^{o(1)}, and the transition to quadratic time sits at W=ln⁡nW=\ln n, the spread at which one key can outweigh all others. At polynomial precision and in dimension O(log⁡n)O(\log n) the threshold becomes Θ(log⁡n)\Theta(\log n), with a constant that tends to zero as the precision grows, and the dimension moves it: at precision n−1−O(1/log⁡log⁡n)n^{-1-O(1/\log\log n)}, spread O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) is hard in dimension (log⁡n)1+Ω(1)(\log n)^{1+\Omega(1)} but easy in dimension O(log⁡n)O(\log n). From satisfiability we obtain hardness at spread (1+θ)ln⁡n(1+\theta)\ln n in dimension no(1)n^{o(1)}, provided the hard CNF formulas have Nc0N^{c_0} clauses for some c0<2c_0<2, and we show that the construction behind this bound, which builds one instance for each proof of a Merlin–Arthur protocol for disjointness, needs c0<2c_0<2 for every such protocol. For the entry bound, every reduction that embeds Orthogonal Vectors vector by vector, with polynomial blowup and logit gap Ω(log⁡n)\Omega(\log n), yields a Merlin–Arthur protocol for disjointness; by Klauck's lower bound, such reductions cannot derive B=Θ(log⁡n)B=\Theta(\sqrt{\log n}) from Orthogonal Vectors in dimension (log⁡n)1+Ω(1)(\log n)^{1+\Omega(1)}. We also map the conditional lower bounds for attention in the literature to the hypotheses that now support them, and find two families whose hypotheses are false, one of them in part of its parameter range.

Primarily AI-generated textHuman understanding: some partsCNF-SETHMerlin-Arthur protocolsOrthogonal VectorsStrong Exponential Time Hypothesisattentioncommunication complexityfine-grained complexitypolynomial methodsoftmaxtransformers
Nov 06, 202643 pages
PDFView work

math.NT — Number Theory

The parity of the prime-counting function in time xo(1)x^{o(1)}

Contributed by Vaibhav Tulsyan

Computing the prime-counting function π(x)\pi(x) exactly takes x1/2+o(1)x^{1/2+o(1)} steps by the analytic method of Lagarias and Odlyzko, and to our knowledge its parity is known faster only on short intervals: Tao, Croot and Helfgott decide whether an interval of length at most x1/2+cx^{1/2+c} near xx contains an odd number of primes in time x1/2−c+o(1)x^{1/2-c+o(1)}. However, their identity needs the Mobius function μ(d)\mu(d) for all d≤xd\le\sqrt x, and we know of no bound of the form xo(1)x^{o(1)} for the parity, even conditionally. We present deterministic algorithms that output π(x) mod 2\pi(x) \bmod 2 and the parity of the number of primes in any interval [A,B][A,B] in time 2O(n/log⁡n)=xo(1)2^{O(n/\sqrt{\log n})}=x^{o(1)}, where nn is the input bit length. Our approach replaces μ(d)\mu(d) by its residue modulo 2, which is the squarefree indicator again: the number of chains d12∣md_1^2\mid m, d22∣d1,…d_2^2\mid d_1,\dots of depth LL is odd exactly when mm is squarefree, for m<22Lm<2^{2^L}. The parity of π\pi on [A,B][A,B] is then the parity of one count of tuples satisfying O(log⁡n)O(\log n) multiplications, which Anthropic's counting engine evaluates through a network whose variables have geometrically shrinking widths. We prove both theorems in Lean 4 (piParity_TM_rate, piIntervalParity_TM_rate; axioms propext, Classical.choice, Quot.sound). The result does not give deterministic prime finding or the exact value of π(x)\pi(x): the parity can be even on every interval one queries, and exact counts seem to need iterated products, for whose product-tree verifiers we prove a lower bound in Lean. The constants are astronomical, and the result rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review.

Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisMobius functiondeterministic prime findingdivisor chainsparity of pi(x)prime-counting functionsquarefree numbers
Nov 05, 20269 pages
PDFView work

math.NT — Number Theory

Class numbers, square roots and quadratic non-residues in time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

Basic counting problems of computational number theory have proven deterministic bounds that are fixed powers of the input. The class number h(D)h(D) of an imaginary quadratic discriminant takes ∣D∣1/2+o(1)|D|^{1/2+o(1)} steps unconditionally and ∣D∣1/5+o(1)|D|^{1/5+o(1)} under the generalised Riemann hypothesis (GRH); exact divisor sums ∑m≤xτ(m)\sum_{m\le x}\tau(m) take x1/3+o(1)x^{1/3+o(1)}. However, none of these bounds is of the form Xo(1)X^{o(1)}, even conditionally. We present deterministic algorithms in time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}, where nn is the input bit length, for the number of reduced forms of discriminant −N-N (for fundamental discriminants, h(−N)h(-N)) and for ∑m≤xτ(m)\sum_{m\le x}\tau(m), ∑m≤xσ(m)\sum_{m\le x}\sigma(m) and the Gauss circle count. Our approach writes each answer as a count of solutions of equations with one or two products and evaluates it with Anthropic's counting engine through one network library with O(n)O(n) shared bits. The same library gives the least square root modulo any mm and the least quadratic non-residue modulo a prime. These are not new bounds (OpenAI's results on the quasi-Riemann hypothesis and on deterministic polynomial factorisation over Fp\mathbb{F}_p give polynomial time modulo a prime), but they are machine-checked. We prove the seven resulting theorems in Lean 4 (for example hForm_TM_rate; axioms propext, Classical.choice, Quot.sound): a finite-alphabet Mathlib Turing machine outputs the answer within ⌊C⋅2Cn/log⁡2(n+2)⌋\lfloor C\cdot2^{Cn/\sqrt{\log_2(n+2)}}\rfloor steps on every input. Lean proves the count of Gauss's reduced forms; its equality with the ideal class number is classical and not formalised. The constants are astronomical, the machines use exponential space, and every result rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review. Version 2 corrects the claims of version 1 about non-residues and square roots.

Primarily AI-generated textHuman understanding: some parts
Nov 05, 202612 pages
PDFView work

quant-ph — Quantum Physics

Exact amplitudes of sparse quantum circuits in subexponential time, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

Classical simulation lower bounds for quantum circuits have been derived from the Exponential Time Hypothesis (ETH). However, in October 2026 OpenAI and Anthropic claimed deterministic subexponential algorithms for #k-SAT, refuting ETH, and neither manuscript mentions quantum circuits. We record the corollary. Assuming three internal results of the Anthropic manuscript, one deterministic Turing machine computes the amplitude ⟨y∣C∣x⟩\langle y|C|x\rangle of a Clifford+T circuit with GG two-qubit gates in arbitrary connectivity exactly, as an element of Z[ω]/2 k\mathbb{Z}[\omega]/\sqrt2^{\,k} with ω=eiπ/4\omega=e^{i\pi/4}, in time 2O(G/log⁡G)2^{O(G/\sqrt{\log G})} whenever the input length LL satisfies log⁡L≤G0.9\log L\le G^{0.9}. The proof reads the sum over paths, one bit per wire segment, as an Anthropic-type network, with a Kronecker map for Z[ω]\mathbb{Z}[\omega] and a Galois bound. We machine-check this theorem in Lean 4 (amplitude_TM_rate', amplitude_TM_rate, amplitude_TM; axioms propext, Classical.choice, Quot.sound) on top of Anthropic's Lean development (sources at https://github.com/xennygrimmato/eth-hamiltonicity). On paper only, the method gives exact marginals and exact sampling, depth-dd circuits in 2O(dn/log⁡n)2^{O(dn/\sqrt{\log n})}, and, through OpenAI's tensor-contraction theorem, polynomial space when the number of Hadamard-type gates is O(G)O(G). Conversely, constant-depth circuits with O(n)O(n) gates encode #3-SAT with O(n)O(n) clauses, so the rate matches that of the refutations. We check the fine-grained supremacy conjectures we found against their sources; a counting form of the Calabro-Impagliazzo-Paturi width reduction refutes the gap conjecture of Morimae and Tamaki's depth-scaling paper. Dense statements (cubic phases, permanents, random circuits) survive. Nothing here concerns approximate sampling, the constants are galactic, and everything is conditional on the claimed refutations, which are under review.

Primarily AI-generated textHuman understanding: some partsClifford+Tfine-grained complexityquantum circuit simulationquantum supremacystrong simulationtensor networks
Nov 04, 202615 pages
PDFView work

cs.DS — Data Structures and Algorithms

Counting Eulerian circuits in subexponential time, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

Counting the Eulerian circuits of an undirected graph is #P-complete, even for planar 4-regular graphs, while for directed graphs the BEST theorem counts them in polynomial time. However, we are unaware of any exact algorithm for undirected graphs of bounded degree that runs in time 2o(m)2^{o(m)}, where mm is the number of edges. We show that such an algorithm follows from the exact counting of Hamiltonian cycles that we proved earlier on top of Anthropic's claimed #SAT algorithm. The reduction is classical: by Kotzig's description, the Eulerian circuits of GG are in bijection with the Hamiltonian cycles of the line graph of the double subdivision of GG, which has 3m3m vertices and at most (Δ+1)m(\Delta+1)m edges. We prove in Lean 4 (theoremEuler, theoremEuler_noIso, theoremEuler_rate; axioms propext, Classical.choice, Quot.sound) that for every δ>0\delta>0 and Δ\Delta a finite-alphabet Mathlib Turing machine outputs the number of Eulerian circuits of every graph of maximum degree at most Δ\Delta within ⌊C(n+2)C2δm⌋\lfloor C(n+2)^C 2^{\delta m}\rfloor steps, and within ⌊C2δm⌋\lfloor C 2^{\delta m}\rfloor steps when there is no isolated vertex; and that one machine does so for all graphs within ⌊C(n+2)C2Cmlog⁡2(Δ+2)/log⁡2(m+2)⌋\lfloor C(n+2)^C 2^{Cm\log_2(\Delta+2)/\sqrt{\log_2(m+2)}}\rfloor steps. The factor (n+2)C(n+2)^C pays for reading the n2n^2-bit adjacency matrix and cannot be dropped. The bijection is checked by brute force on twelve small graphs, for example 132 circuits for K5K_5. The formal object is Kotzig's transition-system definition; its agreement with Mathlib's Eulerian walks is not formalised. The constants are astronomical, and the proof rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review.

Primarily AI-generated textHuman understanding: some parts#P-completenessEuler toursEulerian CircuitsHamiltonian cycleexact countingline graph
Nov 04, 20268 pages
PDFView work

cs.CC — Computational Complexity

Class Numbers of Imaginary Quadratic Orders in the Polynomial Hierarchy

Contributed by Frank Vega

For d≥3d \geq 3 with −d≡0,1(mod4)-d \equiv 0, 1 \pmod 4, let h(−d)h(-d) be the number of classes of primitive positive definite binary quadratic forms of discriminant −d-d. We prove that d↦h(−d)d \mapsto h(-d) is computable in deterministic polynomial time with an oracle for a language in the second level Σ2P\Sigma_2^{\text{P}} of the polynomial hierarchy. The proof uses only reduction theory of binary quadratic forms, Lagrange's theorem and Hermite normal forms; it does not assume the generalized Riemann hypothesis, does not take a generating set of the class group as input, and uses no randomness. A Σ2P\Sigma_2^{\text{P}} oracle finds a generating set of O(log⁡d)O(\log d) forms, and an NP oracle then determines the lattice of relations, whose index is h(−d)h(-d). Consequently, if P=NP\text{P} = \text{NP}, class numbers of imaginary quadratic fields are computable in polynomial time. As an application, the number DnD_n of representations of nn by the ternary form 8x2+2y2+16z28x^2 + 2y^2 + 16z^2 in Tunnell's congruent number criterion equals 2h(−4n)2h(-4n) for square-free n≡2(mod8)n \equiv 2 \pmod 8 and vanishes for square-free n≡6(mod8)n \equiv 6 \pmod 8; hence DnD_n lies in FPΣ2P\text{FP}^{\Sigma_2^{\text{P}}} on even square-free nn, and an exact counting reduction from #SAT\#\text{SAT} to DnD_n would collapse the polynomial hierarchy to Δ3P\Delta_3^{\text{P}}.

Author comments: In this new version, we have added a computer-based numerical verification.

Primarily AI-generated textHuman understanding: all partsHermite normal formTunnell's theorembinary quadratic formsblack-box groupsclass numberscongruent numberscounting complexitypolynomial hierarchy
Nov 04, 20269 pages
PDFView work

math.NT — Number Theory

Arcs of Π(1+z^p): prime races, the Gaussian core, Dirichlet L-functions and a certified solver for Subset Sum

Contributed by Antonio Mennillo

The subsets of {1}∪{p≤N}\{1\} \cup \{p \le N\} reach every integer between 0 and their total, by Bertrand's postulate, so deciding whether a target is a subset sum of the primes is trivial. Counting the solutions is not: the count carries the arithmetic of the primes. We study the generating function FN(z)=Π(1+zw)F_N(z) = \Pi(1 + z^w) on the unit circle and follow one object, the arc at a rational a/qa/q, through three settings. For the primes, the centre of the arc a/qa/q rises above the sea of the minor arcs exactly when q=2k(k≥2)q = 2^k (k \ge 2) or q=2pjq = 2p^j, with excess Λ(q/2)/φ(q)\Lambda(q/2)/\varphi(q), and the neighbourhoods of all the other arcs are bounded uniformly in qq; Theorem E gives the expansion arc by arc. The height of an arc is a race of the primes modulo qq with weights log⁡∣cos⁡(πra/q)∣\log |\cos (\pi ra/q)|. By Landau's theorem a one-sided bound on it is equivalent to GRH for the even characters it sees, unconditionally at q=8q = 8, 10 and 14, where the zero-free segments it needs are certified; at q=14q = 14 the race changes sign infinitely often. The principal arc carries ζ\zeta in the centre and width of its Gaussian. For arbitrary weights, the arcs become the decision rule of a Subset Sum solver that reads them on the original weights and ends with a meet-in-the-middle filtered by a random residue class. Every answer it returns is verified. The dummy weights of HURS explain why the reading is exact: they blur the counts by a flat window, and the blur is invertible on counts, though not on reachable sets. On random weights of bb bits the method has rigorous guarantees, in time 2b/2+o(b)2^{b/2+o(b)} and, with the filter, 2b/3+o(b)2^{b/3+o(b)}, resting on a local limit theorem uniform in the size of the weights and on a concentration bound for signed subset sums. Finally, the solver is read inside a general theory of constraint propagation, in which every network factors as T=Tcomp∘TstructT = T_{\mathrm{comp}} \circ T_{\mathrm{struct}}.

A mix of human-written and AI-generated textHuman understanding: some partsDirichlet L-functionsGRHSubset Sumcircle methodconstraint propagationlocal limit theoremmeet-in-the-middleprime races
Nov 04, 202662 pages
PDFView work

cs.DS — Data Structures and Algorithms

Ulam Metric kk-Center in Parameterized Linear Time

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

Continuous Ulam Metric kk-Center asks for at most kk permutations whose radius-dd balls cover the input rankings. For mm rankings of nn symbols, a deterministic algorithm takes 2O(kdlog⁡(k+d+2))mn2^{O(kd\log(k+d+2))}mn word operations. Permanent reference rankings, short insertion lists, and small obstructions obtained by patience sorting control the search. For one center, this answers a question of Bai, Fomin, Golovach, More, and Wietheger with linear input dependence. An arbitrary-alphabet Hamming embedding with a nonexpansive retraction also gives the matching 2o(dlog⁡d)2^{o(d\log d)} exclusion under the Exponential Time Hypothesis.

Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisUlam distancecontinuous k-centerparameterized algorithmspatience sortingrank aggregation
Nov 04, 20269 pages
PDFView work

cs.DS — Data Structures and Algorithms

The Exact One-Half Threshold for Arbitrary-Capacity Bottleneck Multiple Subset Sum

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

In bottleneck multiple subset sum, items with weights are packed into knapsacks with capacities, possibly leaving items unpacked, so as to maximize the minimum load. For identical capacities the best possible approximation ratio is 2/32/3, and Chen et al.\ asked whether 2/32/3 is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a 1/21/2-approximation using O(nlog⁡(n+1)+mlog⁡(m+1))O(n\log(n+1)+m\log(m+1)) arithmetic and comparison operations for nn items and mm knapsacks, and prove that no fixed ratio above 1/21/2 is achievable unless P=NP\mathsf P=\mathsf{NP}. We also give a short proof of the classical 1/21/2 guarantee of Friesen and Langston for unit profits.

Primarily AI-generated textHuman understanding: some partsapproximation thresholdbipartite matchingbottleneck multiple subset sumknapsacknumerical matching
Nov 04, 20269 pages
PDFView work

cs.CC — Computational Complexity

Universal-Clique Amplification and Hardness of Assignment-Optimal Edge Clique Covers

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

An edge clique cover has assignment cost equal to the sum of its clique sizes. Unless P=NPP=NP, this cost admits no polynomial-time O(N1/2−η)O(N^{1/2-\eta})-approximation for any fixed 0<η<1/20<\eta<1/2, even on connected NN-vertex graphs. A universal-clique join transfers coloring hardness without the additive obstruction in earlier reductions. Its exact residual formula also exhibits a change of optimal cover when a universal twin is added. Explicit counterexamples refute two proposed twin-extension rules, while weighted compression of true-twin classes preserves the optimum.

Primarily AI-generated textHuman understanding: some partsGraph coloringassignment costedge clique coverhardness of approximationtwin reductionsuniversal-clique joinweighted clique covers
Nov 04, 202612 pages
PDFView work

cs.CC — Computational Complexity

The Siriaisa Algorithm for Minimum Independent Dominating Set

Contributed by Frank Vega

The Minimum Independent Dominating Set problem asks for a smallest maximal independent set of a graph. Unless P=NP\mathrm{P}=\mathrm{NP} it is not approximable within n1−εn^{1-\varepsilon} for any ε>0\varepsilon>0; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within δB\delta B on bipartite graphs of maximum degree BB. We present version 0.0.9 of \textsc{Siriaisa}, an ensemble of eighteen strategies that adapts the vertex cover algorithm \textsc{Salvador} and the independent set algorithm \textsc{Esperanza} to independent domination: its exact subproblems are forests, solved by a conditioned tree dynamic program, in place of the bipartite structures of \textsc{Salvador}; one base strategy splits every vertex of degree larger than ⌊n⌋\lfloor\sqrt n\rfloor into unconnected copies; and the improvers include a weighted swap search. We prove that the output is an independent dominating set computed in O(n+m)O(n+m) expected time, with ratio at most Δ\Delta, optimal on forests, and with ratio at most n\sqrt n on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most ⌊n⌋ (i(G)+s(G))\lfloor\sqrt n\rfloor\,(i(G)+s(G)) on every graph, for an explicit splitting excess s(G)s(G), and the output satisfies the same bound when the decoded set is independent. The excess is at most n(n+1)n(\sqrt n+1), largest on complete graphs, zero for n≥D2n\ge D^2 on every family of bounded degree DD, among them the NP-hard and UG-hard bounded-degree families, and O(n)O(\sqrt n) on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio O(n)O(\sqrt n) on all graphs; a proof would imply P=NP\mathrm{P}=\mathrm{NP}. In a reduction from satisfiability, every independent dominating set of the graph of a formula with NN variables and tt copies of every clause, tt at least the largest clause width WW, is a satisfying assignment, with NN vertices, or has at least t+Nt+N vertices; with t=Wt=W, every independent dominating set of ratio smaller than 1+W/N1+W/N is a satisfying assignment. This proves the n1−εn^{1-\varepsilon} inapproximability directly from satisfiability, without a gap from the PCP theorem. Through a reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}, with an explicit edge gadget that turns a graph HH into a graph h(H)h(H) with i(h(H))=τ(H)+2∣E(H)∣i(h(H))=\tau(H)+2|E(H)|, where τ(H)\tau(H) is the minimum vertex cover size, every output on h(H)h(H) decodes into a vertex cover of HH; we state the conditional consequences under the Unique Games Conjecture, for which a proof has been reported but not yet peer reviewed, on general graphs and, through the result of Austrin, Khot and Safra, on bounded-degree graphs. In reproducible experiments the output is optimal on 9 9999\,999 of 10 00010\,000 graphs with an exact integer-program optimum, on all 9595 of 112112 bipartite graphs whose optimum was proved, on all 1818 instances of the set cover reduction, and on 22 of the 3030 instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between 1.251.25 and 1.86651.8665. We also report the results on the 6868 complements of the DIMACS clique benchmark.

Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBoolean satisfiabilityForest Dynamic ProgrammingMinimum Independent Dominating SetMinimum Maximal Independent SetP versus NPUnique Games Conjecturebipartite graphslocal search
Nov 03, 202630 pages
PDFView work

cs.CC — Computational Complexity

A Sublinear Treewidth Exponent for Binary Constraint Satisfaction

Contributed by Troy Tri Nguyen

We give a deterministic algorithm for binary constraint satisfaction whose exponent in the input size is sublinear in treewidth on a class of graphs with unbounded treewidth. There are a class G of graphs of bounded maximum degree, a constant c, and a function f such that one algorithm correctly decides every binary CSP instance and, on instances I with primal graph G ∈ G, runs in time f(G) · ||I||^(c · tw(G) / sqrt(log tw(G))) . This contradicts the literal formulation of Conjecture 1.4 of Marx (2010). The algorithm follows from a domain-uniform counting bound: for every fixed maximum degree ∆, complete-table in- stances with k variables and domain size D ≥ 2 can be counted in time LO∆ (1)DO∆ (k/√log k) for sufficiently large k. The constants are independent of D and of the constraint relations. We obtain this bound from the tensor-network recursion of Claude (Anthropic), and use attributed graph foundations from OpenAI to construct the required expander family. Support pruning connects the counting routine to sparse tuple-list inputs without expanding the original domain. The algo- rithm, its native finite-alphabet machine implementation, and the conjecture counterexample are formalized in Lean 4.

Primarily AI-generated textHuman understanding: some parts
Nov 02, 202616 pages
PDFView work

math.NT — Number Theory

An Improved Subexponential Bound for Deterministic Integer Factorization

Contributed by Joseph Shunia

We prove that the complete prime factorization of an nn-bit integer can be computed deterministically in time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})} and polynomial space. This establishes the bound conjectured by Rudich and Rousseau, sharpening their qualitative No(1)N^{o(1)} result. The proof combines OpenAI's quantitative Boolean tensor-contraction theorem with the linear-size multiplication encoding of Akshima et al. The encoding permits exact counting of divisors with prescribed binary prefixes without loss in the exponent. The least prime factor is then recovered by successive prefix queries, and iteration yields the complete factorization within the same asymptotic bound.

Primarily AI-generated textHuman understanding: all partsBoolean tensor networksdeterministic algorithmsexact countinginteger factorizationsubexponential time
Nov 02, 20264 pages
PDFView work

cs.CC — Computational Complexity

The Esperanza Algorithm for Maximum Independent Set

Contributed by Frank Vega

The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph. It is NP-hard to approximate within n1−εn^{1-\varepsilon} for every ε>0\varepsilon>0, and under the Unique Games Conjecture it is hard to approximate within O(Δ/log⁡2Δ)O(\Delta/\log^2\Delta) on graphs of maximum degree Δ\Delta; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a (2−ε)(2-\varepsilon)-approximation of Minimum Vertex Cover. We present version 0.1.6 of \textsc{Esperanza}, which takes the better of a dynamic minimum-degree (Caro--Wei) greedy set and the complement of the \textsc{Salvador} vertex cover, and improves it by three budgeted local searches: repair-and-grow restarts at the cover vertices and at a maximum-degree vertex, chained local restarts realising (k,k+1)(k,k+1)-improvements, and an iterated (1,2)(1,2)-swap search. We prove that it runs in O((n+m) αA(n))O((n+m)\,\alpha_{\mathrm A}(n)) expected time for fixed budgets, with αA\alpha_{\mathrm A} the inverse Ackermann function. We prove that the output is a maximal independent set, that its complementary vertex cover has at most 2τ−r2\tau-r vertices, where τ\tau is the minimum cover size and rr the number of components with an edge, and that the ratio is at most (Δ+2)/3(\Delta+2)/3 on graphs of maximum degree Δ\Delta. We prove the ratio 2n2\sqrt n on every graph with Δ≤n\Delta\le\sqrt n and on three further classes, and state it for all graphs as a conjecture, whose proof would imply P=NP\mathrm{P}=\mathrm{NP}. We also state the conjecture that the complementary cover has at most 2τ−∣M∣2\tau-|M| vertices for the NetworkX minimum maximal matching MM; a proof would give a 3/23/2-approximation for Minimum Vertex Cover and refute the Unique Games Conjecture unless P=NP\mathrm{P}=\mathrm{NP}. In reproducible experiments the returned set is optimal on all 30 00030\,000 graphs of a suite certified by an exact integer program; on 4040 Khot--Regev YES instances with 640640 to 2 5602\,560 vertices the conjectured bound is certified on 3838 and open on 22; and on 3131 bounded-degree graphs the certified ratio is at most 1.07691.0769 on the families with a planted independent set.

Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBounded-degree GraphsLinear TimeMaximum Independent SetP versus NPUnique Games ConjectureVertex Coverlocal search
Nov 02, 202613 pages
PDFView work

math.NT — Number Theory

Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

Contributed by Joseph Shunia

We give a deterministic polynomial-time primality test whose main verification is the congruence (1+X)n=1+Xn(1+X)^n=1+X^n in Cn[X]/(Xr−b(Y))C_n[X]/(X^r-b(Y)), where Cn=(Z/nZ)[Y]/(Φr(Y))C_n=(\mathbb{Z}/n\mathbb{Z})[Y]/(\Phi_r(Y)). Two identities in the coefficient ring normalize bb and ensure compatibility with the main congruence. A finite-field root count and a lattice bound show that an accepted input is a prime power; elementary preprocessing excludes nontrivial perfect powers. We construct bb deterministically using Jacobi sums and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner, which extends OpenAI's Hecke zero-free theorem. The total bit complexity is L32+o(1)L^{32+o(1)}, where L=⌈log⁡2n⌉L=\lceil\log_2 n\rceil, and verification after constructing bb costs L6+o(1)L^{6+o(1)}. More generally, for a fixed real algebraic 1/2≤θ<11/2\le\theta<1, a common zero-free boundary ℜs>θ\Re s>\theta for the relevant Dedekind zeta functions gives Lmax⁡{6,(1−θ)−1}+o(1)L^{\max\{6,(1-\theta)^{-1}\}+o(1)}. This bound reaches L6+o(1)L^{6+o(1)} at θ=5/6\theta=5/6, and hence under GRH. We state a fixed-base modification of Agrawal's conjecture for odd integers passing the base-22 Fermat test, using the modulus Xr−2X^r-2 with rr the least positive integer not dividing n(n−1)n(n-1).

Primarily AI-generated textHuman understanding: all partsJacobi sumsKummer extensionsbinomial congruencescyclotomic ringsdeterministic algorithmspolynomial timeprimality testing
Oct 31, 202614 pages
PDFView work

cs.CC — Computational Complexity

The partition exponent in the graded pieces of the Claude 3-SAT algorithm is optimal for pieces of that shape

Contributed by Carlos Stein Naves de Brito

In Appendix B of "A 2o(n)2^{o(n)} time algorithm for 3-SAT" (Claude, Anthropic, hexagon:2610.00577) the gain parameter ρ=1/2\rho = 1/\sqrt{2} comes from the Hardy--Ramanujan growth log⁡p(E)∼cE\log p(E) \sim c\sqrt{E} of the partition numbers, and Appendix H observes that growth of order EαE^\alpha would give ρ=2α−1\rho = 2^{\alpha-1} by the same calculation. We point out that the rank floor stated in the same Appendix H already excludes α<1/2\alpha < 1/2 for every graded family of the same shape: the pieces at weight hh have total rank at most (4h+1)dim⁡V≤4h(4h+1)\dim V_{\le 4h} in one of the two directions, and the crossing they must add up to has rank (dim⁡Vh)2(\dim V_h)^2, so the construction needs log⁡dim⁡V≤4h≥2log⁡dim⁡Vh−O(log⁡h)\log \dim V_{\le 4h} \ge 2\log\dim V_h - O(\log h), that is α≥1/2\alpha \ge 1/2. Restoring the rank with a larger weight costs ρ≥2−α\rho \ge 2^{-\alpha} in the weight count, so the count never goes below max⁡(2α−1,2−α)≥1/2\max(2^{\alpha-1}, 2^{-\alpha}) \ge 1/\sqrt{2}, with equality only at α=1/2\alpha = 1/2; when the identity holds on the whole weight space, as Lemma 9 of the paper gives it, the bound sharpens to 2α/(2(4α−1))2^\alpha/(2(4^\alpha-1)), which exceeds 1 for α<0.357\alpha < 0.357. Theorem B of the paper is rank-tight up to a polynomial factor. The inequality is exact and we tabulate it: for the partition numbers it holds for every hh, for partitions into squares (α=1/3\alpha = 1/3) it fails for all h≥5891h \ge 5891. We also record that the Heisenberg Fock spaces on a sparse set of modes, the natural candidates for slower growth, do not carry Lemma 9, and that no choice of coefficients repairs it. The floor ρ≥1/2\rho \ge 1/2 remains open.

Primarily AI-generated textHuman understanding: some parts3-SATExponential Time Hypothesisinteger partitionsrank bounds
Oct 31, 20266 pages
PDFView work

cs.DS — Data Structures and Algorithms

Counting Hamiltonian cycles in sparse graphs in subexponential time, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

In October 2026 two manuscripts claimed refutations of the Exponential Time Hypothesis by deterministic algorithms for #k\#k-SAT, each with a Lean formalisation of its top-level statement. Neither result applies directly to connectivity problems such as Hamiltonicity, because no linear-size CNF encoding of "this edge set is a single cycle" is known. This paper derives a corollary of the Anthropic manuscript: assuming three of its internal results (a network-to-clique reduction, an algorithm for cliques of all levels, and the existence of its "pieces"), the number of Hamiltonian cycles of a graph with nn vertices and at most DnDn edges can be computed exactly and deterministically in time O(2δn)O(2^{\delta n}) for every δ>0\delta>0, and in time 2O(max⁡(m,n)/log⁡n)2^{O(\max(m,n)/\sqrt{\log n})} for a graph with mm edges. A rank-encoded variant of the construction gives 2O(nlog⁡dˉ/log⁡n)2^{O(n\log\bar d/\sqrt{\log n})} for average degree dˉ\bar d. Deterministic decision, search and Hamiltonian-path counting follow, and so do exact sparse TSP with polynomially bounded weights, exact counting of directed Hamiltonian cycles, and ATSP. The result is not a standalone breakthrough; it stands or falls with the claimed refutation. The ingredients are known: the folklore matrix-tree identity on 22-factors, the fermionic (Berezin) matrix-tree theorem of Caracciolo, Jacobsen, Saleur, Sokal and Sportiello, and the blob partitions of Cut&Count. What is new is the observation that connectivity can be encoded with O(1)O(1) bits per edge through a Grassmann determinant whose only non-local part is a sign, and that this sign costs only O(g3)O(g^3) bits for gg blobs, so the whole construction is a network in the sense of the manuscript, whose value is n⋅#HC(G)n\cdot\#\mathrm{HC}(G). Every theorem we claim is formally verified in Lean, end to end, on top of the manuscript's own Lean development: the three counting theorems, the decision, search and path corollaries, sparse TSP, directed Hamiltonian cycles and ATSP, using only the standard axioms, with fresh kernel replays. The Lean sources are at https://github.com/xennygrimmato/eth-hamiltonicity. We also record weaker results that rest only on the machine-checked top-level theorems: the parity of #HC(G)\#\mathrm{HC}(G) for every graph in time 2O((m+n)/log⁡(m+n))2^{O((m+n)/\sqrt{\log(m+n)})} (machine-checked in Lean, with the hypotheses discharged by the labs' own Lean proofs), and one-sided randomized decision. We describe what is proved, what is checked numerically, what is formalised, what is assumed, and what the limitations are.

Primarily AI-generated textHuman understanding: some partsHamiltonian cycle; ETH; matrix-tree theorem; Grassmann algebra; Cut&Count; TSP
Oct 31, 202629 pages
PDFView work

cs.DS — Data Structures and Algorithms

What Does the Refutation of the Exponential Time Hypothesis Mean for Learning Theory?

Contributed by Xiaoyu Li

Two recent works by OpenAI and Anthropic refuted the Exponential Time Hypothesis (ETH). They count the satisfying assignments of a kk-CNF on nn variables in time 2n/(log⁡n)1/2−o(1)2^{n/(\log n)^{1/2-o(1)}}. Many fine-grained lower bounds in learning theory rest on ETH and its relatives. We determine what the refutation changes for learning. The answer is a locality principle: the new algorithms speed up learning when each labeled example constrains few bits of the hypothesis, and under the CNF form of the Strong Exponential Time Hypothesis, which survives, the speed-up ends at Θ(log⁡N)\Theta(\log N) bits. Three transitions make the principle precise. Locality. Call a class with NN-bit descriptions κ\kappa-local if each label depends on at most κ\kappa description bits, as for quantized models on sparse data. Then proper PAC learning, exact version-space counting and sampling, and the halving algorithm run in time poly(m)⋅2o(N)\mathrm{poly}(m)\cdot 2^{o(N)} on samples of size mm for κ=o((log⁡N)1/4/log⁡log⁡N)\kappa=o((\log N)^{1/4}/\sqrt{\log\log N}), and proper PAC learning at constant accuracy does so for κ=o(log⁡N)\kappa=o(\sqrt{\log N}). At inverse-polynomial accuracy, proper learning of κ\kappa-local classes is equivalent to κ\kappa-SAT, up to a factor 22 in the locality. Under CNF-SETH, consistency for binarized perceptrons on O(log⁡N)O(\log N)-sparse data needs time 2(1−γ)N2^{(1-\gamma)N} for every γ>0\gamma>0. Accuracy. Exact empirical risk minimization, proper agnostic learning and the exponential mechanism reduce to tensor contractions over a truncated polynomial ring. As a consequence, the Sparse Max-SAT Hypotheses of Alman and Vassilevska Williams are false. At constant accuracy, proper learning is SAT parameterized by formula length. With quasi-linear PCPs this gives a 2N/polylog N2^{N/\mathrm{polylog}\,N} lower bound under a length form of ETH, which replaces Gap-ETH for reductions of quasi-linear size. At accuracy N−3/8N^{-3}/8, the Max-3-SAT Hypothesis forces time 2(1−o(1))N2^{(1-o(1))N}. Treewidth. Exact inference in graphical models of bounded degree and arity takes time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}. On expanders this beats every elimination order and every structured DNNF. Under #\#CNF-SETH, time 2(1−γ)tw2^{(1-\gamma)\mathrm{tw}} is again necessary once a model may have twO(1)\mathrm{tw}^{O(1)} variables. We also take stock of the conditional lower bounds of learning theory: which ones fall, and which ones survive on which hypothesis. The bound for training one ReLU loses its proof, because its hypothesis about Densest kk-Subgraph on bounded-degree graphs is false. The next obstacle is a permutation problem. On difference vectors ei−eje_i-e_j, empirical risk minimization for real-valued halfspaces is weighted Feedback Arc Set, which the new algorithms do not reach.

Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisPAC learningStrong Exponential Time Hypothesiscomputational learning theoryempirical risk minimizationfine-grained complexitymodel countingprobabilistic graphical modelstensor networkstreewidth
Oct 29, 202667 pages
PDFView work

math.LO — Logic

The Euclidean algorithm is not optimal among uniform processes

Contributed by Jason Davies

Reusing a stored Euclidean prefix, we show that every pair a≥ba\geq b has a derivation of gcd⁡(a,b)\gcd(a,b) from a,ba,b with O(log⁡a/log⁡log⁡a)O(\log a/\log\log a) applications of the remainder function alone; Euclid's algorithm needs order log⁡a\log a in the worst case. These derivations bound the intrinsic complexity of gcd and coprimeness by the same order, refuting Moschovakis's conjectured logarithmic lower bounds for uniform processes; by his best-uniform-process theorem, a single uniform process attains this bound. The Main Conjecture for algorithms remains open. We also prove an Ω(log⁡log⁡a)\Omega(\log\log a) lower bound on this complexity for almost all coprime pairs and give, for each ε>0\varepsilon>0, a nondeterministic register program computing gcd that, on every input a≥b≥1a\geq b\geq1, has a successful computation using at most εlog⁡a+O(1)\varepsilon\log a+O(1) remainder calls. The upper bound also answers negatively an open problem of van den Dries and Moschovakis on the closure depth of the gcd. The main bounds and the refutations are formalised in Lean 4; the best-uniform-process theorem is cited.

Primarily AI-generated textHuman understanding: some partsEuclidean algorithmLean 4closure depthgreatest common divisorintrinsic complexityremainder functionuniform processes
Oct 29, 202616 pages
PDFView work

cs.CC — Computational Complexity

Deterministic Factoring in Time No(1)N^{o(1)}

Contributed by Isaac Rudich, Louis-Martin Rousseau

The current best upper bound for deterministic factoring is N1/5+o(1)N^{1/5+o(1)}. We provide a Lean certificate that there exists a deterministic Turing machine that computes the smallest prime factor of every NN in No(1)N^{o(1)} steps: for every k≥1k\ge 1 it runs within Ck 2n/kC_k\,2^{n/k} steps on nn-bit inputs. The algorithm reduces factoring to counting divisors with prescribed leading bits, and counts them by leveraging the counting engine used to refute the Exponential Time Hypothesis (ETH). The Lean statement that a reader must check to verify the proof is only 13 lines and only uses Mathlib. The full proof is about 35,000 lines. This note was written less than 24 hours after the ETH refutations were posted. No human-readable explanation of these results exists yet, and their Lean proofs are long: Anthropic's alone runs to about 152,000 lines. Our proof re-proves only the part of the counting engine it needs and imports nothing from those developments. We hope this application, with its short statement, serves as a stepping stone for those working to understand the engine; a follow-up paper will explain this proof in detail.

A mix of human-written and AI-generated textHuman understanding: some partsExponential Time HypothesisLeancounting algorithmsdeterministic factoringformal verificationinteger factorization
Oct 29, 20266 pages
PDFView work

cs.CC — Computational Complexity

Subexponential Weighted Counting and Exact Optimisation

Contributed by Deep Bhattacharjee

The deterministic algorithm of \oai{} that counts the satisfying assignments of a kk-CNF in time 2o(n)2^{o(n)} is reproduced in full and extended from counting to sums of local weights with values in any commutative $\Q$-algebra. The extension gives deterministic 2o(n)2^{o(n)} algorithms for exact Max-Cut and Max-kk-SAT on sparse instances, for the independence polynomial, the maximum independent set and the knapsack problem with a conflict graph on every graph, for 00-11 integer programs whose rows involve boundedly many variables, for Vertex Cover in time $2^{o(k)}+\poly(n)$, for the density of states of Ising and Potts models on bounded-degree graphs, for the Tutte polynomial on the hyperbolas (x−1)(y−1)=q(x-1)(y-1)=q, for the minimum distance and the maximum-likelihood decoding of codes with sparse parity checks, for Max-Cut and Max-kk-SAT at every average degree o(log⁡n/log⁡log⁡n)o(\sqrt{\log n/\log\log n}), for Max-Cut on dense graphs close to blow-ups of graphs with o(n/log⁡n)o(n/\log n) vertices, and for every problem in $\SNP$.

A mix of human-written and AI-generated textHuman understanding: some partsExponential Time HypothesisLDPC codes.Max-SATTutte polynomialVertex Coverindependence polynomialpartition functionsweighted counting
Oct 29, 202650 pages
PDFView work

cs.CC — Computational Complexity

On counting satisfying assignments via polynomial separation

Contributed by Scott Kominers

We give a preliminary exposition of a qualitative form of the main result of OpenAI's preprint "The Exponential Time Hypothesis is false": for every fixed ε>0\varepsilon>0, 33-SAT on nn variables with mm clauses can be decided in time Oε(2εn(n+m)O(1))O_\varepsilon(2^{\varepsilon n}(n+m)^{O(1)}) and polynomial space. We separate the general counting procedure from the construction that supplies its input. The procedure deforms the clause inputs so that, at designated points, the count factors into local sums, from which Hermite interpolation recovers the original count; the construction builds such deformations from coordinate swaps in a tensor basis, leveraging a parity interpolation in the spirit of Alman and Williams.

A mix of human-written and AI-generated textHuman understanding: some parts3-SATExponential Time HypothesisHermite interpolationpolynomial interpolationsparsification
Oct 27, 202611 pages
PDFView work

cs.CC — Computational Complexity

Some exposition of “The Exponential Time Hypothesis Is False”

Contributed by Ryan O'Donnell

This is an exposition of the paper "The Exponential Time Hypothesis Is False" by OpenAI [Oct. 26, 2026], produced through discussion with an LLM. Among other things, it tries to highlight the approximating polynomial for parity, and writes the matrix version of this polynomial using (a light amount of) quantum language.

Primarily AI-generated textHuman understanding: no partsSAT
Oct 27, 202612 pages
PDFView work

cs.CC — Computational Complexity

A 2o(n)2^{o(n)} Time Algorithm for 3-SAT

Contributed by Anthropic

We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in 2o(n)2^{o(n)} time. Our algorithm in fact solves the harder problem #3-SAT, providing a count of the number of satisfying assignments. The result was discovered by an internal research Claude model and has been formalized in Lean 4.

Primarily AI-generated textHuman understanding: some parts
Oct 27, 202649 pages
PDFView work

math.RA — Rings and Algebras

The rank of 3×3 matrix multiplication over F2 is 23

Contributed by Tejasvi Singh Tomar

The rank of the tensor of 3×33\times 3 matrix multiplication over the field with two elements is at most 2323 by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least 2222. We prove that it equals 2323. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over F2\mathbb{F}_2 and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for 111111 of Wang's 496496 classes of subspaces, constrain the ranks of the first factors through a 27×2727\times 27 flattening of the tensor, and list, up to symmetry, all sets of 2222 first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

A mix of human-written and AI-generated textHuman understanding: all parts
Oct 26, 202618 pages
PDFView work

math.CO — Combinatorics

A degree-three local-weight cap and an improved relevant-variable bound

Contributed by Ricardo Pinho

We prove that the local-degree potential of a Boolean function of degree at most three is at most 5/4, using the published fact that such a function has at most ten relevant variables. Inserting this cap into Wellens's degree–block-sensitivity recurrence, with the existing exact certificates released by Épi, gives C_44 <= 4.3576549226. The reproduced preceding recurrence gives approximately 4.365467422574458; our exact degree-three cap lowers it by 1/128. Two separately written exact-arithmetic programs check the finite certificates, recurrence, infinite tail and finite cases of the added lemma. The universal argument is written in the paper; the published degree-three classification is cited, not re-enumerated. This preprint is not peer reviewed and not verified in a proof assistant; no optimality is claimed.

Primarily AI-generated textHuman understanding: some partsBoolean functionsblock sensitivitycomputer-assisted proofexact rational certificatespolynomial degreerelevant variables
Oct 26, 20265 pages
PDFView work

cs.CC — Computational Complexity

Polynomial Fault Detection Without Bounded Width: Exact Reachable Sets in Priority Controllers

Contributed by Idris Ali Shaik

Circuit-width restrictions explain several polynomial cases of automatic test pattern generation. We give a different explanation for an arbitrary-size extension of the c432 priority controller, including a subfamily with linear treewidth and net cut-width in its native layout. For a specified first-stage bridge fault, we characterize exactly the reachable qualifier sets and construct a primary input realizing each one. On drive-one inputs where the first selector flag changes, the healthy set is the target singleton; the faulty sets are precisely the target-containing sets with one request bus and all nonempty sets with at least two buses. Drive zero is undetectable. This image reduces detection to comparing decoder values on sets. For supplied guarded decoders, built from zero, positive channel leaves, disjunction and conjunction of one computed child with negative channel literals, supporting paths and dual-Horn reasoning find a detecting set in O((n+q)G) time for n channels, q outputs and counted decoder size G, or O(G) for formula forests. Unsatisfiable instances of the complete guarded native CNF encoding have resolution refutations with O(N³) inferences, where N is the encoding size. Detection is P-complete, while minimum-set optimization and counting detecting sets are NP-hard and #P-complete, respectively. A specified final-qualifier stuck-at fault makes detection NP-complete on shared guarded decoders. The exact first-stage bridge-image statements are formalized in Lean and registered as PALOMAR-2026-10-19-000010, version 1.

A mix of human-written and AI-generated textHuman understanding: all partsBoolean satisfiabilityautomatic test pattern generationfault detectionpriority controllersproof complexity
Oct 23, 202647 pages
PDFView work

cs.CC — Computational Complexity

Unconstrained detection of productive autocatalytic cores is NP-complete

Contributed by Michael Mislan

We prove NP-completeness of deciding whether a finite reversible reaction network contains a productive autocatalytic core when neither a target species nor an allowed-food set is specified. The input is a binary encoding of literal nonnegative integer reactant and product matrices, with a signed real flow on each reaction identity. A nonsingular square-witness characterization gives polynomial certificates. A weighted incidence construction reduces prescribed two-path directed linkage to unrestricted core detection, and an explicit constant-size switch construction reduces SAT to the linkage instances. Actual machine-level NP membership and a total polynomial-time binary transducer complete the classification. The terminal theorem is verified in Lean 4. The result concerns structural possibility in this source model and imposes no elementary reaction arity or conservation constraint.

Primarily AI-generated textHuman understanding: some partsLean formalizationNP-completenessautocatalytic coresbinary encodingpolynomial-time reductionsreaction networks
Oct 20, 20268 pages
PDFView work

cs.CC — Computational Complexity

Deciding D-stability is coNP-hard

Contributed by Michael Mislan

The computational difficulty of D-stability, raised by Chen, Fan and Yu (1995, doi:10.1016/0167-6911(94)00036-U), is addressed by an explicit integer-matrix reduction from PARTITION. For positive weights of total 2T, the construction produces a matrix of order m + 4 that is D-stable exactly when no subset has weight T. When an equal split exists, some positive diagonal scaling has an eigenvalue with strictly positive real part. A Pell recursion supplies the parameters, with a logarithmic search bound and an explicit bound on every matrix entry. These bounds give polynomial binary output length. Together with the classical NP-completeness of PARTITION, the reduction yields coNP-hardness of D-stability and D-semistability, and NP-hardness of strict D-instability, even for a four-dimensional core with attachments at one coordinate. The hardness is in the weak sense for binary encoding. Running-time analysis and the trivial-instance cases are treated conventionally; registered Lean statements verify the explicit arithmetic encoding, bounds and promise dichotomy.

Primarily AI-generated textHuman understanding: some partsD-stabilityLean formalizationPARTITIONPell equationcoNP-hardnessdiagonal scaling
Oct 20, 202619 pages
PDFView work

cs.CC — Computational Complexity

A Three-Polynomial Counterexample to the Generalized Effective Hypercube Nullstellensatz

Contributed by YURAN XIU

We give a counterexample to the proposed extension of the effective Hypercube Nullstellensatz from two polynomials to an arbitrary fixed number of polynomials. For every n≥1n\geq1, we construct three real polynomials in 2n+12n+1 variables, of degrees 2,2,12,2,1, respectively. Each is nonzero as a function on the Boolean cube, their product vanishes on the cube, and they have no common Boolean zero. Nevertheless, every polynomial certificate ∑i=13higi=1\sum_{i=1}^3 h_i g_i=1 on the cube satisfies deg⁡h1g1‾≥n+1\deg\overline{h_1g_1}\geq n+1, where the bar denotes multilinearization. The construction applies a fresh selector variable to the hard pair of Kothari, Kovacs-Deak, Wang, and Yang. Thus its new ingredient is a short transfer of their existing degree obstruction to the product-zero setting. The full unbounded-degree counterexample has been formalized and checked in Lean 4. HAL deposit: hal-05800244v1.

Primarily AI-generated textHuman understanding: no partsBoolean cubeLean formalizationNullstellensatzdegree lower boundspolynomial certificates
Oct 18, 20264 pages
PDFView work

cs.CC — Computational Complexity

A Counterexample to Affine-Subspace Union Stability under Small Deletions

Contributed by YURAN XIU

We construct a family of affine coordinate subspaces of F2N\mathbb{F}_2^N whose union is the entire space, but for which deleting a 1/N1/N fraction from each member removes a fraction larger than N−cN^{-c} from the union, for every fixed c>0c>0 and arbitrarily large NN. Each subspace has codimension log⁡2N\log_2 N, and the family has at most 2N22N^2 members. The construction uses all monochromatic coordinate conditions of size kk on 2k2k distinguished coordinates, where N=2kN=2^k, and deletes their common intersection with the middle Hamming layer. The exact global loss is (2kk)/4k\binom{2k}{k}/4^k. This disproves the affine-union conjecture of Alekseev and Gaevoy, already for their fixed parameters q=2q=2 and r=1r=1. The all-exponent, arbitrarily-large-dimension counterexample has been formalized and checked in Lean 4. HAL deposit: hal-05800246v1.

Primarily AI-generated textHuman understanding: no partsBoolean cubeLean formalizationaffine subspacescounterexampleunion stability
Oct 18, 20265 pages
PDFView work

cs.CC — Computational Complexity

An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm

Contributed by Frank Vega

Minimum Vertex Cover has a classical linear-time ratio of 22, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 22 unless P=NP\mathrm{P}=\mathrm{NP}. We present version 0.1.4 of \textsc{Salvador}, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in O((n+m) α(n))O((n+m)\,\alpha(n)) time, and that the returned cover has at most 2τ−r2\tau-r vertices, where rr is the number of components with an edge, so the ratio is at most 1.9999999991.999999999 whenever τ≤109r\tau\le10^{9}r. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft--Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most 2L−∣M∣2L-|M| vertices, for a lower bound L≤τL\le\tau and the maximal matching MM, is within ratio 3/23/2 on that instance. In a reproducible suite the returned cover satisfies ∣C∣≤2τ−∣M∣|C|\le2\tau-|M| on all 291291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 6868 DIMACS clique complements it is never worse than Hvala and optimal on 3737 instances against 1818. Whether ∣C∣≤2τ−∣M∣|C|\le2\tau-|M| holds on every graph is stated as a conjecture: a proof would give a linear-time 3/23/2-approximation and would refute the Unique Games Conjecture unless P=NP\mathrm{P}=\mathrm{NP}.

Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBipartite LayersEnsemble HeuristicsLinear TimeMaximal MatchingP versus NPSplit GraphUnique Games ConjectureVertex Cover
Oct 18, 202631 pages
PDFView work

cs.CC — Computational Complexity

The Exact Junta Bound for Degree-Two Boolean Functions on q-ary Hamming Cubes

Contributed by YURAN XIU

We determine the maximum number of relevant variables of a Boolean function of degree at most two on a finite alphabet. For every integer q≥2q\geq2, this maximum is exactly max⁡{4,q+1}\max\{4,q+1\}. Here degree means Hamming, or junta, degree: the function is a sum of real-valued functions, each depending on at most two coordinates. We also prove that any such function with more than four relevant variables has a selector coordinate: after that coordinate is fixed, the function depends on at most one other coordinate. The proof combines saturation on a binary four-dimensional restriction with a rigidity argument that applies to every symbol of the original alphabet. Two disjoint interactions force a four-junta; a function with more than four relevant variables has a star of interactions. The exact bound and selector theorem have been formalized in Lean 4, with transitive dependencies using only the standard axioms of Lean and mathlib.

Primarily AI-generated textHuman understanding: no partsBoolean functionsHamming graphsLean formalizationdegree twojunta theoremrelevant variables
Oct 17, 20268 pages
PDFView work

cs.CC — Computational Complexity

Set Cover by Cyclic Rotations Is NP-Complete

Contributed by YURAN XIU

Given an explicitly listed binary pattern of positive length nn and a nonnegative integer bb in binary, can at most bb cyclic rotations of the pattern cover all nn positions? We prove that this decision problem is NP-complete. The reduction constructs a pattern in a cyclic group of polynomial order and outputs its entire indicator word. Its principal ingredient is a replicated-marker construction: a cover within the budget must choose one translate in every layer, and each failed difference constraint leaves a block of more holes than the remaining translates can cover. Combining this construction with the known embedding of graph cliques into circulant graphs using distinct three-term sums gives a polynomial-time reduction from 33SAT. The theorem allows every subset, including the empty pattern, and every binary budget. A Lean formalization checks the mathematical reduction, the full-word polynomial-time programs, NP membership, and the unconditional NP-hardness foundation. HAL deposit: hal-05800233v1.

Primarily AI-generated textHuman understanding: no partsLean formalizationNP-completenesscyclic rotationsset cover
Oct 17, 202611 pages
PDFView work

cs.CC — Computational Complexity

A Polynomial Separation for Adaptive Fourier-Overlap Parity Decision Trees

Contributed by YURAN XIU

Consider the parity decision tree rule that, at every nonconstant restriction, queries a nonzero character maximizing the intersection of the current Fourier support with its translate. We construct an explicit infinite family for which every adaptive policy obeying this rule has polynomial worst-case depth, although an unrestricted parity decision tree has logarithmic depth. For every ℓ≥1\ell\geq1, let R=2ℓR=2^\ell. Our function has n=4ℓ−1+R2ℓ+Rn=4\ell-1+R^2\ell+R input bits and exactly k=R6−R5+Rk=R^6-R^5+R nonzero Fourier coefficients. Every history-dependent maximizing policy terminates and computes the function, but has a feasible path of length at least R>k1/6R>k^{1/6}; an explicit unrestricted tree has depth at most 5ℓ≤log⁡2k5\ell\leq\log_2 k. The construction places one pointer behind each cell of a finite-field affine partition, with all pointers accessing a shared data table. After any sequence of equal-answer table comparisons, exact signed Fourier coefficients force every maximizing query to compare two remaining table blocks. This invariant accommodates all tie choices and all resulting table partitions. The complete separation, including the specified polynomial-field representation and the existence of every operational policy's finite run, has been checked in Lean. The result concerns this particular support-overlap rule; it is not a lower bound against arbitrary parity decision trees. HAL deposit: hal-05800236v1.

Primarily AI-generated textHuman understanding: no partsFourier analysisLean formalizationadaptive algorithmsparity decision trees
Oct 17, 202613 pages
PDFView work