arXiv weekly literature review

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-05T04:33:07Z
Adam Marton, Jaroslav \v{S}upina, Miroslav Repick\'y, Tristan van der Vlugt
arXiv categories: math.LO

We generalise the $\sigma$-ideal $\mathcal E$ generated by the closed Lebesgue null subsets of the Cantor space ${}^\omega 2$ to the context of higher Cantor spaces ${}^\kappa 2$ for an uncountable cardinal $\kappa$ satisfying $\kappa=\kappa^{<\kappa}$. We introduce candidates for a higher closed null ideal based on slaloms on partitions of $\kappa$ into sets of size ${<}\kappa$, and study their combinatorial properties. We also give some relations between the cardinal invariants of the higher closed null ideals and other cardinal characteristics.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-05T13:26:02Z
Martin Dole\v{z}al, V\'aclav Vlas\'ak
arXiv categories: math.LO

We construct a nonmicroscopic $G_\delta$ subset of the real line all of whose compact subsets are microscopic, answering a question of Zindulka and Nowakowski. We first obtain such a set in the standard Cantor space by coding branches of a finitely branching tree together with suitable choices of marked nodes. The coding of the branches ensures that the resulting set is not microscopic, while the marked nodes allow us to construct covers showing that every compact subset is microscopic. The example is then transferred from the Cantor space to the real line by the binary-expansion map.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-05T17:52:19Z
Dhruv Kulshreshtha, Jamie Tappenden
arXiv categories: math.LO, math.GN

Descriptive set theorists often refer to elements of the Baire space, $\mathcal{N} = {}^\omega\omega$, as ``reals.'' In this expository article, we present mathematical justification for this practice and highlight the advantages of working with $\mathcal{N}$ over $\mathbb{R}$ in the context of descriptive set theory.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-06T00:04:06Z
Zhixing You
arXiv categories: math.LO

We answer a long-standing open question of Woodin by proving that if $\kappa$ is a strongly compact cardinal and $GCH$ holds below $\kappa$, then $GCH$ holds.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-06T15:39:35Z
Tatsuya Goto
arXiv categories: math.LO

Let $\mathcal{N}^h_\Omega$ be the null ideal of the Hausdorff measure constructed by Davies and Rogers. We give a Tukey reduction of $(\mathcal{N}^h_\Omega,\mathcal{N}^h_\Omega,\subseteq)$ to a localization system with finite coordinate sets. It follows that $\mathfrak{v}^\forall_{D,g}\le\operatorname{add}(\mathcal{N}^h_\Omega)$ and $\operatorname{cof}(\mathcal{N}^h_\Omega)\le\mathfrak{c}^\forall_{D,g}$ for some $D, g \in \omega^\omega$. Consequently, we prove the consistency of $\mathfrak{d}<\operatorname{add}(\mathcal{N}^h_\Omega)$ and, separately, $\operatorname{cof}(\mathcal{N}^h_\Omega)<\mathfrak{b}$. Hence the additivity and cofinality of $\mathcal{N}^h_\Omega$ can differ from those of the Lebesgue null ideal. We also show that the finite graphs in the Davies--Rogers construction can be chosen so that $\operatorname{cov}(\mathcal{N}^h_\Omega)\le\operatorname{non}(\mathcal{N}^h_\Omega)$.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-06T18:45:20Z
Ruiyuan Chen, Anush Tserunyan, Robin Tucker-Drob
arXiv categories: math.LO, math.DS, math.GR

We prove that every countable Borel equivalence relation containing a finite index Borel treeable subequivalence relation is Borel treeable. This answers a long-standing question of Jackson--Kechris--Louveau. Our proof is based on a median subalgebra filtration construction on products of trees, together with an extension of the median graph treeing algorithm of Chen--Poulin--Tao--Tserunyan to certain well-behaved increasing unions.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-06T20:33:05Z
Gabriel Fernandes
arXiv categories: math.LO

We give a relative consistency counterexample to the conjecture of Inamdar and Rinot that every regular uncountable cardinal carrying no amenable C-sequence is ineffable in the constructible universe L. The existence of a $\Pi^2_1$-indescribable cardinal is equiconsistent with the existence of a $\Pi^2_1$-indescribable cardinal carrying no amenable C-sequence and not ineffable in L. For every ground-model C-sequence on a weakly compact cardinal $\kappa$, generalized Hechler forcing adds a club D with $D\cap\beta\subseteq C_\beta$ at stationarily many inaccessible indices. We use this capture theorem in an iteration of length $\kappa^+$ after Johnstone's local lottery preparation.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-07T09:04:11Z
Yi Wang
arXiv categories: math.LO

An analytic subring of $\mathbb{R}$ has Hausdorff dimension $0$ or is equal to $\mathbb{R}$, by a theorem of Edgar--Miller and Bourgain. We show that this fails for coanalytic subfields in the constructible universe: if $V=L$, then for every $\alpha\in[0,1]$ there is a proper coanalytic subfield of $\mathbb{R}$ of Hausdorff dimension $\alpha$. In fact there is a single parameter-free $\Pi^1_1$ set $G\subseteq[0,1]\times\mathbb{R}$ whose sections $A(\alpha)$ are such fields, are strictly increasing in $\alpha$, and satisfy $A(\alpha)=\bigcup_{r<\alpha}A(r)$ for $\alpha>0$.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-07T13:49:08Z
Maxim Vishnikin
arXiv categories: math.LO

It is proved that there exists a language $L$ such that its $\omega$-power has infinite rank in the difference hierarchy of open sets. The same holds for the decreasing difference hierarchy of $\Pi^0_2$ sets.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-08T07:46:01Z
Su Gao, Qingguo Li, Hualin Miao
arXiv categories: math.GN, math.LO

In this paper, we first construct a universal quasi-Polish space Y with the property that every quasi-Polish space is homeomorphic to a closed subspace of Y. This gives a hyperspace F(Y) of all quasi-Polish spaces which is itself a quasi-Polish space. We then prove that the collection of all Polish closed subspaces of Y forms a coanalytic, non-Borel subset of F(Y). In particular, this collection is {\Pi}11-complete.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-08T18:31:28Z
Jerzy K\c{a}kol
arXiv categories: math.GN, math.LO

We completely resolve Question~5.3 of Kania's paper \cite{Kania} and establish a more general realization theorem. We show that for infinite cardinals $\mu\leqslant\nu<\kappa<\lambda$, a space with \[ \pc(X)=\mu,\qquad\pcl(X)=\nu,\qquad \pcc(X)=\kappa,\qquad\pcd(X)=\lambda \] exists if and only if $\kappa\leqslant2^\mu$. The witnesses may be zero-dimensional and Tychonoff spaces, of the least possible cardinality $\lambda$. They may have the least possible number of non-isolated points, or alternatively be crowded. The main ingredient is an exact computation of the centered local $\pi$-character of star filter spaces in terms of ultrafilter character, obtained from a finite selection lemma for filter pushforwards. We also construct a single space with countable $r$-linked local $\pi$-bases for every finite $r$, centered value $\omega_1$, and any prescribed decreasing value greater than $\omega_1$.

arXiv abstract · PDF

Descriptive Set Theory and Cardinal Invariants · primary corpus · published 2026-10-09T13:06:53Z
Cecelia Higgins, Pieter Spaas, Sofia Torelli
arXiv categories: math.LO, math.CO, math.OA, math.SP

We continue the systematic study initiated in arXiv:2602.05185 of the relationship between the spectral theory and descriptive combinatorics of bounded-degree Borel pmp graphs, particularly in the non-regular setting. We first adapt a classical result of Nikiforov to give a new spectral lower bound on the approximate measurable chromatic number. For certain non-regular graphs, this bound improves on the approximate measurable version of Hoffman's classical bound established in arXiv:2602.05185. Next, we strengthen a characterization in arXiv:2602.05185 of approximate measurable bipartiteness in terms of the spectrum of the adjacency operator by generalizing to the case of non-regular graphs. Finally, we introduce the measurable domination number and adapt several classical results of Lu, Liu, and Tian to give a bound on the spectral gap of the Laplacian operator in terms of the measurable domination number.

arXiv abstract · PDF

Finite Structures and Homomorphism Theory · primary corpus · published 2026-10-05T10:38:58Z
Juan P. Aguilera, Martina Iannella
arXiv categories: math.RA, math.LO

We study finite Laver algebras, the generalizations of Laver tables on sets of cardinality not of the form $2^n$. We characterize the conditions under which projections and embeddings between Laver algebras exist and show that there are $2^{\aleph_0}$ pairwise non-isomorphic direct limits of finite Laver algebras.

arXiv abstract · PDF

Finite Structures and Homomorphism Theory · primary corpus · published 2026-10-05T16:50:46Z
Aris Papadopoulos
arXiv categories: math.CO, math.LO

In this note, we prove a stronger version of the K\H{o}v\'ari-S\'os-Tur\'an theorem for partition-wise $k$-stable $r$-hypergraphs. More precisely, we show that for every $k,r\in\mathbb{N}_{\geq 2}$ there is $\eta=\eta(r,k)>0$ such that if $H=(V;E)$ is a partition-wise $k$-stable $r$-uniform $K^{(r)}_{t,\ldots,t}$-free hypergraph with $|V|=n$, then $|E| = O_{r,k,t}(n^{r-\eta})$. Crucially, $\eta$ is independent of $t$. The proof follows the pseudofinite regime used by Chernikov and Starchenko to prove an analogous version of Erd\H{o}s-Hajnal for stable hypergraphs.

arXiv abstract · PDF

Finite Structures and Homomorphism Theory · primary corpus · published 2026-10-06T08:05:23Z
Josse van Dobben de Bruyn, J\'er\'emie Marqu\`es, David E. Roberson, Tim Seppelt, Gian Luca Spitzer, Peter Zeman
arXiv categories: math.CO, cs.DM, cs.LO

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if, for every graph $F \in \mathcal{F}$, the number of homomorphisms from $F$ to $G$ is equal to the number of homomorphisms from $F$ to $H$. Lov\'asz (Acta Mathematica Academiae Scientiarum Hungarica, 1967) showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs. Subsequently, homomorphism indistinguishability relations of a long list of natural graph classes have been equated with natural graph isomorphism relaxations. Given the wealth of such results, Atserias, Kolaitis, & Wu (LICS 2021) asked for an axiomatic characterisation of homomorphism indistinguishability relations. By exhibiting topological and geometric structure associated with homomorphism indistinguishability, we derive such an axiomatic characterisation. Here, a central ingredient is a novel characterisation of graph parameters of the form $\hom(F, \star)$ for some graph $F$ alternative to a previous result of Lov\'asz & Schrijver (JCTA 2010). Moreover, we investigate the topology of homomorphism indistinguishability and discuss repercussions for the Ulam--Kelly Reconstruction Conjecture.

arXiv abstract · PDF

Finite Structures and Homomorphism Theory · primary corpus · published 2026-10-06T09:20:06Z
Lajos Soukup
arXiv categories: math.CO, math.LO

We study the complementary version of Hedetniemi's problem for infinite graphs. We prove that if a graph $G$ and its complement $\overline{G}$ are both uncountably chromatic while their categorical product is countably chromatic, then $|V(G)|=\omega_1$. Assuming $\diamondsuit$, we construct a graph $G$ on $\omega_1$ such that $\chi(G)=\chi(\overline{G})=\omega_1$ and $\chi(G\times\overline{G})=\omega$; the construction uses two suitably chosen minimal Countryman lines. We also define a c.c.c. forcing of cardinality $\omega_1$ that adds a graph with the same properties. It remains open whether ZFC alone proves the existence of such a graph.

arXiv abstract · PDF

Finite Structures and Homomorphism Theory · primary corpus · published 2026-10-06T11:49:40Z
Luka Carroll, Murray Elder
arXiv categories: math.GR, cs.LO

We prove that deciding whether there is a surjective homomorphism from an arbitrary finitely presented inverse monoid onto the bicyclic monoid is $\mathsf{NP}$-complete. As part of the proof, we show that an extension of existential Presburger arithmetic which involves greatest common divisors on $n$ arguments is in $\mathsf{NP}$, extending a recent result of D\'efossez, Haase, Mansutti, and P\'erez (SODA 2024).

arXiv abstract · PDF

Finite Structures and Homomorphism Theory · primary corpus · published 2026-10-07T15:28:43Z
Ilya Smirnov
arXiv categories: math.CO, math.LO

We establish tight bounds for the width and maximal order type of the h-preorder on Q-labeled trees in terms of the corresponding invariants of well-quasi-order Q.

arXiv abstract · PDF

Finite Structures and Homomorphism Theory · primary corpus · published 2026-10-07T18:58:35Z
Antonios Kalampakas
arXiv categories: math.CO, cs.DM, cs.LO

The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to $d$-tuples of vertices and iteratively refining the colouring according to neighbourhood configurations until it stabilizes. Increasing $d$ allows the test to detect finer structural differences between graphs, but the computational cost grows exponentially with $d$. The central question is which dimension allows us to distinguish nonisomorphic graphs. We relate a sufficient such dimension to the structure of a graph $G$ through a rank decomposition over $\mathbb F_2$. The two parameters governing the bound are the maximum cut rank $w$ and the fork load $\ell$, which is the largest sum of the parent and two child cut ranks at a fork in the decomposition tree. We prove that WL in dimension $\max\{\ell+1,2w+2\}$ distinguishes every finite nonempty vertex-coloured graph $G$ with such a decomposition from every graph not isomorphic to $G$. Consequently, for $k\geq1$, graphs of rank width at most $k$ can be distinguished from every nonisomorphic graph in dimension $3k+1$, graphs of linear rank width at most $k$ in dimension $2k+2$, and edgeless graphs in dimension one. Uncoloured Cai-F\"urer-Immerman (CFI) constructions give linear lower bounds for both width parameters, so the upper bounds are tight up to constant factors.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-06T12:10:30Z
Norihiro Hanihara
arXiv categories: math.RT, math.AC, math.AG, math.CT

