Let S(N) be the least number of comparators in a sorting network on N inputs. We prove S(13)≥44, one more than the previously best proved lower bound. We also prove P(2,N)=⌈log2F(N)⌉ for 3≤N≤32, where 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 F 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)=35 and S(12)=39, these values of P(2,N), the two-value bound S(N)≥S(N−2)+P(2,N) and the one-value bound S(N)≥S(N−1)+⌈log2N⌉ give the twenty lower bounds on S(N) for 13≤N≤32 in Dobbelaere's table; these bounds rested on Van Voorhis's inequality P(2,N)≥⌈log2F(N)⌉, whose published proof is invalid. The bound S(13)≥44 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
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ε vertices for a small ε. Majdoddin extended the method to every ε<ln4/(5ln5)≈0.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 when the prescribed edges are known in advance and there are at most n2−ε/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
We study (t,n)-selection networks, which move the t largest of n inputs to t given lines in any order, and the least number U^t(n) of comparators in such a network. Alekseev showed that U^t(n)≥(n−t)⌈lg(t+1)⌉. For t=2k≥4 we raise this bound by k−1 for every n>t, and by 2k−5 when t≥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≥3. For t=3, Yao's upper bound 2n−5+⌊lg(n−3)⌋ is exact for 4≤n≤18. For t=4 the new bound is 3n−11 for all n≥5, and the value 3n−10 that Knuth expected is exact for 6≤n≤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
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))nlog2n comparisons. The best previously known deterministic polynomial-time adversary forced 6437nlog2n 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
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/2. In October 2026 that barrier fell twice within a week, with OpenAI's 20.49n algorithm and, independently, Li and Ye's 2(1/2−1/450000)n≈20.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.4875754036: for every fixed T′>T, the uniform randomized algorithm uses O(2T′n) word operations on inputs of polynomial bit length, with success probability at least 2/3. In particular, it runs in time O(20.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 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))n alias classes, spending a counted step on each, and uses checksum gap at most Δ needs exponent at least (1−Δ)/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.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
In October 2026 OpenAI and Anthropic each claimed a deterministic subexponential algorithm for counting the solutions of a k-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 U 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×2 grid and of the full 3×3 grid level have flattening-rank sums at least N2, N3 and N8, while N9 is open; the row cut of the permanent has rank (kn), which on paper gives U≥nlog2(n/s) for row-local networks; algebras in which the permanent is a functional of a product have dimension at least (n/2n); pieces have saving ρ≥1/2 (rank form; Anthropic's observation); and exact colouring filters for Hamiltonicity need q≥n−4 colours. On paper we prove U≥(1−o(1))nlog2n for vertex-local networks for the Tutte polynomial off the integer hyperbolas, and ρ≥3/8 for correlated decompositions of full grid levels. We cite 45 Lean theorems, with standard axioms only. Every barrier is about a named model: in Anthropic's general model no unconditional bound on U exists without separating P from P#P, and an unconditional cap on oblivious algebraic algorithms would separate VP from VNP.
Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisSATTutte polynomialcorrelated decompositionscut rankengine barrier problemtensor networks
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 κ-local task families with N-bit descriptions under the uniform prior, the posterior predictive and posterior sampling reduce to #κ-SAT. Without label noise they run in time poly(m)⋅2o(N) on contexts of every length m when κ=o((logN)1/4/loglogN), 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) for a CNF F. So approximating the posterior predictive within 1/4 needs time 2(1−γ)N at locality O(logN) under CNF-SETH, and time 2N/polylogN at locality 3 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 N-bit descriptions is at most N/(m+1) after m 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 κ-local family is linear over ∑j≤κ(jN) local Fourier features, so regression in context learns it from NO(κ) examples, in time polynomial in Nκ and the inverse accuracy.
The average case. For Goldreich's random local functions, the Bayes risk is at most 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/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/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
Alman and Song showed that attention with head dimension O(logn) can be approximated in almost linear time when the entries are o(logn), and needs quadratic time at Θ(logn) 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 clogn (LDOV), which no open hypothesis about satisfiability is known to imply. We measure an instance by its spread W, the largest gap between two logits of a row. At every nontrivial constant precision and in every dimension between ω(logn) and no(1), we show that under LDOV the time exponent of attention is exactly 1+min{W/lnn,1}: uniform sampling of keys is optimal, the cost is min{neW,n2} up to factors no(1), and the transition to quadratic time sits at W=lnn, the spread at which one key can outweigh all others. At polynomial precision and in dimension O(logn) the threshold becomes Θ(logn), with a constant that tends to zero as the precision grows, and the dimension moves it: at precision n−1−O(1/loglogn), spread O(logn/loglogn) is hard in dimension (logn)1+Ω(1) but easy in dimension O(logn). From satisfiability we obtain hardness at spread (1+θ)lnn in dimension no(1), provided the hard CNF formulas have Nc0 clauses for some c0<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<2 for every such protocol. For the entry bound, every reduction that embeds Orthogonal Vectors vector by vector, with polynomial blowup and logit gap Ω(logn), yields a Merlin–Arthur protocol for disjointness; by Klauck's lower bound, such reductions cannot derive B=Θ(logn) from Orthogonal Vectors in dimension (logn)1+Ω(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
Computing the prime-counting function π(x) exactly takes x1/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+c near x contains an odd number of primes in time x1/2−c+o(1). However, their identity needs the Mobius function μ(d) for all d≤x, and we know of no bound of the form xo(1) for the parity, even conditionally. We present deterministic algorithms that output π(x)mod2 and the parity of the number of primes in any interval [A,B] in time 2O(n/logn)=xo(1), where n is the input bit length. Our approach replaces μ(d) by its residue modulo 2, which is the squarefree indicator again: the number of chains d12∣m, d22∣d1,… of depth L is odd exactly when m is squarefree, for m<22L. The parity of π on [A,B] is then the parity of one count of tuples satisfying O(logn) 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): 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
Basic counting problems of computational number theory have proven deterministic bounds that are fixed powers of the input. The class number h(D) of an imaginary quadratic discriminant takes ∣D∣1/2+o(1) steps unconditionally and ∣D∣1/5+o(1) under the generalised Riemann hypothesis (GRH); exact divisor sums ∑m≤xτ(m) take x1/3+o(1). However, none of these bounds is of the form Xo(1), even conditionally. We present deterministic algorithms in time 2O(n/logn), where n is the input bit length, for the number of reduced forms of discriminant −N (for fundamental discriminants, h(−N)) and for ∑m≤xτ(m), ∑m≤xσ(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) shared bits. The same library gives the least square root modulo any m 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 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/log2(n+2)⌋ 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
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⟩ of a Clifford+T circuit with G two-qubit gates in arbitrary connectivity exactly, as an element of Z[ω]/2k with ω=eiπ/4, in time 2O(G/logG) whenever the input length L satisfies logL≤G0.9. The proof reads the sum over paths, one bit per wire segment, as an Anthropic-type network, with a Kronecker map for Z[ω] 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-d circuits in 2O(dn/logn), and, through OpenAI's tensor-contraction theorem, polynomial space when the number of Hadamard-type gates is O(G). Conversely, constant-depth circuits with O(n) gates encode #3-SAT with 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.
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), where m 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 G are in bijection with the Hamiltonian cycles of the line graph of the double subdivision of G, which has 3m vertices and at most (Δ+1)m edges. We prove in Lean 4 (theoremEuler, theoremEuler_noIso, theoremEuler_rate; axioms propext, Classical.choice, Quot.sound) that for every δ>0 and Δ a finite-alphabet Mathlib Turing machine outputs the number of Eulerian circuits of every graph of maximum degree at most Δ within ⌊C(n+2)C2δm⌋ steps, and within ⌊C2δm⌋ steps when there is no isolated vertex; and that one machine does so for all graphs within ⌊C(n+2)C2Cmlog2(Δ+2)/log2(m+2)⌋ steps. The factor (n+2)C pays for reading the n2-bit adjacency matrix and cannot be dropped. The bijection is checked by brute force on twelve small graphs, for example 132 circuits for K5. 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.
The subsets of {1}∪{p≤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) on the unit circle and follow one object, the arc at a rational a/q, through three settings.
For the primes, the centre of the arc a/q rises above the sea of the minor arcs exactly when q=2k(k≥2) or q=2pj, with excess Λ(q/2)/φ(q), and the neighbourhoods of all the other arcs are bounded uniformly in q; Theorem E gives the expansion arc by arc. The height of an arc is a race of the primes modulo q with weights log∣cos(π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=8, 10 and 14, where the zero-free segments it needs are certified; at q=14 the race changes sign infinitely often. The principal arc carries ζ 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 b bits the method has rigorous guarantees, in time 2b/2+o(b) and, with the filter, 2b/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∘Tstruct.
A mix of human-written and AI-generated textHuman understanding: some partsDirichlet L-functionsGRHSubset Sumcircle methodconstraint propagationlocal limit theoremmeet-in-the-middleprime races
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
Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník
Continuous Ulam Metric k-Center asks for at most k permutations whose radius-d balls cover the input rankings. For m rankings of n symbols, a deterministic algorithm takes 2O(kdlog(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(dlogd) exclusion under the Exponential Time Hypothesis.
Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisUlam distancecontinuous k-centerparameterized algorithmspatience sortingrank aggregation
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/3, and Chen et al.\ asked whether 2/3 is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a 1/2-approximation using O(nlog(n+1)+mlog(m+1)) arithmetic and comparison operations for n items and m knapsacks, and prove that no fixed ratio above 1/2 is achievable unless P=NP. We also give a short proof of the classical 1/2 guarantee of Friesen and Langston for unit profits.
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=NP, this cost admits no polynomial-time O(N1/2−η)-approximation for any fixed 0<η<1/2, even on connected N-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
The Minimum Independent Dominating Set problem asks for a smallest maximal independent set of a graph. Unless P=NP it is not approximable within n1−ε for any ε>0; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within δB on bipartite graphs of maximum degree B. 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⌋ 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) expected time, with ratio at most Δ, optimal on forests, and with ratio at most n on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most ⌊n⌋(i(G)+s(G)) on every graph, for an explicit splitting excess s(G), and the output satisfies the same bound when the decoded set is independent. The excess is at most n(n+1), largest on complete graphs, zero for n≥D2 on every family of bounded degree D, among them the NP-hard and UG-hard bounded-degree families, and O(n) on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio O(n) on all graphs; a proof would imply P=NP. In a reduction from satisfiability, every independent dominating set of the graph of a formula with N variables and t copies of every clause, t at least the largest clause width W, is a satisfying assignment, with N vertices, or has at least t+N vertices; with t=W, every independent dominating set of ratio smaller than 1+W/N is a satisfying assignment. This proves the n1−ε 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 H into a graph h(H) with i(h(H))=τ(H)+2∣E(H)∣, where τ(H) is the minimum vertex cover size, every output on h(H) decodes into a vertex cover of H; 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 9999 of 10000 graphs with an exact integer-program optimum, on all 95 of 112 bipartite graphs whose optimum was proved, on all 18 instances of the set cover reduction, and on 2 of the 30 instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between 1.25 and 1.8665. We also report the results on the 68 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
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
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−ε for every ε>0, and under the Unique Games Conjecture it is hard to approximate within O(Δ/log2Δ) on graphs of maximum degree Δ; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a (2−ε)-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)-improvements, and an iterated (1,2)-swap search. We prove that it runs in O((n+m)αA(n)) expected time for fixed budgets, with αA the inverse Ackermann function. We prove that the output is a maximal independent set, that its complementary vertex cover has at most 2τ−r vertices, where τ is the minimum cover size and r the number of components with an edge, and that the ratio is at most (Δ+2)/3 on graphs of maximum degree Δ. We prove the ratio 2n on every graph with Δ≤n and on three further classes, and state it for all graphs as a conjecture, whose proof would imply P=NP. We also state the conjecture that the complementary cover has at most 2τ−∣M∣ vertices for the NetworkX minimum maximal matching M; a proof would give a 3/2-approximation for Minimum Vertex Cover and refute the Unique Games Conjecture unless P=NP. In reproducible experiments the returned set is optimal on all 30000 graphs of a suite certified by an exact integer program; on 40 Khot--Regev YES instances with 640 to 2560 vertices the conjectured bound is certified on 38 and open on 2; and on 31 bounded-degree graphs the certified ratio is at most 1.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
Contributed by Matthew Bowen, András Máthé, Oleg Pikhurko
This AI-assisted draft constructs, for every sufficiently large D, a local rule of radius O((lnD)2) that produces, on any triangle-free graph G of maximum degree at most D, a random independent set that includes each vertex with probability at least (1−oD(1))lnD/D. Further properties of the rule yield, for every fixed ε>0 and all sufficiently large D, a randomised LOCAL algorithm that colours any such finite graph G with at most (1+ε)D/lnD colours, with high probability, in Oε(lnD)+(lnln∣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.
In October 2026 two manuscripts claimed refutations of the Exponential Time Hypothesis by deterministic algorithms for #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 n vertices and at most Dn edges can be computed exactly and deterministically in time O(2δn) for every δ>0, and in time 2O(max(m,n)/logn) for a graph with m edges. A rank-encoded variant of the construction gives 2O(nlogdˉ/logn) for average degree 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 2-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) bits per edge through a Grassmann determinant whose only non-local part is a sign, and that this sign costs only O(g3) bits for g blobs, so the whole construction is a network in the sense of the manuscript, whose value is n⋅#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) for every graph in time 2O((m+n)/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.
To the best of our knowledge, we present a state-of-the-art change-of-basis algorithm for 2×2 matrix multiplication under the Karstadt--Schwartz-style basis change regime [1].
We do this by introducing basis-change matrices BU, BV, and BW that each require only a single addition and hence give rise to a matrix-multiplication algorithm performing 5nlog27−4n2+43n2log2n, arithmetic operations when multiplying two n×n matrices, with n a power of 2. This improves on the previous best bound, which had last term 23n2log2n.
Primarily human-written textHuman understanding: all parts
Two recent works by OpenAI and Anthropic refuted the Exponential Time Hypothesis (ETH). They count the satisfying assignments of a k-CNF on n variables in time 2n/(logn)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 Θ(logN) bits. Three transitions make the principle precise.
Locality. Call a class with N-bit descriptions κ-local if each label depends on at most κ 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) on samples of size m for κ=o((logN)1/4/loglogN), and proper PAC learning at constant accuracy does so for κ=o(logN). At inverse-polynomial accuracy, proper learning of κ-local classes is equivalent to κ-SAT, up to a factor 2 in the locality. Under CNF-SETH, consistency for binarized perceptrons on O(logN)-sparse data needs time 2(1−γ)N for every γ>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/polylogN lower bound under a length form of ETH, which replaces Gap-ETH for reductions of quasi-linear size. At accuracy N−3/8, the Max-3-SAT Hypothesis forces time 2(1−o(1))N.
Treewidth. Exact inference in graphical models of bounded degree and arity takes time 2O(n/logn). On expanders this beats every elimination order and every structured DNNF. Under #CNF-SETH, time 2(1−γ)tw is again necessary once a model may have twO(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 k-Subgraph on bounded-degree graphs is false. The next obstacle is a permutation problem. On difference vectors ei−ej, 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
Contributed by Isaac Rudich, Louis-Martin Rousseau
The current best upper bound for deterministic factoring is N1/5+o(1). We provide a Lean certificate that there exists a deterministic Turing machine that computes the smallest prime factor of every N in No(1) steps: for every k≥1 it runs within Ck2n/k steps on n-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
The deterministic algorithm of \oai{} that counts the satisfying assignments of a k-CNF in time 2o(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) algorithms for exact Max-Cut and Max-k-SAT on sparse instances, for the independence polynomial, the maximum independent set and the knapsack problem with a conflict graph on every graph, for 0-1 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, for the minimum distance and the maximum-likelihood decoding of codes with sparse parity checks, for Max-Cut and Max-k-SAT at every average degree o(logn/loglogn), for Max-Cut on dense graphs close to blow-ups of graphs with o(n/logn) 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
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, 3-SAT on n variables with m clauses can be decided in time Oε(2ε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
Let S(N) be the least number of comparators in a sorting network on N inputs (the Bose--Nelson problem). The values are known for N≤12, and for 13 inputs the smallest known sorting network, found by Juill\'e, has 45 comparators. We prove S(13)≥45, so S(13)=45. Deleting the comparators met by the largest and the second largest input leaves a sorting network on N−2 inputs, so S(N)≥S(N−2)+P(2,N), where P(2,N) is the least possible worst-case number of comparators met by these two values. Van Voorhis stated P(2,N)≥⌈lgF(N)⌉ for an explicit function F, but Mericanii showed that his proof is invalid. We prove P(2,N)=⌈lgF(N)⌉ for 3≤N≤32 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)=35 this bound gives only S(13)≥44. For 45 we apply it to the suffix of a network: if a network with L comparators sorts a set X of 0-1 vectors, then for suitable pairs of inputs the two values meet at most L−c comparators, where c 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 44 comparators discards each set for which no single network stays within all these budgets, and no set survives at depth 25. 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) for 13≤N≤32 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
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
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 232 and 233. On one RTX 5090, two reserved cohorts give ratios 24.00 and 10.95 of sums of hot per-prime medians against the identified historical dense engine. A separate batch study gives throughput factors 1.23-2.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) running-time bound.
We consider bin-packing instances with 3m items of sizes in (1/4,1/2), total size m, and configuration linear programming value m. Let d be the relative dimension of the polytope of zero-sum multiplicity patterns obtained by centering sizes at 1/3. We determine the maximum additive integrality gap for every d≤10. It is zero for d≤4 and one for 5≤d≤10. 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 d, we construct an LP-tight subinstance with at most 6d+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). 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
Minimum Vertex Cover has a classical linear-time ratio of 2, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 2 unless P=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)) time, and that the returned cover has at most 2τ−r vertices, where r is the number of components with an edge, so the ratio is at most 1.999999999 whenever τ≤109r. 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∣ vertices, for a lower bound L≤τ and the maximal matching M, is within ratio 3/2 on that instance. In a reproducible suite the returned cover satisfies ∣C∣≤2τ−∣M∣ on all 291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 68 DIMACS clique complements it is never worse than Hvala and optimal on 37 instances against 18. Whether ∣C∣≤2τ−∣M∣ holds on every graph is stated as a conjecture: a proof would give a linear-time 3/2-approximation and would refute the Unique Games Conjecture unless P=NP.
Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBipartite LayersEnsemble HeuristicsLinear TimeMaximal MatchingP versus NPSplit GraphUnique Games ConjectureVertex Cover
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 admits query time O(d+ε−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 ε with probability 1−δ in time O((d+ε−2)log(d+1)log(2/δ)), 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
Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník
For a nonempty finite graph, let F be its fractional DAG treewidth, maximized over all acyclic orientations. Its DAG treewidth is at most 160F3ln(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 5F2. Classical epsilon-net rounding then converts fractional bag covers to integral ones without changing the decomposition.
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.
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.
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
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.
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
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