Browse

Data Structures and Algorithms

cs.DS — Data Structures and Algorithms

cs.DS RSS feed

Works in cs.DS

40 works

cs.DS — Data Structures and Algorithms

Sorting networks on 13 inputs need at least 44 comparators

Contributed by Tejasvi Singh Tomar

Let S(N)S(N) be the least number of comparators in a sorting network on NN inputs. We prove S(13)≥44S(13)\ge44, one more than the previously best proved lower bound. We also prove P(2,N)=⌈log⁡2F(N)⌉P(2,N)=\lceil \log_2 F(N)\rceil for 3≤N≤323\le N\le32, where P(2,N)P(2,N) is the least worst-case number of comparators met by the two largest inputs in a network that delivers them to fixed outputs and FF is an explicit function of Van Voorhis; the lower bound comes from a finite search based on the structure of the paths of these two values. Starting from Harder's S(11)=35S(11)=35 and S(12)=39S(12)=39, these values of P(2,N)P(2,N), the two-value bound S(N)≥S(N−2)+P(2,N)S(N)\ge S(N-2)+P(2,N) and the one-value bound S(N)≥S(N−1)+⌈log⁡2N⌉S(N)\ge S(N-1)+\lceil \log_2 N\rceil give the twenty lower bounds on S(N)S(N) for 13≤N≤3213\le N\le32 in Dobbelaere's table; these bounds rested on Van Voorhis's inequality P(2,N)≥⌈log⁡2F(N)⌉P(2,N)\ge\lceil \log_2 F(N)\rceil, whose published proof is invalid. The bound S(13)≥44S(13)\ge44 is also proved in Lean 4, with every step checked by Lean's kernel.

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

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202620 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

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

cs.DS — Data Structures and Algorithms

An Optimal Deterministic Adversary for Sorting

Contributed by Nicholas Nash

This paper describes an optimal deterministic, polynomial-time adversary for ordinary sorting. For any correct sorting algorithm, the adversary forces that algorithm to make (1−o(1))nlog⁡2n(1-o(1))n\log_2 n comparisons. The best previously known deterministic polynomial-time adversary forced 3764nlog⁡2n\frac{37}{64}n\log_2 n comparisons. The adversary maintains a family of orders consistent with the answers so far, using a hierarchy of directed acyclic graphs. Bounds on vertex degrees and directed path lengths allow comparison answers to be chosen through deterministic calculations on small graph neighborhoods.

Author comments: Substantially revised and expanded exposition, with explicit algorithms, intuitive explanations of the main proofs, and further consequences. 36 pages. Source and Lean formalization: https://github.com/nicknash/sorting-adversary-proofs .

Primarily AI-generated textHuman understanding: some parts
Nov 10, 202636 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

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

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

Three-machine unit-job scheduling in time O((L+2)^276)

Contributed by David Niedbala Giraudin

OpenAI recently gave a deterministic polynomial-time algorithm for P3|prec,p_j=1|C_max (problem OPEN8 of Garey and Johnson), with running time O((L+2)^150020) on a multitape Turing machine, L being the input length; the same exponent appears in the accompanying Lean statement. The exponent comes from enumerating all Boolean formulas with at most 10000 leaves, each leaf choosing its own triple of jobs. We show that every description actually used by the structural proof involves at most 21 distinct job triples and at most 3 distinct rank thresholds. Restricting the enumerated family accordingly, and using the length bound on accepting paths already proved there to limit the number of reachability passes, the same algorithm runs in time O((L+2)^276).

Primarily AI-generated textHuman understanding: no partsOPEN8polynomial-time algorithmprecedence constraintsrunning-time exponentthree-machine schedulingunit processing times
Nov 04, 20263 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.DS — Data Structures and Algorithms

Arithmetic Dynamics as the Seventh World: The Law of Forgetting for z^2+c

Contributed by Zeng Chunping