We study the truncation $(-)^{\leq0}$ of dg categories. We first show that given a dg category $\mathscr{C}$ with shifts, for example a pretriangulated dg category, the canonical functor $\mathscr{C}^{\leq0}\to\mathscr{C}$ is a localization whose kernel is compactly generated by the $0$-th cohomology. Next we demonstrate that the derived category of the truncation serves as a triangulated analogue of the Auslander's category of coherent functors over abelian categories. We give a description of the Auslander-Reiten-Serre duality in terms of the inverse dualizing bimodule of the truncation. Building on truncations, we introduce the notion of connective resolutions of dg categories, defined as a localization functor from a connective dg category. This notion encompasses non-commutative resolutions of algebras in module categories, cluster tilting objects in triangulated categories, and also the truncation as the universal connective resolution. We give a sufficient condition for an object in a triangulated category to give a connective resolution of its enhancement in terms of finiteness of resolution dimension. Furthermore, we show that every proper dg module over a connective dg algebra is a direct summand of a dg module giving a connective resolution. Consequently, for every proper connective dg algebra, its bounded dg derived category has a connective resolution. Finally, we give some explicit description of the truncation for some categories including the derived and cluster categories of a Dynkin quiver, and the Yoneda category of a finite dimensional algebra.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-07T12:26:33Z
Eduardo Hoefel, Grigory Solomadin
arXiv categories: math.AT, math.CT

In this note, for every topological colored nonsymmetric operad with CW spaces in each arity we construct a homotopy isomorphism with a CW homotopy operad (i.e. all higher homotopies are cellular with respect to the product structure and CW structure on cubes) not changing its objects. By using the two-sided bar construction, we rectify this to a homotopy isomorphism with a strict CW operad. This applies more generally to topological algebras over colored operads in sets. In the case of diagrams of finite CW complexes over finite posets, the resulting diagram consists of finite CW spaces enhancing the Quillen adjunction between simplicial sets and topological spaces. As a byproduct, we produce an embedding of topological homotopy algebras over operads into the presheaf category over the branch resolution for the category of $P$-trees generalizing the known case of topological operads.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-07T14:25:19Z
Shengyong Pan
arXiv categories: math.AG, math.CT

We construct effective finite group actions on smooth projective complex curves for which Conjecture A of Polishchuk and Van den Bergh fails. For every $h\geq1$, an explicit $S_3$ action on the smooth projective model of $y^2=t^{12h-5}+t$ has quotient of genus $h$ and exactly one ramification orbit, with inertia of order three. The fixed quotient for the three-cycle class consists of two points, but its derived category admits no $\C$-linear exact fully faithful embedding into the equivariant derived category. More generally, when the coarse quotient has positive genus, we prove that the maximum number of pairwise completely orthogonal exceptional objects is $\sum_i\lfloor e_i/2\rfloor$, where $e_i$ are the inertia orders. We also characterize conjugacy-class decompositions with embeddings linear over the coarse quotient: such a decomposition exists if and only if $|[g]\cap H_i|\leq\lfloor e_i/2\rfloor$ for every nonidentity conjugacy class and every branch inertia group $H_i$. The sufficiency proof uses coloured paths of type $A$ and derived reflection functors, and produces kernels on the natural fibre products. The known ordered curve decomposition still yields a decomposition indexed by the connected components of the fixed quotients.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-07T16:51:12Z
Emily Cliff, Yves Lolelo, Sandrine St-Cyr
arXiv categories: math.AT, math.CT

Let $\mathcal{G}(G,A,\alpha)$ be a discrete 2-group, given as the {categorical} extension of an ordinary group $G$ by an abelian group $A$. We define principal $\mathcal{G}$-bundles over a manifold in terms of \v{C}ech data over a good open cover. In the case of the manifold $S^2$, we calculate this bicategory explicitly, and identify its 2-skeleton. We compare with the holonomy bicategory $\mathrm{Fun}(*/\!\!/ \pi_{\le 2}(S^2), * /\!\!/ \mathcal{G})$, and provide a concrete equivalence between the two.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-08T09:31:26Z
Zhangqi Pan
arXiv categories: math.AT, math.CT

For $n\ge1$, we study representations of a simplicial group $G$ in the full $\infty$-subcategory of simplicial vector spaces whose normalized homology is concentrated in degrees $0,\ldots,n-1$, retaining its full mapping spaces. The resulting functor category depends only on the $n$-truncated homotopy type of $\mathbf{B}G$ and admits projectively bifibrant strict diagram and simplicial group-algebra module models. If restriction along a specified map $f:G\to H$ is an equivalence, then $\pi_0(f)$ is a group isomorphism; the proof uses ordinary extension and restriction of scalars. Yet for every $n\ge2$ and prime $q$ invertible in $k$, the nontrivial source $K(\mathbb Z/q,n-1)$ has the same $n$-representation category with vertex evaluation as the trivial group. The group-algebra augmentation is a weak equivalence, so the constant functor is also an equivalence for untruncated representations. Thus $n$-representations depend only on the $n$-truncation of $\mathbf{B}G$, but need not determine that truncation, even together with vertex evaluation.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-08T13:53:54Z
Peng Xu
arXiv categories: math.CT

In this paper, we study the tensor triangular geometry of band algebras $RB$, where $B$ is a finite left regular band and $R$ is a commutative Noetherian ring. We show that the Balmer spectrum of $\Perf(RB)$ is homeomorphic to $\Spec R\times L_B$, where $L_B$ is the support lattice of $B$. We also show that there is a bijection between the localizing ideals of $D(RB)$ and the stable subsets of $\Spec R\times L_B$. As a consequence, the telescope conjecture holds for $D(RB)$. Finally, we construct a band $B$ such that the generalized Nerves of Steel Conjecture fails for the non-rigid tensor triangulated category $\Perf(RB)$.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-08T14:53:50Z
Hanlin Lin, Hao Zheng
arXiv categories: math.CT, math-ph, math.MP, math.QA

In this work, we propose a mathematical description of the critical point of boundary phase transitions in 2+1D topological orders. Given two boundary phases, $\mathcal{C}_A$ and $\mathcal{C}_B$, with corresponding Lagrangian algebras $A$ and $B$ in a 2+1D topological order $\mathcal{C}$, respectively, we propose that the critical point of the phase transition between these two phases, if it exists, corresponds to $D = A \times_{M} B$, which is the fiber product of $A$ and $B$ over $A$-$B$-algebra $M$. We prove that $D$ is also a condensable algebra. Additionally, we present an alternative classification of condensable algebras in $Z(Vec_G^\omega)$ and reveal splitting phenomenon that arises during the condensation of certain algebras. We also perform explicit computations for the condensable algebras within several examples of $Z(Vec_G^\omega)$, covering both Abelian and non-Abelian groups $G$.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-09T16:16:57Z
Mattia Ornaghi
arXiv categories: math.AT, math.AG, math.CT

Let $f$, $g\colon A\to B$ be two A$_{\infty}$-morphisms between two A$_{\infty}$-algebras (linear over a commutative ring $\mathbb{K}$). In this paper, we compare different notions of (right) homotopy between $f$ and $g$. We note that the A$_{\infty}$-algebra $B\otimes R$, where $R:=\mathbb{K}[t,dt]$, is a model for the interval $[0,1]\times B$ in the sense of Fukaya-Oh-Ohta-Ono, and we give a short alternative proof, in the unfiltered case, of the existence of comparison morphisms between such models. We use it to prove that two A$_{\infty}$-morphisms are homotopic \`a la Seidel if and only if, considered as morphisms of 2-colored DG operads, they are elementary homotopic \`a la Markl-Shnider-Stasheff through a homotopy which is constant on the two monochromatic parts. We also provide an example of two A$_{\infty}$-morphisms which are elementary homotopic but not weakly equivalent (and so homotopic \`a la Seidel). Moreover, over a field, we observe that the models for the interval are good path objects in the category of A$_{\infty}$-algebras with (non strict) A$_{\infty}$-morphisms, and we explain why weakly equivalent A$_{\infty}$-morphisms need not be homotopic.

arXiv abstract · PDF

Homotopical and Higher Algebra · primary corpus · published 2026-10-09T17:56:26Z
Andrew Riesen
arXiv categories: math.QA, math.CT

We announce an explicit construction of a unitary, strongly rational vertex operator algebra $U$ of central charge $8$ inside $V_{E_6\oplus A_2}$, with a ribbon equivalence $\mathrm{Rep}(U)\simeq Z(\mathcal H_3)$ realizing the Haagerup double. The vertex algebra is generated by six affine currents and three specified weight-two fields; its weight-one Lie algebra is $\mathfrak{sl}_2\oplus\mathfrak{sl}_2$, at levels $1$ and $39$. We outline the argument, which combines exact lattice calculations, an all-weight strong-generation induction and $C_2$-cofiniteness, semisimple descent for a full corner of Zhu's algebra, modular Galois symmetry, and holomorphic $E_8$ extensions.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-06T03:33:08Z
Alexander Kurz, M. Andrew Moshier, Achim Jung
arXiv categories: cs.LO, math.CT, math.GN, math.LO

We investigate how to systematically construct continuous dualities from zero-dimensional dualities, employing well-known methods from algebra, topology, category theory, and domain theory. While our method is general, this paper focusses on the move from Stone spaces to compact Hausdorff spaces and the move from Priestley spaces to compact ordered Hausdorff spaces. The engine of our approach is Stone duality for relations: on the space side quotienting by a preorder turns zero-dimensional spaces into continuous ones, while distributive lattices with a proximity relation are their algebraic duals. Our duality for relations is inherently order-enriched. Double categories organise both functional and relational morphism in the same structure. The move from zero-dimensional to continuous dualities is then a three-step construction: extend a duality from functional to relational morphism, split idempotents, restrict to maps.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-06T14:41:01Z
Bojana Femi\'c
arXiv categories: math.CT

We prove a two-dimensional version of Hermida's equivalence result on representable multicategories and classify its stricter versions. The obtained three-dimensional equivalence of the respective totality categories is of categories enriched over the multicategory $\mathsf{Bicat}$ of Verity. There is a basic enriched equivalence with respect to inherently lax monoidal pseudofunctors, and a one with respect to pseudo-monoidal pseudofunctors, related to the latter via the forgetful enriched functors. We extend Slattery's result on a bi-multicategory structure of the Kleisli bicategory of a 2-multicategory encompassing bi-representability.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-06T15:36:33Z
Yuto Kawase
arXiv categories: math.CT

We give a negative answer to the open problem posed by Ad\'amek and Rosick\'y in 2001, asking whether the cocompletion of any small category under sifted colimits is finitely accessible. We will construct an infinite family of counterexamples.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-07T09:31:26Z
Maria Manuel Clementino, Diana Rodelo
arXiv categories: math.CT

In this work we investigate a relative notion of protomodularity. We say that a finitely complete category $\mathsf{C}$ satisfies the \defn{$\mathscr{M}$-version of protomodularity} when the change-of-base functors (concerning the fibration of points) are conservative with respect to a class of morphisms $\mathscr{M}$ of $\mathsf{C}$. If $\mathscr{M}$ is the class of all morphisms or the class of all monomorphisms of $\mathsf{C}$, then this notion is precisely that of an ``ordinary'' protomodular category. We analyse what conditions the class $\mathscr{M}$ should have to obtain the relative $\mathscr{M}$-versions of some well-known properties of protomodular categories, such as the Split Short Five Lemma (when $\mathsf{C}$ is also pointed) and their relation with Mal'tsev categories. We also give diverse examples of categories satisfying the $\mathscr{M}$-version of protomodularity for different choices of $\mathscr{M}$.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-07T18:46:38Z
Paul-Andr\'e Melli\`es, Federico Olimpieri, Lionel Vaux Auclair
arXiv categories: cs.LO

We give a direct and explicit construction of the homotopy span model of linear logic originally formulated by Melli\`es using abstract homotopy theory in the Quillen category Cat of small categories equipped with its natural model structure. Following the principles of homotopy theory, the formulas and proofs of linear logic are interpreted in the model as small categories up to categorical equivalence, the notion of weak homotopy equivalence underlying the natural Quillen model structure on Cat. Here, we explain how the original interpretation of proofs as fibrant spans can be replaced by a more liberal interpretation of proofs as separately fibrant spans. This relaxation from fibrant spans to separately fibrant spans enables us to give a simple and intuitive description of the homotopy span model, where the axiom and cut links are interpreted as identity spans, and where the symmetries of the exponential modality are captured by a shuffle structure on the interpretation of proofs.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-07T21:37:59Z
Alexander Pr\"ahauser
arXiv categories: math.CT, math.GN

We introduce a systematic way to use the subobject functor on any category to set up an framework for generalized topological and measure-theoretic notions and inferences. Concretely, we develop two connected calculi: 1. a fourfold calculus derived from notions of smallness and density that generalizes, among other things, topological density and measure-theoretic negligibility, 2. a twofold calculus that generalizes topological and measure-theoretic inference procedures. The resulting theory is distinguished in that it is inter-categorical in character: its definitions can be applied not just to describe smallness and density of subobjects in any category and classify morphisms by how they handle them, but also functors and natural transformations by how they transform them, somewhat like the theory of limits but with a simple and intuitive conceptual meaning that applies to each incarnation. We provide examples of these notions from many areas of mathematics and outline their unfolding throughout category theory as we add assumptions that bring them closer to classical settings, which we complete by generalizing the topological duality of open and closed subsets and outlining a possible framework for a categorical measure theory. Central to this interaction is the subobject 2-functor and the 2-category of upward-bounded preorders, so in the last part of the text we provide a study of their function. Concretely we derive representation theorems for this 2-functor and 2-category and a conjecture about how to generalize these theorems to n-categories.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-08T08:36:50Z
Joe Gildea
arXiv categories: math.CT

We develop a semisimple obstruction theory for finite-length abelian categories. To each object \(X\) we associate a canonical obstruction subobject \(\mathcal O(X)\), consisting of the part invisible to all morphisms into semisimple objects. The quotient \(X/\mathcal O(X)\) is semisimple and universal among such morphisms, yielding a canonical semisimplification reflector and characterizing semisimplicity by the vanishing of obstruction. Iterating the construction gives an obstruction filtration which, in finite-length module categories, recovers the classical radical filtration and Loewy theory. Obstruction is also heart-dependent: under Happel--Reiten--Smal{\o} tilting, extension data can appear as new obstruction layers, leading to obstruction shadows and visible torsion. Thus classical radical theory arises as the fixed-heart module-theoretic instance of a categorical framework for semisimple reconstruction, persistence, and variation of heart.

arXiv abstract · PDF

Categorical Foundations and Duality · primary corpus · published 2026-10-09T08:20:08Z
Matteo Mio, Colin Riba
arXiv categories: cs.LO

Proofs in quantitative algebra are, generally, infinite objects due to the presence of infinitary rules in the deductive apparatus. A quantitative equational theory is called compact if all its consequences are derivable by means of finite proofs, that is, proofs not using any instances of the infinitary rules. This definition is purely logical. In this work we give an equivalent, but categorical, characterisation based on the notion of monad restriction.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-05T18:25:09Z
Edward Bierstone, Jean-Baptiste Campesato
arXiv categories: math.CA, math.AG, math.CV, math.LO

Consider a system of equations $A(x)\cdot F(x) = B(x)$ on a subset $X$ of $\mathbb R^n$, where $A(x)$ and $B(x)$ are matrix- and vector-valued semialgebraic functions on $X$, and the unknown $F(x)$ is a field of vector-valued $m$-jets. We assume there is a solution which is the field of Taylor polynomials of order $m$ on $X$ of a $\mathcal C^m$ vector-valued function $f$ on $\mathbb R^n$, and ask whether we can find a $\mathcal C^m$ semialgebraic solution $f$. Our main result is a positive answer in the case $\dim X = 1$. The methods are based on an article of Fefferman and Luli for $X \subset \mathbb R^2$, and a secondary goal is to show that their approach applies in a much simpler way in the case $\dim X =1$, or in the case of the semialgebraic Whitney extension problem in $\mathbb R^2$. Our results hold more generally for functions definable in an o-minimal expansion of $\mathbb R$.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-06T10:03:40Z
Spencer Dembner
arXiv categories: math.LO, math.CV

Zilber's celebrated quasiminimality conjecture states that a subset of $\mathbb C$ defined by polynomials and exponentials is either countable, or has countable complement. Koiran has asked whether the same could be true replacing $\exp$ with any unary entire function. We give a negative answer to Koiran's question, using results from the theory of holomorphic approximation.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-06T11:42:39Z
Zhenyu Xiu
arXiv categories: math.LO

In this paper, we establish necessary and sufficient representation theorems for the classes $\widetilde{\mathcal{U}}_{\mathrm{top}}$, $\widetilde{\mathcal{U}}_{\mathrm{bot}}$, $\widetilde{\mathcal{U}}_{\mathrm{max}}^{r}$, and $\widetilde{\mathcal{U}}_{\mathrm{min}}^{r}$ of uninorms on bounded trellises, extending the corresponding bounded-lattice results. For a non-extremal neutral element $e$ belonging to no non-trivial cycle, we use a common decomposition of the elements incomparable with $e$; every neutral element of a uninorm is shown to be middle-transitive. Each uninorm in $\widetilde{\mathcal{U}}_{\mathrm{top}}$ (respectively, $\widetilde{\mathcal{U}}_{\mathrm{bot}}$) is represented by an interior operator (respectively, a closure operator), a component uninorm, and an increasing, associative, and commutative operation, with all components uniquely determined. Two further conditions characterize the subclasses $\widetilde{\mathcal{U}}_{\mathrm{top}}^{\star}$ and $\widetilde{\mathcal{U}}_{\mathrm{bot}}^{\star}$. For $\widetilde{\mathcal{U}}_{\mathrm{max}}^{r}$ (respectively, $\widetilde{\mathcal{U}}_{\mathrm{min}}^{r}$), we identify the pairs in $I_e^3\times I_e^3$ whose values lie in $[0,e[\cup I_e^1$ (respectively, $]e,1]\cup I_e^2$) or equal $e$. The pairs producing $e$ satisfy a symmetric unique-partner condition, while the remaining values are encoded by a partial operation. Regional order compatibility and explicit associativity conditions then yield necessary and sufficient representations. Finally, we compare the four classes, relate them to the corresponding bounded-psoset classes, prove their bounded-lattice specialization under transitivity, and provide finite examples on proper trellises illustrating the additional compatibility conditions.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-06T14:11:29Z
Junguk Lee, Wan Lee
arXiv categories: math.LO, math.NT

We study the structure of finitely ramified henselian valued fields of mixed characteristic with arbitrary residue fields via their residue rings of higher length, where a residue ring of length $n$ is the quotient ring of the valuation ring by the $n$th power of its maximal ideal. We prove an approximate lifting theorem for homomorphisms between residue rings of higher length and explicitly determine the optimal bound of error of lifting. As applications, we obtain several Ax-Kochen-Ershov principles for relative completeness, relative existential completeness, and existential closedness using the pure ring structures on the residue rings. And we show that any formula on a residue ring of length $k$ is equivalent to a normal form of sentences in pure ordered group structure and special formulas at level $n$, uniformly for all finitely ramified henselian valued fields of mixed characteristic $(0,p)$ and the same initial ramification index $e$. Here, for $n\ge k$, a special formula at level $n$ represents a definable set on a residue ring of length $k$ given by a projection image of a definable set in pure ring structure on a residue ring of length $n$. Also, such $n$ is optimally computed from the precise estimation of error of lifting and depends only on $k$, residue characteristic $p$, and initial ramification index $e$.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-06T18:31:22Z
Kristian Muri Knausg{\aa}rd
arXiv categories: math.NT, cs.LO

Let N(T) count the nontrivial zeros of the Riemann zeta function up to height T with multiplicity, N_d(T) the distinct ones, and N_0^s(T) those that are simple and on the critical line. We prove liminf N_d(T)/N(T) >= 1645064/1960733 = 0.83900...; earlier work proves 0.83699..., and a report we have not verified claims 0.83805.... Hence more than 67.80% are simple. Also liminf N_0^s(T)/N(T) >= 0.67353...; earlier work proves 0.67250..., and reports we have not verified claim 0.673492. Two estimates of Lamzouri are improved: at least 88.93% of the zeros are simple or on the critical line, and the proportions of simple zeros and of zeros on the line average at least 83.67%. By the unconditional form of Montgomery's pair-correlation theorem the energy, a sum of a test function over pairs of zeros, is known asymptotically. A zero of multiplicity d contributes d^2 to it and nearby zeros contribute too, so a lower bound for such pairs leaves less energy for multiple zeros. The proof has three steps. First, for zeros at least a fixed fraction of the mean spacing apart, a large sieve inequality lets their pairs be used in full, with multiplicities. Second, their contribution is bounded below by a computer-assisted inequality for seven or eight consecutive zeros which distinguishes simple and double zeros. Its correction terms telescope, as increments of a storage function. Third, the test function is chosen to make this contribution large, at the cost of more energy. We also prove upper limits for what such inequalities can give with the two main test functions. The lower bounds and these limits are proved in Lean 4, analytic inputs included. The proofs use three axioms beyond those of Mathlib, one per inequality. Each records that a search program returned true; Lean's kernel does not check the run itself. This work is an experiment in AI-assisted mathematical research.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-07T02:12:20Z
Hongyu Zhu
arXiv categories: math.LO

We propose a new variant of Vaught's conjecture, based on Martin's (model-theoretic) conjecture and the $\omega$-Vaught's conjecture of Gonzalez and Montalb\'an. For $\omega$-stable theories, we prove the conjecture by analyzing in detail Bouscaren's and Shelah-Harrington-Makkai's proofs of Martin's conjecture and Vaught's conjecture, respectively, for $\omega$-stable theories. In particular, when there are countably many countable models, we improve the required number of quantifiers for a Scott sentence from $\omega+\omega$ to $\omega+5$, and we obtain a similar bound of $\omega+6$ for the uncountable case.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-07T11:10:03Z
Raf Cluckers
arXiv categories: math.LO

Following Macintyre's quantifier elimination result for semi-algebraic $p$-adic sets from 1976, Denef's cell decomposition from 1984 has played a catalyzing role for both motivic integration and Hensel minimality. Motivic integration has in turn been applied in the Langlands program via transfer principles to change the characteristic of the local field, e.g., for the fundamental lemma. Hensel minimality has been used to study rational points on definable sets, providing non-archimedean analogues of results by Pila and Wilkie in o-minimal structures. I will review some related results and open questions.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-07T15:06:11Z
David J. Smith
arXiv categories: math.LO, math.AG, math.NT

Let $G$ be a simple abelian variety of dimension $g \in \mathbb{N}$ defined over $\mathbb{Q}^\mathrm{alg}$ and let $C_1, C_2 \subseteq G^N(\mathbb{C})$ be irreducible closed algebraic curves with $N \geq 3$. Further assume that at least one of $C_1$ and $C_2$ is not defined over $\mathbb{Q}^\mathrm{alg}$. Suppose that there does not exist an algebraic subgroup $H_1 \subseteq G^N(\mathbb{C})$ of dimension $g$ such that $C_1 \subseteq H_1$ and that there does not exist an algebraic subgroup $H_2 \subseteq G^N(\mathbb{C})$ of dimension $2g$ such that $C_1 \cup C_2 \subseteq H_2$. Denoting $\mathcal{N} = \{n \in \mathbb{N} \ | \ [n]C_1 \subseteq C_2\}$, we prove that $\bigcup_{n \in \mathbb{N} \setminus \mathcal{N}}\{x \in C_1 \ | \ nx \in C_2\}$ is finite.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-08T01:42:12Z
Spencer Unger, Jerry Wei
arXiv categories: math.LO, math.GR

The Whitehead problem, which asks whether every abelian group $A$ satisfying $\mathrm{Ext}^1(A,\mathbb{Z}) = 0$ is free, is independent of ZFC. However, this problem has an analogue in condensed mathematics that can be answered affirmatively. In this note, we give a new proof that an abelian group $ A $ of size $\kappa$ is free if and only if $\underline{\mathrm{Ext}}^1(\underline{A}, \underline{\mathbb{Z}})(S_\kappa) = 0$, where $ S_\kappa $ is the Stone space of the Boolean completion of $\operatorname{Add}(\omega,\kappa)$.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-08T02:16:58Z
Olga Kharlampovich, Rizos Sklinos
arXiv categories: math.GR, math.LO

We establish a uniform small cancellation theorem for non-elementary torsion-free hyperbolic groups: given any prescribed small cancellation constant, finitely many fixed words suffice to produce a small cancellation element from every pair of noncommuting elements. As an application, we prove that the first-order theory of every non-elementary torsion-free hyperbolic group does not admit a model companion.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-08T16:20:33Z
Anastasis Kratsios, Philipp Zimmermann
arXiv categories: math.FA, cs.DS, math.CA, math.LO

We identify explicit closed-form and variational formulae for interpolating the exact values and derivatives through order $s$ of a $C^{s,1}$ function $f:\mathbb{R}^d\to\mathbb{R}$ at $N$ distinct points in $[0,1]^d$. The reconstruction satisfies bounds on its global $C^{s,1}$ seminorm and its Lipschitz constant on $[0,1]^d$ that are independent of the sample size $N$, the latter being the sharp Whitney condition. For $s\ge2$, the reconstruction is real analytic away from the data points and definable in the o-minimal structure $\mathbb{R}_{\exp}$. Our nonlinear extension formula coincides with the formula of McShane (1934) for $s=0$ and with the formulae of Le Gruyer and Phan (2015) and Azagra, Le Gruyer, and Mudarra (2018) for $s=1$, and is new for $s\ge2$. For fixed $d$ and $s\ge2$, our closed-form formula is computable away from the data points by a circuit using only elementary unary and binary real operations, with $\mathcal{O}(N)$ gates and $\mathcal{O}(\log N)$ depth. This yields $\mathcal{O}(N)$ storage and $\mathcal{O}(\log N)$ parallel evaluation time. From the supplied coefficients and weights, the circuit can be compiled with $\mathcal{O}(N)$ one-time work in the exact-real word-RAM model. Thus, in this supplied-data setting, our nonlinear construction improves by a logarithmic factor on the $\mathcal{O}(N\log N)$ initialization bound of Fefferman and Klartag (2009), while retaining linear storage and attaining logarithmic query time through parallel evaluation.

arXiv abstract · PDF

Model Theory and Algebraic Structures · primary corpus · published 2026-10-09T15:53:01Z
Carlos Cordoba-Caycedo, Dario Garcia
arXiv categories: math.LO

This paper studies pseudofinite abelian groups and counting properties of definable sets in finite abelian groups and their ultraproducts. First, we characterize pseudofinite abelian groups in terms of Szmielew invariants and, building on results of Macintyre, extend this analysis to obtain a characterization of pseudofinite $\omega$-stable abelian groups. We then give an alternative proof that the class of finite abelian groups forms a multidimensional exact class, explicitly describing the possible cardinalities of definable sets in classes of finite abelian groups. We also investigate $N$-dimensional asymptotic classes of finite abelian groups and provide a series of examples showing that, despite the exactness result, several natural classes of finite abelian groups fail to be $N$-dimensional asymptotic classes for every $N\geq 1$. Finally, in an appendix, we characterize the SU-rank of pseudofinite abelian groups, building on work of Rogers. In particular, we show that for every pseudofinite abelian group $A$, either $\operatorname{Th}(A,+)$ is superstable of finite SU-rank or it is strictly stable.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-05T08:37:53Z
Isaac Goldbring
arXiv categories: math.LO, math.OA

Answering a question of Thomas Sinclair, we show that the standard presentation of the reduced group C*-algebra $C^*_r(G)$ of an infinite hyperbolic group $G$ is computable. The main ingredient in proving this result is showing that the Gromov boundary $\partial G$ of $G$ admits a computably compact metric presentation for which the natural action of $G$ on $\partial G$ is computable.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-05T08:42:46Z
Isaac Goldbring
arXiv categories: math.LO, math.OA

We show that whenever $G$ is a finitely generated group with the rapid decay property (property RD), then the norm on the reduced group C*-algebra $C^*_r(G)$ is computable if (and only if) $G$ has solvable word problem. We also give an example of a finitely presented group $G$ with solvable word problem for which the norm on $C^*_r(G)$ is not computable.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-05T14:04:07Z
J\"org Endrullis, Ievgen Ivanov, Femke van Raamsdonk
arXiv categories: cs.LO

Confluence is a fundamental property of nondeterministic computations, arising from parallelism, concurrency, or freedom in the evaluation order. It guarantees that such a computation always yields the same result, regardless of the order in which steps are taken. The decreasing diagrams technique of van Oostrom is one of the most versatile methods for establishing confluence of transition systems (abstract rewriting systems). It reduces global confluence to local confluence: a system is confluent whenever its transitions admit a locally decreasing labeling. Essentially all classical confluence criteria arise as corollaries. A central question, posed by van Oostrom in 1993, asks whether the decreasing diagrams technique is complete: Does every confluent transition system admit a locally decreasing labeling? This is Problem 56 of the RTA List of Open Problems. A positive answer was known only for countable systems, and recently up to the first uncountable cardinal $\aleph_1$. The general case remained open. We settle this thirty-three-year-old problem in full. We prove that every confluent transition system admits a locally decreasing labeling using only three labels. This bound is optimal, as two labels do not suffice even at the first uncountable cardinality. It follows that this single criterion can, in principle, certify the confluence of every confluent system, and hence of every confluent program. The entire development is machine-checked in the Isabelle/HOL and Lean proof assistants and relies only on classical logic and the axiom of choice.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-05T17:22:19Z
Anssi Yli-Jyr\"a
arXiv categories: cs.FL, cs.CC, cs.DM, cs.LO

We introduce recurrent incidence automata (RIAs), a new automaton model motivated by a decomposition of certain two-stack visibly pushdown computations. The decomposition separates vertex-local finite-state computations from recurrent one-stack interfaces connecting consecutive vertices. The construction is motivated by a two-stack visibly pushdown encoding of arbitrary ordered graphs whose strings admit a unique factorization into center-foldable vertex-local factors and whose auxiliary stack is empty at every factor boundary. Folding each factor into a sequence of pair symbols yields a local interface transformation. An RIA consists of a finite-state unit that computes these transformations and a recurrent layer that composes them across consecutive factors. Rather than manipulating an internal pushdown store, RIAs externalize long-range stack memory into recurrent interfaces between local computations. We show that nondeterministic RIA languages are closed under union, intersection, concatenation, Kleene-*, and reversal. Deterministic RIAs are closed under Boolean operations, although emptiness remains undecidable.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-06T18:46:57Z
Vincent Liew
arXiv categories: cs.CC, cs.LO

SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this phenomenon. CDCL SAT solvers implicitly search for resolution proofs, and no lower bound on proof size has ruled out the existence of short proofs that solvers simply fail to find. We give the first lower bound of this kind by showing that general resolution proofs of the associativity of $n$-bit multiplication require size $2^{\Omega((n/\log n)^{1/4})}$. This lower bound holds for a broad class of multiplier encodings based on partial product summation, including the standard array and Wallace-tree multipliers used to bit-blast multiplication in SMT solvers. This result resolves an open problem of Beame and Liew. The proof constructs a reduction from a perfect-matching principle on bounded-degree bipartite expander graphs to multiplier associativity. Itsykson, Slabodkin, and Sokolov proved that this principle is hard for resolution. The lower bound for multiplier associativity follows. The same reduction, when combined with H\r{a}stad's recent lower bound for the perfect-matching principle of the odd grid, yields an exponential lower bound for multiplier associativity in the stronger bounded-depth Frege proof systems.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-07T07:12:56Z
Masahiko Sakai, Mizuhito Ogawa, Michio Oyamaguchi
arXiv categories: cs.LO

This paper proposes a new method for proving the confluence of an abstract reduction system (ARS) by clarifying the sufficient conditions, called compatibility and edge commutativity, for expanding a given finite sub-ARS into a confluent one by adding rewrite edges. This method can be regarded as an extension of our earlier work, which showed that a weakly non-overlapping, shallow, and non-collapsing term rewriting system (TRS) is confluent. Furthermore, we apply our method to demonstrate that a non-$E$-overlapping and weakly shallow TRS is confluent. Here, a term is weakly shallow if each defined function symbol occurs either at the root or in the ground subterms, and a TRS is weakly shallow if both sides of all its rewrite rules are weakly shallow. This drops the non-collapsing condition assumed in our previous work on weakly shallow TRSs. Moreover, since a weakly shallow TRS is non-$E$-overlapping whenever it is non-$\omega$-overlapping, and the latter property is decidable, we also obtain a decidable sufficient condition for confluence: non-$\omega$-overlapping and weakly shallow TRSs are confluent.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-07T12:41:14Z
Joseph M. Shunia
arXiv categories: math.LO

Prunescu, Sauras-Altuzarra, and Shunia asked whether addition, totalized integer division, and base-two exponentiation form a substitution basis for the Kalm\'ar elementary functions. We answer this problem negatively, even after adjoining multiplication. On independent powers of two, every fixed term built from addition, multiplication, and integer division takes only polylogarithmically many distinct values below a given bound, and the same restriction survives arbitrary nesting of $2^x$. No such term recovers $n$ from $2^n$, so neither $\lfloor\log_2 x\rfloor$ nor integer remainder is representable. The obstruction is not special to the base two. For every fixed integer $b\geq 2$, the same sparsity bound holds with constants independent of $b$, and $\langle x+y,\lfloor x/y\rfloor,b^x\rangle$ remains a proper subclass of the elementary functions. Variable exponentiation reverses the conclusion: addition, integer division, and $x^y$ do form a substitution basis, $$ \langle x+y,\ \lfloor x/y\rfloor,\ x^y\rangle=\mathcal{E} .$$ Once the base may depend on the input, integer remainder and truncated subtraction become representable. The incomplete base-two class is nevertheless complete for truth values. Every elementary characteristic function belongs to it, as does every elementary function with a fixed finite range.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-07T13:18:12Z
Nohra Hage
arXiv categories: math.CO, math.CT

We study the tableaux monoid from the perspective of rewriting theory. We first construct a finite quadratic convergent presentation based on column generators and prove that it yields a biautomatic structure. We then extend this presentation to a finite coherent presentation in the sense of polygraphic rewriting. These results provide canonical normal forms, yield homological and algorithmic consequences, and produce a higher-dimensional presentation that can be used to describe actions of the tableaux monoid on categories.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-08T11:41:48Z
Patrick Uftring
arXiv categories: math.LO

We answer the following question by Frittaion, Nemoto, and Rathjen positively: "Is [independence of premise] an admissible rule of $\textsf{CZF}$ or any other familiar constructive/intuitionistic set theory $T$?" To be more precise, we show that whenever $\textsf{IZF}$ (or $\textsf{CZF}$ with full separation) derives a statement of the form $\lnot\psi \to \exists y\ \varphi(y)$ where $y$ does not occur in $\psi$, then $\textsf{IZF}$ (or $\textsf{CZF}$ with full separation) also derives $\exists y\ (\lnot\psi \to \varphi(y))$. Our proof method is a variant of the famous Friedman-Dragalin $A$-translation adapted to the context of set theory in a hereditary manner.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-08T16:25:05Z
Charles C. Norton
arXiv categories: cs.LO, cs.NE

A fixed network of McCulloch-Pitts threshold units with weights in {-1,0,1} can hold other threshold networks in its state and run them: the state is a ring of banks of records, each record a unit of a stored network, and each step evaluates one record. We use such a network to carry out von Neumann's universal construction and self-reproduction exactly. As a cellular automaton keeps its rule, the fixed network keeps its weights, and what reproduces is a stored network. A constructor of 143 records reads the description of a network from its tape, builds that network in the next bank, copies the description onto the next tape and hands control to what it built; started on its own description, it rebuilds itself, weights included, in every generation. The scheme scales to a universal computer. A SUBLEQ computer of 17,598 ternary units, stored as 36,080 records and running a program of 27 instructions, builds any network that fits a bank and reproduces itself in the same way, at every word width from eight bits on; run directly, it emits the serialization of its own weights, memory and tape. Integer pre-activations give every orbit a margin of 1/2, and replicating each unit r times multiplies it by r. That suffices against noise of any size on the pre-activations, but against von Neumann's output flips only below a threshold inversely proportional to the fan-in. These results are proved in Rocq.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-08T17:57:15Z
Ivan O. Shevchenko, Jun Liu, Xinzhi Liu
arXiv categories: math.DS, math.CA, math.LO

We study the decision problem of global asymptotic stability (GAS) of the origin for homogeneous polynomial vector fields with rational coefficients. In the first part of the paper we give, for every fixed dimension $n$ and odd degree $2k+1$, a computable map which sends a homogeneous vector field of degree $2k+1$ on $\mathbb{R}^n$ to a homogeneous cubic vector field on $\mathbb{R}^m$, $m=\binom{n+k-1}{k}$, and preserves both GAS and Lyapunov stability. The map passes to new variables $y_\alpha=x^\alpha$ (one for each monomial $x^\alpha$ of degree $k$), in which the vector field becomes cubic, and adds a cubic penalty term transverse to the set of points of the form $(x^\alpha)_{|\alpha|=k}$; the main point is that this controls every initial state of the new system. As a consequence, the GAS problems for all degrees, for each fixed odd degree $d\ge3$, and for degree three are pairwise many-one equivalent. In the second part we prove that there are a fixed dimension $N_*$ and a fixed odd degree $d_*$ such that the set of homogeneous vector fields on $\mathbb{R}^{N_*}$ of degree $d_*$ whose origin is GAS is many-one complete. The reduction encodes an undecidable family of polynomial equations in integer unknowns into the constant term of a product of Jacobi theta series, realizes these series as outputs of a polynomial differential system with rational coefficients, and turns the existence of an integer solution into the sign of a maximal invariant average, which homogeneous GAS detects. Combining the two parts shows that GAS of rational homogeneous vector fields on $\mathbb{R}^N$ of degree $d$ is many-one complete for every odd $d\ge3$ and every sufficiently large $N$; in particular it is undecidable for cubic vector fields in a fixed dimension. Building on recent work, some analogous results are proven for Lyapunov stability of homogeneous vector fields.

arXiv abstract · PDF

Rewriting Systems and Computability · primary corpus · published 2026-10-09T04:08:09Z
Tatsuji Kawai
arXiv categories: math.LO

The minimum principle states that every real-valued uniformly continuous function f : X -> R on a compact metric space X attains its minimum. Working in the base system EL0 of constructive reverse mathematics, we show that the minimum principle is equivalent to weak Konig's lemma and to the Cantor intersection theorem (i.e., the contrapositive of the Heine-Borel theorem). Moreover, the above equivalence naturally extends to the equivalence between the corresponding principles with unique existence assumptions, which are then shown to be equivalent to the Fan theorem for detachable bars and the positivity property for a real-valued uniformly continuous function on a compact space. These results sharpen the equivalence among these principles obtained by Ishihara [Math. Log. Q. (1990), 237-240] and Berger and Ishihara [Math. Log. Q. (2005), 360-364] in Bishop's constructive mathematics.

arXiv abstract · PDF

Non-Classical Logics and Decidable Fragments · primary corpus · published 2026-10-05T15:14:41Z
Oskar Fiuk
arXiv categories: cs.LO

Maslov's class K is a decidable fragment of equality-free first-order logic. It subsumes numerous classical decidable fragments, including the equality-free monadic fragment, the equality-free two-variable fragment, and the G\"odel class. Introduced over 50 years ago, the class K has been studied in automated deduction, primarily through resolution-based methods. Despite this long history, the precise complexity of the satisfiability problem for K remained open until recently, when NExpTime-completeness was finally established. The two main contributions of this work are as follows. 1. The recent proofs of NExpTime-completeness and the finite model property for K are highly non-trivial and technically sophisticated. We present considerably simpler proofs of both results. Our approach combines a novel reduction from K to the class of solvable Skolem sentences with a randomised construction of finite models. 2. We introduce the class K+E by allowing sentences in K to contain one distinguished binary predicate E whose interpretation is constrained to be an equivalence relation. By leveraging our approach to this extended class, we prove that K+E has the finite model property and that its satisfiability problem is 2-NExpTime-complete.

arXiv abstract · PDF

Non-Classical Logics and Decidable Fragments · primary corpus · published 2026-10-05T19:49:56Z
Stefania Dumbrava, Efthymia Tsamoura
arXiv categories: cs.AI, cs.LO

Logic programming is increasingly used as the symbolic component of neurosymbolic AI systems. We survey the main rule-based languages in this setting, namely Datalog, answer set, and probabilistic logic programs, along four axes: semantics, expressiveness, neural integration, and evaluation mechanism. We analyse over 50 recent systems and applications, comparing formalism usage across four research areas: databases and programming languages, machine learning, vision, and robotics. We provide a decision matrix mapping application scenarios to required features and close by outlining open problems.

arXiv abstract · PDF

Non-Classical Logics and Decidable Fragments · primary corpus · published 2026-10-06T13:00:53Z
Yaroslav Petrukhin
arXiv categories: cs.LO, math.LO

In this paper, we investigate connections between dependence logics, viewed as a subclass of relating logics, and three-valued logics. More specifically, we identify common features of Epstein's subject-matter semantics and the variable-inclusion conditions characteristic of some infectious many-valued logics. Inspired by Del Cerro and Lugardon's sequent calculi for dependence logics, in which classical connectives are combined with connectives satisfying Epstein-style conditions, we introduce two three-valued dependence-like logics that combine classical conjunction and disjunction with infectious negation and implication. We also provide sound, complete, and cut-free bisequent calculi for these logics.

arXiv abstract · PDF

Non-Classical Logics and Decidable Fragments · primary corpus · published 2026-10-06T13:23:53Z
Yaroslav Petrukhin
arXiv categories: cs.LO, math.LO

This paper investigates many-valued generalisations of the classical essence and accident modalities. In two-valued logic, a proposition is essentially true (resp. false) if, whenever it is true (resp. false), it is necessarily true (resp. false); it is accidentally true (resp. false) if it is true (resp. false) but not necessarily so. Many-valued logics provide a natural setting for introducing further modalities of this kind. We focus on Belnap-Dunn's First-Degree Entailment (FDE), a four-valued system that generalises the classical truth values. More precisely, we consider an extension of FDE with Boolean negation and implication. In addition to modalities of essential and accidental truth and falsity, we define modalities of essential and accidental inconsistency and indeterminacy. We present a four-valued S5-based Kripke semantics and cut-free hypersequent calculi for the resulting logics. We then prove semantic and syntactic embedding theorems for these logics into a four-valued version of S5 with necessity and possibility modalities. These embeddings clarify the intended interpretation of the Belnapian essence and accident modalities and yield soundness, completeness, and cut-admissibility results.

arXiv abstract · PDF

Non-Classical Logics and Decidable Fragments · primary corpus · published 2026-10-07T09:45:43Z
Jakub Michaliszyn, Piotr Witkowski
arXiv categories: cs.LO

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

arXiv abstract · PDF

Non-Classical Logics and Decidable Fragments · primary corpus · published 2026-10-07T13:01:09Z
Igor Sedl\'ar, Pietro Vigiani
arXiv categories: cs.LO

Motivated by relevant epistemic logic, we extend Dunn's simple Kripke-style binary relational semantics for the semi-relevant logic RM to fit a modal extension of RM. It is shown that the modal axioms and rules that need to be added to RM to obtain a sound and complete axiomatisation of its modal extension give an axiomatisation of modal extensions of all logics in the family of generalised Nelson logics, also studied by Dunn.

arXiv abstract · PDF

Non-Classical Logics and Decidable Fragments · primary corpus · published 2026-10-08T14:10:16Z
Jinfan Xu, Jieting Luo
arXiv categories: cs.AI, cs.LO

Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy ($\Sigma_1^1$ or $\Pi_1^1$), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance ($\Cred$), skeptical acceptance ($\Skep$), extension existence ($\Ex$), uniqueness ($\Uni$), and non-empty existence ($\NE$). For grounded semantics, credulous and skeptical acceptance are already known to be $\Sigma_1^0$-complete. We show that non-empty existence is also $\Sigma_1^0$-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, $\Cred_{\pref}$ is shown to be in $\Pi_1^0$-c and $\NE_{\pref}$ is $\Sigma_2^0$-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving $\Skep_{\pref}$ in $\Pi_1^1$ and $\UniPref$ in $\Sigma_2^1$-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-05T18:34:49Z
T. Y. Tsui, Zihao Ye, Pengxiang Cai, Yanchao Li, Yuqiang Li, Zhehong Ai
arXiv categories: cs.LG, cs.AI, cs.CL, cs.LO

``What are the irreducible conditions that are sufficient to produce an outcome?'' is one of the most common questions that recur across computation and science. Its answers, the minimal sufficient witnesses, are what we mean by explanations, mechanisms and reasons. These problems usually ask for multiple minimal witnesses, yet standard RL methods may reveal only one solution or redundant ones. We formalize this problem as minimal-witness identification and introduce Minimal-Witness Reinforcement Learning (MWRL). MWRL takes the union of the sets certified by successful proposals sampled from the policy and credits each proposal for the coverage the group union would lose without that proposal. This credit assignment, derived directly from the problem definition, unifies the demands for minimality and recovery of alternatives from a single black-box verifier bit. Under this principle, we derive a value iteration planner that recovers the entire family of witnesses and a policy gradient method that can scale to large language models. Across different experimental settings, MWRL recovers most minimal witnesses, while other methods return redundant supersets or a single witness. By making witness families learnable from verifier feedback, MWRL expands the scope of reinforcement learning beyond single-solution optimization. Our code is available at https://github.com/TSUITUENYUE/MWRL.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · cs.SE candidate · published 2026-10-06T03:20:59Z
Hao Zheng, Jaime Rafael Imperial, Bardia Nadimi, Xiangfei Kong
arXiv categories: cs.AR, cs.AI, cs.SE

Large language models (LLMs) are increasingly being integrated into hardware verification to automate specification interpretation, verification-artifact generation, debugging, formal reasoning, and tool orchestration. This survey provides a systematic review of LLM-assisted hardware functional verification across SystemVerilog assertion generation, stimulus and testbench generation, bug localization and design repair, model checking and equivalence checking, SAT/SMT optimization, and emerging agentic verification workflows. We organize the literature by methodology, verification objective, tool interaction, benchmark, and evaluation criterion, and examine both inference-time techniques--including prompting, retrieval, structured reasoning, and agentic workflows--and training-time adaptation. Across these areas, a common pattern emerges: LLMs are most effective as semantic reasoning, search, and orchestration components embedded within verification-aware workflows, while simulators, formal engines, coverage tools, and solvers provide executable feedback and correctness evidence. However, tool acceptance alone does not establish verification correctness, since assertions, tests, repairs, or proofs may satisfy available checks without faithfully capturing the complete design intent. We therefore identify semantic alignment between specifications and verification evidence, scalable integration with deterministic tools, generalization to unseen designs, and rigorous evaluation of correctness, cost, robustness, and human effort as key challenges. Finally, we discuss emerging directions toward specification-centered, neuro-symbolic, and persistent agentic verification systems that combine LLM flexibility with independently checkable verification evidence.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-06T16:56:48Z
Giorgio Bacci (Aalborg University, Denmark), Micka\"el Randour (UMONS - Universit\'e de Mons, Belgium)
arXiv categories: cs.LO, cs.FL

This volume contains the proceedings of GandALF 2026, the Seventeenth International Symposium on Games, Automata, Logics, and Formal Verification. The symposium was held in Aalborg, Denmark, on September 15-17, 2026. The aim of GandALF 2026 is to bring together researchers from academia and industry who are actively working in the fields of Games, Automata, Logics, and Formal Verification. The idea is to cover an ample spectrum of themes, ranging from theory to applications, and stimulate cross-fertilisation.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-06T18:00:43Z
Nikolaos Kekatos, Dimitrios Nikou, Anastasios Temperekidis, Alexios Lekidis, Nikolaos Kolokotronis, Panagiotis Katsaros, Stylianos Basagiannis
arXiv categories: cs.CR, cs.AI, cs.LO

LLM-based agents are entering decision-support roles in defence staff work, where the obligations they must respect are already written down and binding, and where retraining is not available as a control because models arrive as procured components. What can be placed under engineering control is the interface between the agent and the systems it acts on. Those obligations are at once spatial, temporal and text-semantic, and a violation typically lives in the composition of a multi-step interaction, which is why per-event guardrails miss sequential tool-attack chains. We present a multi-aspect runtime-verification framework that decomposes a natural-language policy clause into a typed spatial/temporal/semantic triple over one canonical event stream, checks each aspect with its own monitoring specification, and fuses the verdicts through a four-valued algebra that carries provenance. The spatial aspect is interpreted over a weighted two-sorted location graph in which mission geometry and information-release topology are one object; we show that these spatial obligations are not in general subsumed by a first-order temporal specification. The past-time aspect runs on the unmodified MonPoly engine, which agrees with our reference monitor at every time point. Across two mission domains, casualty evacuation and contested sustainment, and one civil domain, composition under the precautionary blocking policy drives attack success to zero with no observed false positives and microsecond-scale per-event cost, while every single aspect and every pair leaves a substantial share of attacks succeeding. In a closed-loop experiment a policy-naive planner reaches a violating state in most unshielded missions and in none when shielded, and four refused episodes in five still recover to a compliant outcome.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-06T18:29:27Z
Gustavo Feio, Jorge Coelho, Miguel Flor, Jo\~ao M. Louren\c{c}o, Ant\'onio Ravara
arXiv categories: cs.PL, cs.DC, cs.SE

The Go programming language provides a lightweight abstraction for concurrent programming through goroutines, which are prone to deadlocks. Go includes a runtime detector that aborts execution when all threads are blocked (a global deadlock). However, due to nondeterministic thread scheduling, this runtime mechanism only detects global deadlocks that manifest during execution and cannot identify partial deadlocks, where a subset of goroutines is permanently blocked while at least one remains runnable. Statically detecting local deadlocks is essential for developing dependable concurrent software. While several tools statically detect deadlocks in concurrent programs, few assist developers in fixing them. Detecting and resolving partial deadlocks requires reasoning about complex interleavings and communication patterns, an inherently challenging task. In this paper, we present GoDDaR, a tool that detects unobserved global or partial deadlocks in Go programs and suggests concrete fixes. GoDDaR translates Go source code into an intermediate representation reflecting message-passing communication events and composition patterns. Partial deadlocks are identified through symbolic analysis over this representation. To resolve detected deadlocks, our algorithms transform the intermediate representation to eliminate problematic synchronization patterns, allowing GoDDaR to generate fix suggestions for the original Go source code as a diff. We evaluate GoDDaR on a benchmark suite of representative deadlock examples from literature and git repositories to validate algorithm correctness and compare performance against the state of the art. Results demonstrate that GoDDaR is competitive with top approaches in partial deadlock detection and advances the state of the art in automated deadlock fixing.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-06T22:34:56Z
Nguyen Cong Nhat Le, Claire N. Bonial, John G. Rogers, Neil T. Dantam
arXiv categories: cs.LO, cs.SY, eess.SY

Fault and error detection is crucial for ensuring the correctness of safety-critical systems. Safety verification often addresses reachability of bad system states, where exhaustive state inspection may be intractable due to the large state spaces of complex systems. We propose a reachability relaxation for hybrid trace nets, a useful mathematical model for analyzing concurrent event systems, to efficiently verify system safety. We further use our relaxation to effectively identify invariants, expressions that hold in all reachable states, allowing state-space reduction for efficient verification. Empirically, our approach proves unsafe states unreachable in 1.5x more instances, generates 2.5x more invariants with up to 2 orders of magnitude faster generation times than the baselines in the tested problems.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-06T22:49:50Z
Yanze Li, Ivan Beschastnikh, Alexander J. Summers
arXiv categories: cs.PL

Asynchronous (async) programming is a popular paradigm for managing concurrency. Languages that provide async support typically have a runtime to manage asynchronous executions. These runtimes are critical infrastructure, yet verifying them has received little attention. One reason is that a property that users care most about from an async runtime is a liveness property: tasks submitted to the runtime eventually make progress. Verifying liveness is challenging for libraries that are both concurrent and highly optimized. We present a lightweight and modular proof technique for verifying eventual progression guarantees for Rust async runtimes. We describe this technique in the context of a simple language based on Rust and Rust's async model. We then realize this proof technique as a set of static analyses for Rust and use these to verify eventual progression of several key components of multiple Rust async runtime implementations.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-07T10:40:16Z
Nikolaos Kekatos, Marinelio Chintri, Panagiotis Katsaros, Alexios Lekidis, Tom Nianios, Ioannis Seitoglou, Stylianos Basagiannis
arXiv categories: cs.CR, cs.LO, cs.SE

Cyber resiliency in edge-IoT deployments is fundamentally an economic problem: detection must keep critical processes operating under attack, but defender resources (compute, bandwidth, operator attention) are bounded. Centralised cloud monitoring offers expressive cross-device detection at prohibitive bandwidth cost; purely edge-local monitoring is cheap but blind to coordinated multi-device attacks where the asymmetric balance favours the attacker. We propose a lightweight hierarchical security-monitoring framework, built on formal runtime-verification methods, that occupies the practical middle ground at quantified cost. Each edge device runs a lightweight TeSSLa stream specification (size, payload validity, rate, and timestamp-drift predicates) that emits a four-valued verdict per aggregation window at sub-microsecond per-event cost; the gateway runs a parametric first-order MonPoly monitor over the per-device verdict streams at microsecond-scale per-verdict cost. The edge-to-gateway uplink carries roughly one Boolean per aggregation window per node, orders of magnitude smaller than the raw packet stream. The gateway tier detects coordinated attack patterns that no single-node monitor can see, shifting the asymmetric cost balance toward the defender. Every alert carries a witness set naming the device, the monitor tier, and the predicate that fired, providing an auditable record of the decision. We evaluate the framework on a container-host testbed spanning nominal and attacker nodes across four attack classes (buffer overflow, time spoofing, denial-of-service, and mixed advanced-persistent-threat patterns), and describe the edge- and gateway-tier specifications together with the cost-versus-coverage trade-off as monitor levels are added.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-07T10:49:57Z
Nikolaos Kekatos, Marinelio Chintri, Panagiotis Katsaros, Alexios Lekidis, Tom Nianios, Ioannis Seitoglou, Anastasios Temperekidis, Stylianos Basagiannis
arXiv categories: cs.CR, cs.DC, cs.LO

Security monitoring of edge-IoT fleets faces three structural challenges. (i) A per-node monitor is cheap but cannot see attacks that coordinate across devices. (ii) A cloud monitor sees the full fleet but pays for that view in bandwidth. (iii) Even at the cloud, a monitor built on a single RV engine can be fooled by an attacker who compromises a device, raises one malicious request, and then goes silent: once the events stop, an event-triggered monitor has nothing left to evaluate. We propose a three-layer hierarchical runtime-verification framework that addresses all three. The edge layer classifies events as they happen, the gateway layer aggregates short windows of per-device behaviour, and the cloud layer runs two complementary RV engines. MonPoly handles first-order temporal correlation over the merged alert stream: coordinated overflow (which genuinely quantifies across devices) plus per-device multi-vector APT, escalation, and persistent-campaign patterns. RTLola handles a time-triggered silent-node property that an event-triggered engine cannot detect within a bounded delay under fleet silence. We evaluate the framework on a 15-actor Docker testbed covering eight attack profiles plus a silent-bypass scenario. In the controlled labelled testbed, every device-attributable incident the framework raises names an attacker-labelled device, and the RTLola tier catches silent-bypass attempts the event-triggered tier misses. Per-event monitoring stays in the microsecond range at the edge and gateway, with low end-to-end alert-to-incident latency at the cloud.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-08T11:16:55Z
Nathalie Bertrand (Universit\'e de Rennes, Inria, CNRS, IRISA, Rennes, France), Patricia Bouyer (LMF, CNRS & ENS Paris-Saclay, Universit\'e Paris-Saclay, Gif-sur-Yvette, France), Ga\"etan Staquet (Nantes Universit\'e, \'Ecole Centrale Nantes, CNRS, LS2N, Nantes, France)
arXiv categories: cs.LO

Concurrent parameterized games involve a fixed yet arbitrary number of players. They are described by finite arenas in which the edges are labeled with languages that describe the possible move combinations leading from one vertex to another (n players yield a word of length n). Previous work showed that, when edge labels are regular languages, one can decide whether a distinguished player, called Eve, has a strategy to ensure a reachability objective, against any strategy profile of her arbitrarily many opponents. This decision problem is known to be PSPACE-complete. A basic ingredient in the PSPACE-membership proof is the reduction to the exponential-size knowledge game, a 2-player game that reflects the knowledge Eve has on the number of opponents. In this paper, we provide a symbolic approach, based on antichains, to compute Eve's winning region in the knowledge game. In words, it gives the minimal knowledge Eve needs at every vertex to win the concurrent parameterized reachability game. More precisely, we propose two fixed-point algorithms that compute, as an antichain, the maximal elements of the winning region for Eve in the knowledge game. We implemented these two algorithms in C++, as well as the one initially proposed, and report on their relative performances on various benchmarks.

arXiv abstract · PDF

Formal Verification and Runtime Monitoring · primary corpus · published 2026-10-08T14:00:41Z
Dhruv Nevatia, David Basin
arXiv categories: cs.FL, cs.LO, cs.PL

Many network protocols and distributed systems combine recursion, unbounded local state, and quantitative behaviour such as cost, latency, or reliability. Existing decidability results for networks of pushdown systems are largely qualitative, and do not extend to quantitative analyses, which must jointly track traces and weights. We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems. Finitely summarising a recursive network component requires collapsing the infinite family of runs obtained by pumping its nested loops, and doing so exactly, rather than by over-approximation, is a standing difficulty. We give a class of weight domains where this is possible: pumping semirings, those in which the weights accumulated by such a family collapse to a closed form; informally, the domain must be unable to count iterations. The class admits domains with infinite ascending chains, such as the arctic semiring and downward-closed languages. Over these, we give a terminating saturation algorithm computing quantitative reachability exactly, resting on two ideas: segment tree algebras, a compositional representation of runs, and thermal extensions, which symbolically separate accelerated weights so that further acceleration remains exact. We use this to compute upward and downward closures of context-free languages uniformly, and to lift the algorithm to acyclic networks over "thin" pumping semirings, yielding the first quantitative safety and reachability analyses for networks of pushdown systems.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · cs.SE candidate · published 2026-10-06T00:00:54Z
Bruno Claudino, Ruizhe Xing, Yuanhao Zuo, Tyler Menezes, Anita Sarma, Kostadin Damevski, Zixuan Feng
arXiv categories: cs.SE

One practitioner we interviewed said their team writes "must" instead of "should" when instructing a coding agent, because the agent may treat "should" as optional. Small wording choices matter because agents often fill gaps in their instructions with their own assumptions. Spec-driven development (SDD) asks developers to write a specification, plan, and tasks before the agent writes code. SDD frameworks provide templates for these artifacts, but the templates do not help developers judge whether they have written enough or clearly enough. We studied what good SDD specifications contain. We scored the artifacts of 114 open-source SDD repositories against ISO/IEC/IEEE 29148 and derived practices from the highest-scoring ones. The resulting framework, EPIC, has 40 practices in 10 quality dimensions that guide developers in making expectations and decisions explicit in specifications, plans, and tasks for coding agents. The majority of SDD practitioners (N=15) endorsed every practice. Repositories in the top third of specification quality spent 11.8% of their commits on bug fixes, compared with 20.4% in the bottom third, and had a median of 4x as many contributors. Developers can use EPIC to find and fill the gaps in a specification before the agent does.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · primary corpus · published 2026-10-06T10:58:01Z
Alexander Bastounis, Fabian Circelli, Anders C. Hansen
arXiv categories: math.AP, cs.AI, math.LO

Autoformalisation is increasingly used to verify mathematical texts, including those generated by AI, as in OpenAI's announced proof of blow-up of solutions to the Navier-Stokes equations. In this process, an AI system translates the text from a natural language (NL) into a formal language such as Lean. Once this translation is done, the argument expressed in the formal language can easily be mechanically verified. The purpose of this article is to demonstrate why this process may offer no confidence in the original NL argument, owing to the various difficulties in performing the translation semantically faithfully. In particular, we highlight that the problem of resolving ambiguities in mathematical NL text, which is necessary in order to provide semantically faithful translation, is arbitrarily high up in the Solvability Complexity Index (SCI) hierarchy/arithmetical hierarchy (the SCI $= \infty$). Hence, informally, providing semantically faithful AI autoformalisation is harder than any computational problem including the Halting problem (which has SCI $= 1$). To demonstrate the effect of this result we provide several examples of AI mistranslations of NL statements and proofs into Lean in practice, resulting in mismatches between NL proofs and their Lean `verifications'. These include OpenAI's announced Navier-Stokes proof. In particular, we show that the formalised Lean proof does not correspond to the NL proof of blow-up of solutions to the Navier-Stokes equations.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · primary corpus · published 2026-10-06T12:07:39Z
Christoph Benzm\"uller, David Fuenmayor, Luca Pasetto
arXiv categories: cs.AI, cs.LO