Among the seven worlds of the central-charge program (number fields, function fields, graphs, finite-type dynamics, knots, tropical geometry, and arithmetic dynamics), the seventh is the only one whose critical exponent is continuously tunable, and the only one whose "cusp layer" is visible point by point over the primes. For phi(z) = z^d + c reduced modulo p, the orbit structure splits into two layers: an algebraic-closure layer (universal, smooth, forgotten: N_m = #Fix(phi^m) = d^m + 1, independent of c) and an F_p-rational layer (arithmetic, fingerprinted, remembered: Per_p(phi), the Frobenius fixed-point count). We prove: the dynamic Lehmer constant L_dyn = h_{x^2+1}(0) = 0.203677261369740... (a complete minimization proof over Q); the three-axis separation theorem for the splitting family c = (1-m^2)/4 (amplitude = 2 is a free fingerprint carried entirely by the n = 1 layer; alpha = 0.5 is a theorem for all m >= 5; the Jensen gap J has no m-dependence and separates the monomial and Chebyshev cases that the scale exponent alpha confounds); the sqrt(2) anisotropy of escape near the cusp, A(phi) = |sin(phi/2)|/sqrt(6) (Joukowski coordinates, 15 directions at two scales digit-perfect); the Sha growth law lim_n log_2(Sha_n)/2^n = 2*alpha - 1 with the Stoll mod-square family classified (7/7 separation); the criterion alpha = 1 if and only if disguised group endomorphism, across polynomials and rational maps including both Lattes quotients; and the number-field PCF criterion h(0) = 0 if and only if c in M intersect O_K with all embeddings in M, verified against Baker-DeMarco with a six-field Lehmer table. The universal far-tail rate is identified with the random-mapping class, Phi = (4-pi)/4 = 0.2146, with a quantitative accounting of the PCC contamination that had drifted earlier measurements. All corrections found during the research (including two withdrawn headline predictions) are recorded in an appendix.

Primarily human-written textHuman understanding: all partsarithmetic dynamics,z^2+c,arboreal Galois representation
Nov 03, 202613 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.CO — Combinatorics

Local independent sets and colourings of triangle-free graphs

Contributed by Matthew Bowen, András Máthé, Oleg Pikhurko

This AI-assisted draft constructs, for every sufficiently large DD, a local rule of radius O((ln⁡D)2)O((\ln D)^2) that produces, on any triangle-free graph GG of maximum degree at most DD, a random independent set that includes each vertex with probability at least (1−oD(1))ln⁡D/D(1-o_D(1))\ln D/D. Further properties of the rule yield, for every fixed ε>0\varepsilon>0 and all sufficiently large DD, a randomised LOCAL algorithm that colours any such finite graph GG with at most (1+ε)D/ln⁡D(1+\varepsilon)D/\ln D colours, with high probability, in Oε(ln⁡D)+(ln⁡ln⁡∣V(G)∣)O(1)O_\varepsilon(\ln D)+(\ln\ln |V(G)|)^{O(1)} communication rounds. Applying known transference principles for Borel graphs, we obtain the same asymptotic bound on the number of colours for measurable and Baire-measurable colourings, and for Borel colourings of graphs with finite asymptotic separation index.

Primarily AI-generated textHuman understanding: some partsChromatic numberLOCAL algorithmdescriptive combinatoricsindependent settriangle-free graphs
Oct 31, 202629 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

Improved basis-change transformations for 2×22 \times 2 matrix multiplication

Contributed by Hugo Nielsen

To the best of our knowledge, we present a state-of-the-art change-of-basis algorithm for 2×22 \times 2 matrix multiplication under the Karstadt--Schwartz-style basis change regime [1]. We do this by introducing basis-change matrices BUB_U, BVB_V, and BWB_W that each require only a single addition and hence give rise to a matrix-multiplication algorithm performing 5nlog⁡27−4n2+34n2log⁡2n,5n^{\log_2{7}} - 4n^2 + \frac{3}{4}n^2 \log_2{n}, arithmetic operations when multiplying two n×nn \times n matrices, with nn a power of 22. This improves on the previous best bound, which had last term 32n2log⁡2n\frac{3}{2}n^2\log_2{n}.

Primarily human-written textHuman understanding: all parts
Oct 31, 20264 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

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.DS — Data Structures and Algorithms

Sorting networks on 13 inputs need 45 comparators

Contributed by Tejasvi Singh Tomar

Let S(N)S(N) be the least number of comparators in a sorting network on NN inputs (the Bose--Nelson problem). The values are known for N≤12N\le12, and for 1313 inputs the smallest known sorting network, found by Juill\'e, has 4545 comparators. We prove S(13)≥45S(13)\ge45, so S(13)=45S(13)=45. Deleting the comparators met by the largest and the second largest input leaves a sorting network on N−2N-2 inputs, so S(N)≥S(N−2)+P(2,N)S(N)\ge S(N-2)+P(2,N), where P(2,N)P(2,N) is the least possible worst-case number of comparators met by these two values. Van Voorhis stated P(2,N)≥⌈lg⁡F(N)⌉P(2,N)\ge\lceil\lg F(N)\rceil for an explicit function FF, but Mericanii showed that his proof is invalid. We prove P(2,N)=⌈lg⁡F(N)⌉P(2,N)=\lceil\lg F(N)\rceil for 3≤N≤323\le N\le32 by a finite search, which rests on the structure of the tree of paths of the largest value, the comparators on these paths, and a forest of comparators that carries the second largest value. With S(11)=35S(11)=35 this bound gives only S(13)≥44S(13)\ge44. For 4545 we apply it to the suffix of a network: if a network with LL comparators sorts a set XX of 00-11 vectors, then for suitable pairs of inputs the two values meet at most L−cL-c comparators, where cc is the cost of sorting the residual set left when their paths are deleted. A breadth-first search over the sets produced by prefixes of a hypothetical sorting network with 4444 comparators discards each set for which no single network stays within all these budgets, and no set survives at depth 2525. A separate verifier checks the certificate written by the search. Two proofs in Lean 4 check the same certificate, and in one of them Lean's kernel checks every computation, with only the standard axioms. Juill\'e's network is checked in the kernel as well. As a consequence, each of the twenty lower bounds on S(N)S(N) for 13≤N≤3213\le N\le32 that rested on Van Voorhis's inequality is proved and raised by one.

A mix of human-written and AI-generated textHuman understanding: all parts
Oct 26, 202647 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.MS — Mathematical Software

Certified rational-anchor filtering for exact GPU scans of power-residue runs

Contributed by Brice Pouly

We study exact longest monochromatic runs of power-residue colourings, including neutral prefixes and least canonical witnesses. A certified rational cover represents every relevant interval inside a short signed character table. A reflection-compatible schedule retains an anchor; conservative filters reject only known contradictions, bilateral completion recovers the full run, and tie-preserving reduction selects its least witness. We prove this exact-success contract and describe its CUDA realization with separate arithmetic domains below 2322^{32} and 2332^{33}. On one RTX 5090, two reserved cohorts give ratios 24.0024.00 and 10.9510.95 of sums of hot per-prime medians against the identified historical dense engine. A separate batch study gives throughput factors 1.231.23-2.582.58 against an already optimized reference. The experiments have different timing boundaries and their factors are reported separately. Short-table multiplicative extraction has close algorithmic antecedents in cryptanalysis; our contribution is its certified organization for exhaustive maxima and witnesses and its measured implementation. Square-root-sized cover parameters do not give a general O(p)O(\sqrt p) running-time bound.

Primarily AI-generated textHuman understanding: no partsCUDANVIDIA RTX 5090SM120certified algorithmsexact GPU scansmultiplicative characterspower-residue runsrational-anchor filtering
Oct 20, 202621 pages
PDFView work

math.OC — Optimization and Control

Additive Rounding for LP-Tight Three-Item Bin Packing

Contributed by Ruixue Yuan, Da Teng, Zhenyu Sun

We consider bin-packing instances with 3m3m items of sizes in (1/4,1/2)(1/4,1/2), total size mm, and configuration linear programming value mm. Let dd be the relative dimension of the polytope of zero-sum multiplicity patterns obtained by centering sizes at 1/31/3. We determine the maximum additive integrality gap for every d≤10d\le10. It is zero for d≤4d\le4 and one for 5≤d≤105\le d\le10. More generally, a representation of the multiplicity vector by at most five zero-sum patterns admits an integral packing, and a representation by at most eleven patterns requires at most one additional bin. The integral-packing result has a structural proof; the additive-one result combines structural restrictions with exact finite enumeration. For arbitrary dd, we construct an LP-tight subinstance with at most 6d+36d+3 items and no smaller additive gap. An integer representation preserving the signs of triple sums then yields a finite rational family attaining the worst gap, which is computable in time 2O((d+1)2)2^{O((d+1)^2)}. Finally, we construct a sharp family with simplex pattern polytopes and a linearly growing zero-sum matching deficit. Its eleven-dimensional member violates the zero-sum remainder condition used in the ten-dimensional proof. Thus the bound of eleven fractional patterns in that condition is sharp.

Primarily human-written textHuman understanding: all partsbin packingconfiguration linear programminghypergraph matchinglattice polytopeszero-sum patterns
Oct 20, 202618 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.DS — Data Structures and Algorithms

Diameter-Free Pointwise Gaussian KDE in Near-Additive Query Time

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

Wagner asked whether Gaussian kernel density estimation in Rd\mathbb R^d admits query time O~(d+ε−2)\widetilde O(d+\varepsilon^{-2}) without dependence on the diameter of the data. We answer this affirmatively for each fixed query: a randomized data structure answers a query to additive error ε\varepsilon with probability 1−δ1-\delta in time O((d+ε−2)log⁡(d+1)log⁡(2/δ))O((d+\varepsilon^{-2})\log(d+1)\log(2/\delta)), independently of the number of data points and of their diameter. The key ingredient is a variance bound for a Fastfood-type structured Fourier block that holds uniformly in the norm of the displacement.

Primarily AI-generated textHuman understanding: some partsFastfoodGaussian kernel density estimationpointwise approximationrandom Fourier featuresstructured random features
Oct 15, 202610 pages
PDFView work

cs.DM — Discrete Mathematics

Fractional DAG treewidth controls DAG treewidth: profile reorientation and VC-dimension rounding

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

For a nonempty finite graph, let FF be its fractional DAG treewidth, maximized over all acyclic orientations. Its DAG treewidth is at most 160F3ln⁡(16F)160F^3\ln(16F). This answers the boundedness question of Bressan, Lanzinger, and Roth. Reorienting the graph converts shattered source profiles into projective-plane obstructions, which bound their VC dimension by 5F25F^2. Classical epsilon-net rounding then converts fractional bag covers to integral ones without changing the decomposition.

Primarily AI-generated textHuman understanding: some partsDAG treewidthVC dimensionepsilon netsfractional hypertreewidthgraph homomorphisms
Oct 15, 202610 pages
PDFView work

cs.DS — Data Structures and Algorithms

Subset Sum in time O(2^{0.4877n})

Contributed by Annanay Kapila

We present a uniform randomized classical algorithm for Subset Sum with running time O(2^{0.4877n}) in the word-RAM model, for inputs whose integer bit lengths are polynomially bounded in the number n of input integers. The algorithm halts on every execution and answers correctly with probability at least 2/3. The construction builds on OpenAI’s “Subset Sum in Time O(2^{0.49n})” (4 October 2026), retaining its framework of isolation, a capped preliminary search, a modular checksum, and alias subtraction. Two components are replaced: an alias procedure that computes phase sums using a smaller modulus, and a family of 43 checksum filters selected according to the input pattern. The analysis combines an averaged small-layer lemma, grouping by reduced and unreduced subset sums, and rigorous numerical certificates. Verification scripts using Arb ball arithmetic check the alias constraints and 430 moment inequalities. The argument relies on results from the earlier paper, which are restated in an appendix; the numerical certificates verify specified inequalities rather than formally verifying the entire proof.

Primarily AI-generated textHuman understanding: some partsSubset Sumcomputational complexityexponential-time algorithmsrandomized algorithmsrigorous numerics
Oct 15, 202628 pages
PDFView work

cs.DS — Data Structures and Algorithms

Deterministic Integer 3SUM in O(n^1.999017) Time via a Sharper Binomial-Tail Analysis

Contributed by 宇轩 徐

We refine the analysis of the deterministic integer 3SUM algorithm of Alman and Vassilevska Williams (arXiv:2610.06783v1). Within their framework of thin matrix products and reductions through Exact Triangle, we obtain a worst-case running time of O(n^1.999017) for polynomially bounded integer inputs on a word RAM with O(log n)-bit words. The main refinement retains the binomial tail in the preprocessing cost instead of replacing it immediately by a uniform geometric bound. An entropy estimate yields a strictly larger preprocessing saving exponent, while preserving the query algorithm and its complexity. With explicit rational parameters c = 21, theta = 0.11202, a = 0.05665, and s = 0.06945, the resulting 3SUM exponent is 1.999016414375 + o(1), giving the stated fixed exponent with a positive margin. Separately, retuning the existing analysis without the tail refinement gives O(n^1.999073). We account for encoding, queries, prime selection, instance construction, witness scanning, and parameter rounding. The numerical inequalities are certified using exact rational interval arithmetic with explicit logarithm remainder bounds. Independent computations provide additional consistency checks. The contribution is a refinement of an existing algorithmic analysis, rather than a new matrix multiplication construction or reduction. No complete Lean formalization of the improved running-time bounds is claimed, and no global optimality or priority claim is made.

Primarily AI-generated textHuman understanding: no parts3SUMExact Trianglebinomial tailscomputer-assisted analysisdeterministic algorithmsfine-grained complexitythin matrix products
Oct 13, 20268 pages
PDFView work

cs.DS — Data Structures and Algorithms

From Snapshots to Processes: Dynamic Contact Algebras as a Foundation for Process-Oriented GIS

Contributed by John Hessler

Geographic information science has argued for three decades that representing change requires moving from time-stamped snapshots to events and processes. This ontological shift has not been matched by a formal foundation with the properties a GIS needs: explicit axioms, representation theorems, and decidable reasoning. We propose dynamic mereotopology, in the form of Vakarelov’s dynamic contact algebras (DCAs), as a candidate foundation. DCAs are point-free with respect to both space and time. Regions are histories, primitive relations include space contact, time contact and precedence, moments are recovered as clusters of the time-contact relation, and properties of time correspond to axioms about regions alone. Using Grenon and Smith’s distinction between SNAP (snapshot) and SPAN (process) ontologies, we argue that DCAs originate on the SNAP side, since they are abstracted from a snapshot model, yet their primitives already carry much of what a SPAN ontology requires. We then identify precisely what is still missing for a process-oriented GIS: process and participation primitives, continuity of change, freedom from global simultaneity, identity under splitting and merging, and granularity. We develop a SPAN-first extension. For two of its components we give full proofs: a point-free continuity axiom, shown to express exactly the intended condition in discrete time and in finitely variable dense time, and a set of correspondences showing which axioms of continuous space hold at every finite resolution of discrete data and which emerge only in the limit of refinement. The remaining proposals are stated as conjectures, and the framework is tested against three case studies: a flood, a wildfire, and a pandemic.

A mix of human-written and AI-generated textHuman understanding: all partsdynamic mereotopology; contact algebra; boolean algebra
Oct 09, 202627 pages
PDFView work

cs.DS — Data Structures and Algorithms

A Lean Certificate for the Single Source Unsplittable Flow Cost Counterexample

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We explain a standalone Lean 4 and Mathlib verification of the finite counterexample announced by Dmitry Rybin to the cost-preserving single-source unsplittable-flow conjecture. The instance has seven vertices, nine directed arcs, and three terminal demands. An exact rational path flow saturates every arc, has cost 58, and has largest demand 15. Exhaustive graph-path classification reduces every unsplittable routing to two choices per terminal. Three backbone-arc inequalities force any routing with load at most the fractional load plus 15 to use at least two paid routes, each costing 30. Thus every such routing costs at least 60, ruling out cost preservation even with a non-strict congestion bound. We present the numerical certificate, its graph realization, and the boundary between the pinned proved implementation and its statement-only verification interface. The contribution is an exposition of a source-based formal certificate; no new counterexample, first formalization, or general rounding algorithm is claimed.

Primarily AI-generated textHuman understanding: some partsGoemans cost conjectureLean 4MathlibRybin counterexamplefinite counterexampleformal verificationsingle-source unsplittable flow
Oct 01, 20266 pages
PDFView work

cs.DS — Data Structures and Algorithms

Deferred Acceptance in Lean for Finite Strict Preference Markets

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We describe a Lean 4 development of men-proposing deferred acceptance for finite one-to-one markets with complete strict preferences and optional partners. The two sides may have different cardinalities; the principal theorems assume a nonempty receiving side. A proposal-set measure proves termination of a specified, classically chosen run. Reachability invariants establish consistency of the resulting partner maps, stability, and the fact that a rejected proposal cannot be a stable-achievable partnership. The public optimality theorem is conditional on a man receiving a partner; an internal lemma separately excludes stable-achievable partners for men unmatched at quiescence. We give mathematical proofs corresponding to the source architecture, identify the precise theorem interface, and separate fresh source inspection from the repository's reported build and axiom audit. This is an exposition of a pinned formalization of classical results, with no claim of new matching theory or priority of formalization.

Primarily AI-generated textHuman understanding: some partsGale-ShapleyLean 4deferred acceptanceformalizationstable matching
Sep 30, 20267 pages
PDFView work

cs.CC — Computational Complexity

Generalized Bawo: A Finite-State Model and an EXPTIME Upper Bound

Contributed by Isaac kaimfa

Four-row mancala games, including Malawian Bawo and the related East African Bao, have received limited attention in computational complexity theory despite their combinatorial richness. This paper introduces GENERALIZED-BAWO-WIN, a finite-state two-player game model inspired by Malawian Bawo. The model is parameterized by a half-board width n and a binary-encoded lap cap L, and incorporates relay sowing, marker-pit capture, a formalized capture-relay rule (abstracting kichwa), mandatory capture, a singleton-start prohibition, and an explicit lap-cap truncation rule that guarantees move termination. We prove that GENERALIZED-BAWO-WIN belongs to EXPTIME under these semantics. The proof proceeds by establishing that the game's state space has size at most 2poly(|I|), that legal successors can be generated in 2poly(|I|) time, and that a WIN/LOSS/DRAW retrograde attractor can be computed over the resulting finite game graph. We emphasize that this is an upper bound: no hardness result is established. We further emphasize that the theorem applies only to the formally defined generalized model and does not classify Bao as played in East Africa, whose rules differ materially.

A mix of human-written and AI-generated textHuman understanding: all partsEXPTIMEcombinatorial gamescomputational complexityfinite gamesgeneralized Bawostate-space complexity
Sep 28, 202612 pages
PDFView work