We report on an approach to teaching logic to mixed groups of computer science, mathematics, and philosophy students, based on the logico-pluralistic LogiKEy methodology, used for more than a decade in courses, summer schools, and tutorials. LogiKEy uses classical higher-order logic (HOL) as a universal metalogic in which object logics, classical and non-classical alike, are encoded by defining their semantics; through these semantical embeddings a single proof assistant (e.g. Isabelle/HOL), with its automated theorem provers and (counter-)model finders, becomes one environment in which students learn, experiment with, and compare logics. After making the pedagogical case for proof assistants in the logic classroom, we present a graded sequence of classroom examples, each transition motivated by a limitation of the preceding representation, by a need for more explicit modelling resources, or by a new application. A liars-and-truth-tellers puzzle leads from propositional to modal logic; the Wise Men puzzle leads on to dynamic epistemic logic; Boolos's curious inference illustrates what a higher-order meta-logic buys, even for automated proof search; Chisholm's paradox takes the sequence into deontic logic, and from standard to dyadic deontic logic; and G\"odel's ontological argument brings it to a research-level metaphysical argument. We then rebut the objection that embedding everything in classical HOL is monism rather than pluralism, reflect on three years of teaching such a course, and sketch the portability of the approach beyond Isabelle.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · primary corpus · published 2026-10-06T13:49:10Z
Jonas Bayer, Anna Danilkin, Marco David, Annie Yao
arXiv categories: cs.LO

This article offers an introduction to metaprogramming in Isabelle/HOL for beginners, based on a running example for working with multivariate polynomials. The example is motivated by our formalisation of universal Diophantine pairs. We describe the implementation of the poly_degree command, which computes upper bounds on the total degrees of multivariate polynomials and automatically proves their correctness. The complete metaprogram handles a variety of special cases but herein we present a simplified version for the sake of exposition. We describe our development process and design decisions; our goal is to offer a small and self-contained tutorial on Isabelle/ML, for mathematicians who want to get started with metaprogramming.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · primary corpus · published 2026-10-06T22:00:49Z
Param Biyani, Krishnamurthy Dvijotham
arXiv categories: cs.AI, cs.LO, cs.SE

As autonomous coding agents get increasingly deployed, the risk that accidental or adversarially injected misspecifications in tasks lead to dangerous agent behavior is critical to address. Prior work has shown that agents given such tasks rarely flag the conflict and instead cheat, editing tests or hard-coding expected outputs, and the actions taken to cheat can cause real damage, such as deleting a security defense to make a corrupted test pass. It remains unclear whether such conflicts can be established with independently verifiable evidence before the agent acts. We present SpecGuard, which detects and formally certifies these conflicts between task intent and tests. Given only the task description and codebase, SpecGuard autoformalizes the intended behaviour into a Lean 4 specification. The tests are formalized independently, and the Lean kernel checks whether any implementation could satisfy both formalizations, producing a machine-checked certificate when none can. On conflicted SWE-bench tasks, SpecGuard detects up to 72.8% of conflicts and formally certifies up to 51.1%, with a nearly five-fold lower conflict miss rate than model-based judgment. SpecGuard provides a pre-execution safety check that identifies reward-hacking opportunities through formal certification of task-level conflicts, before any agent behavior is observed. Our code is available at https://github.com/prmbiy/specguard.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · cs.SE candidate · published 2026-10-07T02:11:30Z
Srijith Nair, Aditya Vempaty, Jia Liu, Ashish Jagmohan
arXiv categories: cs.SE, cs.AI

When generating verifiable code, natural language requirements are mapped to machine checked code using LLMs and agentic workflows. A crucial component of this pipeline is specification generation (SpecGen), which produces a formal contract against which an agent can prove implementation correctness. Proof generation can obtain deterministic feedback from a theorem prover, but SpecGen lacks a definitive check that a generated specification captures the user's intent. A checked proof can therefore establish correctness against a specification that misrepresents the intended behaviour. We take a step towards holistic SpecGen evaluation with a unified dataset assembled from $350$ existing Lean tasks, including $189$ from VERINA and $161$ from CLEVER, and a framework covering formal validity, reference similarity and equivalence, and behavioural adequacy. We distinguish acceptance of required inputs from acceptance of valid outputs and rejection of invalid outputs, while making each metric's evidence scope explicit. Across four SpecGen configurations, restricting the generalized tree edit distance (GTED) comparison, a reference similarity measure, to $32$ jointly measurable VERINA tasks changes the VERINA configuration's position from second to fourth in mean similarity, showing the importance of measurement coverage. In an authored control, a specification achieves $100\%$ positive test recall and negative test rejection while accepting $0\%$ of required inputs. This demonstrates that perfect postcondition scores can miss an unusable input contract, motivating separate feedback on input coverage and output constraints.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · primary corpus · published 2026-10-07T08:42:24Z
Shuangjie Yao, Nikolaus Holzer, Mark Paul Santolucito, Baishakhi Ray, Suman Jana, Dongdong She
arXiv categories: cs.AI, cs.LO, cs.PL, cs.SE

Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers. It's a guarantee especially valuable for code generated by large language models (LLMs), which is fluent but carries no assurance of correctness. Almost all existing provers, however, pursue pass rates alone at whatever sampling or search budget it takes, and overlook the success-vs-cost frontier; yet real software often carries hundreds of interdependent proof obligations, so what matters at scale is not whether one theorem can be proved, but how many can be proved economically. We introduce CoCo-Prover, which formalizes cost-efficient program proving as metalevel decision-making under cost, grounded on two-level proof graphs: an AND/OR proof hypergraph within each declaration is joined to a lemma-dependency graph across declarations; and at each step, it answers two questions: which open goals to select, and which actions to purchase on these goals. Selection stays symbolic as a topological pass over the proof graphs. Action choice is agent orchestration via metalevel decision-making: an agentic router treats every bounded specialist invocation as a separately priced, best-effort computation, matching heterogeneous specialist agents together with configurations, under evolved routing rules as evidence accumulates. On five program verification benchmarks in Lean 4 including function-level CLEVER, VERINA, and AlgoVeri, and repository-level NTP4VC and Vero, we show that CoCo-Prover achieves a better success-vs-cost frontier than baselines including frontier coding agents and state-of-the-art LLM-based provers: it achieves the best solve rate on every benchmark and up to 100% on two benchmarks. It also reduces cost by up to 30.9% compared to the strongest baseline with the strongest LLM in our evaluation.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · cs.SE candidate · published 2026-10-08T01:31:58Z
Dominik Blain
arXiv categories: cs.SE

Translating COBOL to a modern language can change what a program computes, and LLM translations carry no guarantee of equivalence. We present IRONPROOF, which parses COBOL into an intermediate representation, generates Python, encodes both as Z3 formulas over shared inputs, and emits either a machine-checkable equivalence certificate (UNSAT) or a counterexample (SAT). On 2,345 COBOL files (GnuCOBOL tests, NIST CCVS85, open-source collections, and programs we generated or wrote), 782 enter the checking path: 606 (77.5%) are proved equivalent, 101 are partially verified, none is refuted, and 75 fail inside our pipeline and stay in the denominator. On independently authored programs the rate is 52.6% (153 of 291), against 92.3% on programs we wrote. Of the 153 independent proofs, 37 cover a single execution of a program that reads input the encoder does not model, and across all 606 proofs only 14 quantify over an input that a proved output depends on. On two public business-application corpora (AWS CardDemo and IBM GenApp), the encoder models no program end to end. An April 2026 LLM-only baseline failed on 54 of 94 independently authored programs, counting translations our encoder could not verify. PIC-bounded overflow detection flags an out-of-range output in 22.1% of the programs it can analyze, an upper bound. An earlier confrontation with GnuCOBOL 3.2.0 found 24 of 49 executable independent proofs disagreeing with the runtime on a variable in the proof's domain. A proof establishes that the generated Python computes what our intermediate representation says the COBOL computes, not equivalence to a COBOL implementation.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · cs.SE candidate · published 2026-10-08T11:24:55Z
Hartwig Grabowski
arXiv categories: cs.SE

The Spec Growth Engine anchors AI-assisted software development in a graph of specifications that the code is coupled to. This paper describes its implementation, which serves two tasks and keeps them apart as two layers. The first layer prevents spec-code divergence: a deterministic engine validates the spec graph, compares it with the code's import graph, earns a node's verified status from recorded test evidence, and classifies every change by what it can break -- without calling a model. The second layer grows the spec with agents: an intent author, a planner and a coder, each played by its own model, extend the graph in rounds, and a deterministic rule decides after each round whether the run goes on. How much of the human's judgement is delegated is set by three independent switches -- a draft gate, a delegation for breaking changes, and the run mode -- which, with two ways of laying a project's floor, give eighteen ways to run a project. We describe each of them, the gates, requests and waivers through which agents and the human communicate, and the spectrum of operation from entirely manual work to an unsupervised run whose decisions the human reviews afterwards. Throughout, one claim holds the design together: an autonomous run is worth only as much as the deterministic instance that measures it.

arXiv abstract · PDF

Proof Assistants and Formalized Reasoning · primary corpus · published 2026-10-08T13:11:53Z
Xavier Allamigeon, Yazid Id-Sahra, Pierre-Yves Strub
arXiv categories: cs.LO, math.CO, math.OC

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-05T01:51:04Z
Ashkan Vedadi Gargary, Guido Mart\'inez, Sebastian Burckhardt, Gabriel Ebner, Abhinav Jangda, Madan Musuvathi, Tyler Sorensen
arXiv categories: cs.PL, cs.DC, cs.LG

AI systems can now write and optimize production GPU kernels, but validating them remains an important challenge. Evaluating the kernel on a few random inputs and checking that its outputs match a trusted reference kernel within numeric tolerances is not sufficient: races can cause nondeterministic behavior that fails to manifest in tests, and numeric tolerances can hide bugs and cause false positives even after extensive calibration. To address this challenge, we present RESOLVE, which combines testing and formal verification to build a comprehensive kernel validation pipeline. It operates in three steps: First, it tests for nondeterminism using binary instrumentation that perturbs execution timing to expose races. Second, an agent rewrites the candidate and reference kernels to obtain "reduced-concurrency" versions that are simpler to analyze but still produce bitwise-identical outputs in all tests. Third, the reduced kernels are formally analyzed in the F*/Pulse framework and prove that they perform the same computation on real numbers. This sidesteps the need for numeric tolerances. We show that RESOLVE can validate a broad selection of kernels using KernelBench, and prove equivalence across fused GEMMs in three state-of-the-art frameworks and languages: CUTLASS, Triton, and Gluon. It also analyzes mega-kernels, notoriously difficult to validate, and finds four previously unreported issues, including two clear bugs. We show that agents can use RESOLVE to repair the issues, with minimal performance impact, highlighting that agents can optimize aggressively when they can rigorously check their results.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-05T09:00:33Z
Daniel Drodt
arXiv categories: cs.PL

Formally reasoning about Rust programs requires a rigorous formal semantics, especially in the context of deductive verification and concurrent programming. We present a modular, flexible semantics for a significant subset of (close to) source code level Rust, based on the recent locally abstract, globally concrete semantics framework, separating local evaluation of expressions from their composition into concrete traces. The semantics is extended to model Rust's asynchronous programming features and Rust's most popular async runtime, Tokio. Based on our more abstract formalization, we establish the fairness of Tokio's scheduler. Further, we show the applicability of our semantics to deductive verification of Rust by providing soundness proofs for a Rust program logic.

arXiv abstract · PDF

Programming Language Semantics and Compilation · cs.SE candidate · published 2026-10-05T11:13:02Z
Boshuai Ye, Peng Liang, Arif Ali Khan
arXiv categories: quant-ph, cs.SE

Quantum compilers synthesize high-level operations, such as the quantum Fourier transform and multi-controlled X gates, into gate-level circuits. Across compilation stages, a circuit may be serialized, exchanged as OpenQASM, converted between compilers, or lowered to gates. These representation changes can preserve computation while removing the high-level operation itself, leaving the receiving compiler unable to apply a requested synthesis method. We call this loss synthesis availability. We study synthesis availability in Qiskit, TKET, and Cirq through controlled experiments, repository analysis, circuits captured from project tests, and a Munich Quantum Toolkit pipeline. Synthesis availability survives serialization when deserialization restores the high-level operation and survives compiler conversion only when the receiving compiler supports that operation. It does not survive the evaluated OpenQASM routes. After a direct OpenQASM 3 round trip, requested synthesis has no effect in all 360 delivered conditions even though compilation succeeds. In the MQT pipeline, OpenQASM 2 interchange increases the two-qubit gate count by 37.2 percent for an eight-qubit Grover circuit. We also introduce Verified, which records high-level operations before a representation change and reconstructs them only when a check confirms that the record still matches the delivered circuit. Verified restores requested synthesis in all 830 recovery runs, with median verification times from 2.0 to 638 ms per operation family. The check rejects every stale record but also some valid records. These results show that preserving functional equivalence alone is insufficient when later synthesis choices depend on retained high-level structure.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-05T15:50:27Z
Michael D. Adams, William E. Byrd
arXiv categories: cs.PL

The miniKanren and Relational Programming Workshop brings together researchers, implementors, and users of the miniKanren family of relational programming languages, including miniKanren, microKanren, core.logic, OCanren, Guanxi, and related systems. The workshop focuses on the design, implementation, and application of miniKanren-like languages, as well as new techniques and tools for relational programming. These proceedings collect the eleven accepted papers presented at the Seventh miniKanren and Relational Programming Workshop.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-05T16:26:02Z
Advait Deshpande, Luciano Baresi, Arosha K. Bandara
arXiv categories: cs.ET, cs.DC, cs.PL, cs.SE

Despite the promise and potential of quantum computing, most of the current day developments of quantum computing have several limitations for relevant practical use. As a result, hybrid classical-quantum computing has emerged as a viable solution. This paper discusses the software aspects of hybrid classical-quantum computing solutions to understand and examine how hybrid computing solutions can be expected to work in practice. This paper examines existing software solutions (cloud applications, middleware frameworks, and API gateways) that can enable classical and quantum computing to work together. For practitioners the paper provides a curated list of algorithms, full stack libraries, simulators, and cloud service providers that are likely to be central to the development of any hybrid computing solutions. We conclude by identifying an agenda for future research on classical-quantum hybrid software engineering, and some near-term priorities for development of functional, robust hybrid software systems. The paper argues that due to the deep dependency of quantum execution on classical pre- and post-processing, hybrid computing may represent a near-permanent outcome of classical-quantum computing rather than a transitional workaround.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-06T00:09:11Z
Zheyuan Chen, Simon Kagle, Tiago Cogumbreiro, Tyler Sorensen
arXiv categories: cs.PL

Warp primitives such as tensor core operations, shuffles, reductions, and barriers are critical to high-performance GPU kernels, and every major GPU language supports some set of them. The threads that participate in a primitive, and therefore synchronize, are determined dynamically by how threads diverge and reconverge, and by intra-warp scheduling such as independent thread scheduling. In practice, many high-performance kernels use these primitives and behave as expected, following an intuitive but unwritten data-race-freedom contract that has never been stated precisely or empirically tested. We present WarpDRF, the first abstract warp programming model to make this contract precise, with participation rules parameterized by reconvergence guarantees and per-primitive requirements so that instantiations match different GPU languages. We prove (formalized in Rocq) that a kernel satisfying WarpDRF executes every warp primitive with the participants the reference semantics assigns and produces the same results, so a programmer can reason in the reference semantics alone. We implement the model in MLIR with a reference interpreter and fuzz 10K conformance tests for each of three configurations across CUDA, HIP, HLSL, Metal, and SPIR-V on 16 device and backend pairs; at least one WarpDRF configuration describes each, with CUDA honoring the strictly weakest configuration. Finally, we extend Faial, a static data-race analyzer for CUDA, into the first DRF checker for an empirically validated warp model, and apply it to llama.cpp, where most kernels that use warp primitives already satisfy the contract, but three contain previously unknown data races, showing the need for tools that check it.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-06T04:37:22Z
David Pissarra, Jinkun Lin, Haitian Jiang, Aurojit Panda, Jinyang Li
arXiv categories: cs.PL, cs.AI

Optimized kernels such as FlashAttention and FlashDecoding are crucial for accelerating today's large models. Most of them are handwritten by experts because existing ML compilers cannot match their efficiency. Producing such kernels requires fusing computations with multiple reductions, which requires both algebraic transformation of the computation graph and operator scheduling of the transformed graph. Unfortunately, searching the two jointly yields a space too large to navigate. We propose Cleave, an ML compiler built on symbolic decoupling: Cleave discovers transformations by performing superoptimization on a graph with symbolic shapes, and then schedules each resulting graph on concrete shapes. Representing shapes as symbols makes equivalence checking cheap and lets a new Split operator, with a symbolic split count, parallelize along a reduction dimension. Cleave's scheduler fuses graphs with multiple reductions through iterative tiling and horizontal fusion. Evaluation on common LLM subgraphs shows that Cleave generates kernels up to 2.8x faster than the best baseline (1.6x on average) and reduces compilation time by 5.9x on average compared to Mirage. For dynamic workloads captured from production serving traces, Cleave compiles each operator once and achieves geometric mean speedups of 1.4x and 1.7x over FlashInfer's handwritten FA2 and FA3 backends. Cleave's code is available at: https://github.com/nyu-systems/cleave

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-06T19:00:45Z
Brett Saiki, Bill Zorn, Cynthia Richey, Zachary Tatlock
arXiv categories: cs.PL

Number libraries, which implement number formats and their arithmetic in software, are used to simulate hardware, making hardware behavior reproducible and thus verifiable and easier to design. However, modern machine learning accelerators are difficult to simulate, as they increasingly use specialized number formats that existing number libraries do not support. It is costly to extend these libraries using traditional methods: each combination of operation, format, and rounding mode typically requires a bespoke implementation. An easier way is to double round---compute at higher precision, then re-round---so that one high-precision kernel serves many formats, but double rounding is only known to be correct in select cases. We give a precise, efficiently checkable characterization of when double rounding is correct across many formats and rounding modes. Our result rests on a novel abstract number format that unifies fixed- and floating-point representations, reducing the correctness of double rounding to format containment: whether every value of one format is representable in another. We mechanized these results in Lean 4. In addition, we introduce a format inference algorithm that, given a sequence of operations, bounds each expression by a number format guaranteed to contain its result. We apply these insights in two ways. First, we present MPFX, a correctly-rounded, multi-precision number library that exploits correct double rounding to efficiently simulate many number formats. MPFX's correctly-rounded operations are up to 11x (mean: 6.05x) faster than MPFR's, and competitive with SoftFloat's---between 0.46x and 1.63x as fast (mean: 0.94x)---at the same precision. Second, in a case study, we implement a software simulation of a hardware specification using both SoftFloat and MPFX's primitives; the MPFX version is up to 13.5x faster.

arXiv abstract · PDF

Programming Language Semantics and Compilation · cs.SE candidate · published 2026-10-07T17:07:35Z
Rylan Malarchick
arXiv categories: quant-ph, cs.SE

A pulse-level quantum control program is written against a device whose limits are recorded, if at all, in vendor documentation and source code. A program that exceeds them can be refused at compile time. It can also be accepted and silently altered, or compile and then fail at the board. In the last two cases the experiment runs, and the data does not correspond to the program that was written. We present qconform, a checker that decides whether a pulse program is realizable on a device, given a versioned capability descriptor for that device. Every constraint in a descriptor cites the toolchain observation that established it. The checker is design-time, offline, and deterministic, and it uses no floating point. It reports a verdict, the rules it applied, and a coverage manifest that names what it did not check. We evaluate qconform by differential testing against the QICK and Qblox toolchains, on three QICK board configurations and one Qblox cluster. Over 1263 program runs of 969 distinct programs, the checker accepted no program that a toolchain refuses. On both vendors, a descriptor pinned to one toolchain release accepts programs that older releases refuse. The evaluation also found ten defects in the checker and its descriptors, all fixed.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-07T18:51:37Z
Feras A. Saad
arXiv categories: cs.PL, cs.LO

Probabilistic programs provide a rigorous programming-language foundation for expressing rich probabilistic models and offer language-level support for solving challenging statistical inference problems. A key theoretical challenge that probabilistic programs inherit from probability theory is conditioning a probability distribution on an observation that has probability zero. Many languages address this challenge by using computational rules for conditioning that may work well for some problems but are statistically unsound for others. This article introduces a principled mathematical approach for conditioning probabilistic programs. We first show that existing techniques based on "soft conditioning" and "neighborhood limits" exhibit semantic issues from the perspective of measure theory and produce inference results that disagree with sound statistical reasoning. By leveraging tools from geometric measure theory, we construct a novel disintegration-based semantics for probabilistic program traces that enables sound conditioning. The theory delivers an explicit Bayes rule representation of the conditional distribution, which is directly compatible with widely used probabilistic inference algorithms that require access to unnormalized posterior densities. Our Bayes rule handles probabilistic models with loops, branches, discrete, continuous, and mixed-type distributions, observations on manifolds, differentiable structure, and additional modeling motifs that arise in practice.

arXiv abstract · PDF

Programming Language Semantics and Compilation · cs.SE candidate · published 2026-10-08T03:58:37Z
Mushahid Khan, Olivia Di Matteo
arXiv categories: quant-ph, cs.SE

Quantum compilers play a critical role in transforming high-level quantum programs into optimized, hardware-compatible circuits. However, verifying the correctness of compiler passes remains challenging, as determining the expected output of large, deeply entangled quantum circuits is computationally intractable. This challenge is further amplified when compiler passes modify already complex circuit structures, making manual validation of transformed circuits impractical. In this work, we perform a systematic analysis of unit tests for quantum compiler passes in four quantum programming frameworks (PennyLane, Qiskit, Cirq, and pytket). Our findings indicate validation is dominated by program-content and program-metric assertions, and test circuits are generally small and shallow. Motivated by these observations, we introduce a testing methodology for automated validation of quantum compiler passes based on retromorphic testing and principles from the Hadamard test. This methodology analyzes a compiler pass, test circuit, and expected pass behavior to verify semantic preservation and intended structural modifications. We implement our methods in a framework, RetroQ, and apply it to compiler passes in PennyLane and Qiskit. Experimental evaluation reproduced several existing bugs as well as uncovered previously undetected defects, such as flawed symbolic parameter handling, incorrect commutation logic, failure to recognize self-adjointness of gates, and runtime crashes. These findings highlight the need for compiler-pass-specific testing methodologies to improve the reliability of the evolving quantum software stack.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-08T19:28:31Z
Huanzhi Pu, Chulhyung Park, Chihyo Ahn, Ramyad Hadidi, Hyesoon Kim
arXiv categories: cs.AR, cs.PL

GPU architecture research requires representative benchmarks that can execute on new designs. However, many vendor-tailored workloads and library kernels cannot run directly on research architectures because their implementations are closed-source or rely on programming models unsupported by the target architecture. Migrating existing kernels requires manual effort to adapt their implementations and validate their behavior. This creates a need to automate workload migration to target platforms. We present VortexSynth, a framework that uses profile-guided benchmark reconstruction to construct GPU benchmarks from reference workloads. Our workflow selects hot kernels through profiling, synthesizes implementations in the target programming language, verifies output equivalence, and measures profile differences using a translated proxy implementation. The resulting profile signature gap is supplied to an agent for iterative refinement. We evaluate the method on Vortex, an open-ISA GPGPU, using robotics as the application domain. All active kernel pairs pass both output-equivalence checks, and the case studies show that iterative refinement can reduce profile distance.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-09T03:03:03Z
Houston Haynes
arXiv categories: cs.PL, cs.DC, cs.LO

Clef was created as a concurrent programming language whose compiler tracks state ownership, waiting computations and request dependencies. We develop a coexponential account of stateful services and their client pools within this design. Delimited continuations retain the computation and resources needed to complete each interaction. These structures give our compiler premises for verifying service composition and preserving it through native lowering to multiple hardware targets. We connect finite actor state transitions to the initial, service and final rules of a coexponential server. A separate operational account relates actor dispatch to single-use continuation frames. We prove state-ownership and reply preservation for that translation, give a finite communication-summary analysis, and circular-wait exclusion from the conditions needed. A further result identifies when changing service order preserves both state and replies. Our Program Semantic Graph retains these facts through compilation. We are researching reusable proofs to confirm the ownership and communication interfaces, while our BAREWire implementation connects message meaning to its unboxed representation across respective endpoints. A distributed worker example preserves request identity across suspension, reordered replies and boundary conversion. Urschel's elimination-growth bounds supply quantitative premises for a solver service, whose accuracy and failure budget compose with the protocol contract. The design we envision connects automatic structural analysis, reusable proof terms and native realization. Protocols determine the admissible interactions, continuations expose their storage requirements, and retained dependencies support differential compilation. Developers can express ordinary stateful services while the compiler carries the conditions for their correct composition across execution targets.

arXiv abstract · PDF

Programming Language Semantics and Compilation · primary corpus · published 2026-10-09T14:45:50Z
Nan An, Xiaotian Zhou
arXiv categories: cs.PL

The layout algebra behind NVIDIA's CuTe library describes how tensor tiles map onto threads and memory. A layout is a shape with a stride for each entry, so a coordinate's address is the sum of its indices times their strides. As formalized by Shah and by Cecka, its central operations (e.g., composition, complement, division, product) are guarded by at least six interacting admissibility conditions. We show that this complexity is an artifact of a representational choice, not of the domain. We present a layout algebra in which every layout names the space its inputs and outputs live in: logical, physical, or thread-value indices. A layout into logical or thread-value space must be a bijection from its $N$ coordinates onto $[0,N)$. A layout into physical space must be alias-free: distinct coordinates land on distinct addresses, except under broadcast, where many threads read one value on purpose and the layout must mark where. Nothing maps out of a physical index. Composing $f$ with $g$ requires only that $f$'s range be exactly $g$'s flattened coordinate set. The index arithmetic can always be emitted naively: compute $f$, split the result by division and remainder into $g$'s coordinates, and apply $g$. Often the composite simplifies to a layout; we show that when it does, there is a coarsest such form, whose digits every other one refines, and we emit that. A warp's or thread's slice is a \emph{restriction}. A restricted layout is no longer composable, which forces the user to settle the whole view of a tile before taking slices. We validate the algebra by reproducing within it CuTe's operations, such as composition, complement, and division. We implement it in OCaml and use the implementation to rederive CuTe's atoms and usage patterns. The decision procedure is proved correct in Rocq.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-05T11:18:42Z
Morgan May, Simon Caton, Pierpaolo Dondio
arXiv categories: cs.AI, cs.CV, cs.LG, cs.LO

Accurately quantifying the predictive uncertainty or improving model calibration plays an important role in medical image classification, in particular in melanoma diagnosis, where accurate uncertainty quantification can have significant implications for patient care. One of the methods for calibration improvement is data augmentation. In addition, data augmentation as a method for synthetically increasing the size of the dataset has been proven to improve the performance of models trained on imbalanced datasets. However, the impact of data augmentation, as a transformation of a part of the original data, on calibration of models trained on imbalanced datasets, in particular in melanoma classification is under-explored. We train neural networks on SIIM-ISIC 2020 melanoma classification dataset under two conditions: with and without data augmentation, and compare the differences in AUC and expected calibration error (ECE) in both scenarios. Our results shows improvements in uncertainty calibration using different augmentation methods.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-07T03:08:11Z
Nam H. Le
arXiv categories: cs.NE, cs.LO

Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output. A substantial line of work instead makes the program an input to a separate learner, so fitness measures the learner's output rather than the program's. Which learner to attach matters, with no account of what decides it. What makes a target hard for genetic programming is how much nonlinearity the program must build by composing primitives; whatever nonlinearity the learner supplies, the program need not. The quantity to measure is therefore how much of a target's nonlinearity a learner can take over, though on continuous benchmarks it can only be estimated. Here we show that how much the program must still build is decided by which learner is attached, and is measurable on the programs themselves. Moving to Boolean domains, where a target's nonlinearity is exactly its Fourier degree, we tune that degree from one to six with everything else fixed. Conditioned on success, a linear learner forces the evolved program to the target's degree exactly, at one through six without exception over thirty runs per setting, while tree ensembles succeed with far simpler programs and four times as often. This gives the field two things: a learner can be chosen from a target's structure instead of its reputation for difficulty, and the degree of the evolved program is a diagnostic free to compute during any run. Our control target has lower degree than the parity problems yet gains nothing from a nonlinear learner, while targets reducible to a simple statistic gain a great deal. The latter comes with a warning: evolution internalises what the learner supplies in only four of sixty-three conditions, and grows more dependent on it in forty-four, so the more capable the learner, the less of the model is legible in the program.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-07T06:29:42Z
Nishant Balepur, Kiran Tomlinson, Tobias Schnabel
arXiv categories: cs.SE, cs.AI, cs.PL

Repository benchmarks (e.g., SWE-bench) for coding agents often assume that lines of code edited can predict task difficulty, but such datasets' poor control over code and task types makes it hard to know which abilities truly drive agent errors. We present CABRA: a Coding Ability Blueprint for Rigorous Agent evaluation. CABRA builds tasks from scratch as call graph transformations and scales difficulty via a task size parameter on four axes: function traversal, search, runtime resolution, and instruction following. We run eight LLMs and six coding agents on 6,840 CABRA tasks to show: 1) LLM accuracy falls as task size~grows, but agents stay near-perfect by offloading work to tools (e.g., grep); 2) Larger CABRA tasks elicit more tool calls for reading and analysis, while a separate study on SWE-bench Verified shows these tool call counts predict agents' accuracy better than lines of code edited, suggesting task difficulty for agents can lie in understanding code to edit, not just in making edits; 3) Extending CABRA to an intense understanding task where models analyze divergent logic across two classes backs this finding, as agent accuracy finally falls. More broadly, we argue for synthetic evaluations like CABRA to unmask LLM weaknesses trivialized by tools (e.g., needle-in-a-haystack) and abilities beyond just editing (e.g., understanding) that coding agents still find difficult, pairing SWE-bench-style tasks with controlled diagnosis.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · cs.SE candidate · published 2026-10-07T07:58:04Z
Shuangjie Yao, Hao Wang, Koushik Sen, Simin Chen, Baishakhi Ray, Dawn Song
arXiv categories: cs.SE, cs.AI

Large language model (LLM) agents are rapidly reshaping software engineering, accompanied by an explosion of new code benchmarks. Yet nearly all existing benchmarks still rely on the same decades-old criterion: a solution is correct if it passes a fixed set of unit tests. Such tests are often insufficient: they check only part of what the task requires, so agents can reward hack them or silently miss required behavior while still passing every test. As a result, higher benchmark scores may partly reflect better adaptation to the evaluator rather than better problem solving. Existing works focus on static test augmentation: they strengthen each task's tests once, before any trial is seen, and thus overlook how real trials actually fail. We introduce TestJack, a scalable framework for evaluating patches beyond fixed tests. For each trial, TestJack generates tests targeting prompt requirements the patch may violate, retains only tests passed by the ground-truth patch, and re-examines any trial failures. Each confirmed failure is thus supported by a replayable test. To reduce evaluation cost, we also introduce a lightweight variant which audits a random sample of trials in depth and reuses the resulting tests across all trials for the same task. Across 6 frontier model backends and 5 benchmarks such as DeepSWE and SWE Marathon, we find that about 34.4% of the model trials currently judged correct violate the task requirements, lowering the overall resolution rate from 50.6% to 33.2%. Our results reveal a fundamental limitation of current coding-agent evaluation: as LLMs become better at optimizing against fixed evaluators, those evaluators themselves must become more adaptive.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-07T16:25:20Z
Batuhan Yeltekin, Daniel Bauer
arXiv categories: cs.SE, cs.PL

We evaluate 13 LLMs on generating, solving, simulating, and diagnosing novice programming misconceptions on code-tracing problems. While frontier models reliably perform these tasks, small models ($\le$14B) struggle with dynamic execution. Notably, code-tuned models fail during misconception simulation by reverting to correct execution. Finally, misconception diagnosis is significantly easier in True/False formats than in open-ended generation tasks.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-08T04:19:47Z
Weizhe Xu, Jialiang Fan, Mengyu Liu, Fanxin Kong
arXiv categories: cs.RO, cs.AI, cs.CL, cs.LO

Large Reasoning Language Models (LRLMs) enable multi-step reasoning for robotic task planning, but continued reasoning can overwrite valid intermediate plans or leave constraint violations unresolved, reducing planning reliability and wasting inference-time computation. We develop an inference-time monitor that exposes and verifies intermediate plans without disrupting the original decoding trajectory. Building on this monitor, we propose SafeInferCom, a formal verifier-guided framework that preserves valid intermediate plans and directs error correction during generation. Experiments across multiple LRLMs and planning domains reveal reasoning-response inconsistency and limited self-correction under one-shot inference. SafeInferCom improves planning success and accelerates error correction relative to one-shot inference. When combined with iterative refinement, it further improves success while reducing token usage compared with refinement alone. We additionally evaluate SafeInferCom in VirtualHome and provide a real-world robotic-arm demonstration.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-08T15:42:27Z
Lars Simon, Holger Eble, Manuel Radons
arXiv categories: cs.AI, cs.LG, cs.LO

We introduce a self-improvement loop for reasoning models based on the following observation: Even when the difficulty of a problem exceeds the model's current solving abilities, an additionally supplied solution might enable the model to extract useful solution ideas in hindsight. We operationalize this by jointly training the same model to exhibit the following three capabilities: predicting solution ideas from problems alone, reverse-engineering ideas from problems and known solutions, and solving problems using provided ideas. The loop alternates between reverse engineering such ideas from problems with supplied solutions and using these ideas as additional supervision for joint training of all three capabilities. We give a formal specification of our method and a concrete instantiation for interactive theorem proving in the Lean theorem prover; empirical evaluation remains future work.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-08T22:35:57Z
Oleg Grynets, Ivan Fedorchuk, Vasyl Lyashkevych
arXiv categories: cs.SE, cs.DB, cs.LO

This paper presents a leakage-resistant framework and benchmark (LRFB) for measuring evaluators of AI-generated Oracle PL/SQL specifications. The benchmark contains 494 labelled source-specification pairs across 19 quality metrics grouped into seven dimensions; each metric contains 26 records divided into development and held-out subsets of 13 records each, with three clean and ten defective specifications per subset. Ground truth is mechanically sealed from inference and checked with canary and label-permutation tests. Three LLM judges were evaluated with three runs per record and compared against two trivial baselines. On 247 held-out records, GPT-4o, DeepSeek V4 Pro, and Claude Sonnet 4.5 reached balanced accuracies of 0.87, 0.89, and 0.81, respectively, while a specification-length baseline reached 0.88. Exact paired tests did not separate any judge from that baseline. The judges nevertheless provided information unavailable to length: the labelled defect category appeared among findings in 84%-92% of violated records, and quoted evidence overlapped the labelled span in 92%-93%. The study therefore reframes specification evaluation from binary issue detection toward evidence-linked, typed findings and benchmark-validity controls.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · cs.SE candidate · published 2026-10-09T06:26:02Z
Kazuki Egashira, Niels M\"undler-Sasahara, Mark Niklas M\"uller, Martin Vechev
arXiv categories: cs.SE

Coding agents are increasingly used to create large software projects. While code-generation benchmarks have scaled accordingly to full applications, test-generation benchmarks remain limited to individual functions or bug fixes. In particular, generating complete test suites for complex software from scratch remains unexplored. To address this gap, we introduce TestSuiteBench, a benchmark of 165 open-source applications, each with a structured and detailed specification of intended behavior, a reference implementation, a reference test suite, and on average 74 mutants. Each mutant is generated from a single requirement of the specification and refined to isolate that behavior: 73\% are killed by exactly one reference test and, on average, by only 0.2\% of the remaining tests. We find that even frontier coding agents struggle to generate strong test suites given our specifications, achieving mutation scores below 60\%, despite their suites being largely valid and 88\% of their tests passing on the reference implementation. We observe that generated test suites often lack relevant input combinations and are smaller than reference test suites. Meanwhile, implementations generated for the same specifications pass 82\% of the reference tests. These results show agents can build software they cannot verify, a gap that directly limits fully autonomous software development.

arXiv abstract · PDF

Machine Learning and Language Model Evaluation · primary corpus · published 2026-10-09T11:59:46Z
Pablo Manrique, Hai Xia, Stefan Szeider
arXiv categories: cs.AI, cs.LG, cs.LO

AI systems are making rapid progress in mathematics, but this progress is hard to measure. Benchmarks of solved problems saturate, and in benchmarks of open problems each problem can be resolved for the first time only once. We present SqueezeBench, a benchmark that is resilient to saturation: a success raises the bar instead of removing the problem. Each problem fixes an integer function $f(n)$ whose values are known only for small $n$, and the benchmark keeps a lower and an upper record on it. A record is a computable Lean function with a machine-checked proof that it bounds $f$. A submission proposes a new function and proves that it bounds $f$, that it is no worse than the current record at any $n$, and that it is strictly better at some $n$. Once accepted, it becomes the record that the next submission has to beat. The system thus chooses the bound as well as its proof, and it may improve the record at a single $n$ or its growth rate. At every $n$, the gap between the two records shows how far the certified bounds are from determining $f(n)$. Every proof is checked by two independent Lean kernels, so no referee needs to check the mathematics. The checks also reject a function that computes $f$ by exhaustive search at small $n$, and a maintainer only reads the submitter's report and looks for such a search at larger $n$. We release ten problems from extremal combinatorics with twenty proved initial records and the admission tools. As a baseline, agents based on a frontier language model, with at most one hour per record, had 82 submissions accepted and improved every record, without going beyond the published literature. Agents based on two newer models then started from these records, had 60 more submissions accepted and improved 19 of the 20 records again. For eight of the ten problems, at least one record is still asymptotically behind the best published bound.

arXiv abstract · PDF