CS Paper Radar

On the Representational Geometry of Dynamic Programs

Richard F. M. Lim, Ruriko Yoshida

cs.LG cs.DMmath.AGmath.CO ·submitted 2026-08-25 18:23 UTC · v1
theory

Abstract

Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels --- formal polynomials and their computed functions --- connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.

Comment
13 pages, 7 figures; submitted to NeurIPS 2026 Workshop on Symmetry and Geometry in Neural Representations (Extended Abstract Track)

Closest papers

Nearest neighbours by meaning across the whole index.

Step Recursion: Resource Profiles and Descent Quotients

cs.CC cs.LO ·2026-08-23 ·Kirill Osipov
similarity 0.60
Abstract · Companion to arXiv:2608.04871

We develop a resource representation for step recursion in which mutable-state width and recursion descent are explicit and independent parameters. A width bound $u$ controls the size of the encoded machine state, while an effective descent $ρ$ determines the available recursion depth $δ_ρ(u)$. For generalized-inverse descents, we derive the depth directly from generator growth and characterize the increasing sequences that can occur as generator orbits. We then connect this depth--width geometry to standard finite-branching computation. Every deterministic bounded-state dynamics is realizable by a single ordinary bounded step recursion over a fixed finite numerical basis. Using deterministic, existential, universal, or alternating aggregation on the same local dynamics yields the corresponding machine semantics. After closure under the width reparameterizations needed to absorb fixed local cost, the resulting language classes are exactly the machine time--space classes on profiles $(δ_ρ(u),u)$. Finally, profile domination quotients effective descents by admissible width reparameterization. Some depth curves collapse, yet polynomial widths support an explicit infinite strict hierarchy between the canonical polynomial- and exponential-depth profiles. Thus descent remains a nonredundant resource coordinate after polynomial width reparameterization; standard complexity classes are calibration points.

0.32

Lossless First-Action Menus for Linear-Reward Planning

cs.AI ·2026-11-15 ·Yukun Yang
theory similarity 0.59
Abstract · 8 pages, 0 figures

We study sequential decision making where an agent reserves a minimum menu of initial actions before multi-objective trade-offs are revealed, followed by unrestricted continuation planning once linear reward weights arrive. We prove that a menu preserves the unrestricted optimal return across all linear scalarizations if and only if its reachable continuations cover all vertices of the full feature polytope. This geometric equivalence yields an output-sensitive algorithm that is fixed-parameter tractable in the vertex count, combining scalar backward induction with oracle-based facet identification. On explicitly layered graphs with unit feature increments, menu verification is coNP-complete and synthesis is complete for the second existential level of the polynomial hierarchy, even under additive loss strictly below one. In fixed dimensions two and higher, verification is polynomial whereas synthesis remains NP-complete, while one-dimensional instances admit polynomial-time solutions.

0.26

Two Linear Programs are Better than One

cs.CC math.COcs.DMcs.LG+1 ·2026-10-11 ·Alexander E. Black, Christoph Hertrich, Stefan Kober, Georg Loho
similarity 0.58
Abstract

The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $Θ(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.

0.34

Reconfiguration of Time-Bounded Descriptions

cs.CC cs.DM ·2026-11-06 ·Dimitrios Myrisiotis
similarity 0.58
Abstract · 50 pages

Time-bounded Kolmogorov complexity measures a string by the length of its shortest program that prints it within a deadline. An adjunction-universal machine (Bauwens, Kozachinskiy, and Shen, arXiv, 2025) is a Turing machine that simulates every Turing machine $M$ on every input $z$ with polynomial overhead when given a code of $M$, computable from $M$ in polynomial time, followed by $z$ unchanged. Any two adjunction-universal machines give the same measure up to an additive constant and a polynomial change of the deadline. However, this measure records only the shortest program for a string. We study all programs of one length that print a string within one deadline, join two of them when they differ in one bit, and ask when this graph is connected. Fix any adjunction-universal machine. For almost all $m$-bit strings and every deadline beyond some polynomial, the graph is disconnected at program length $m+O(1)$ and has at least $2^{m-O(1)}$ components at length $2m+3$. In contrast, we build an adjunction-universal machine in which every such graph is connected or empty, at every deadline, once the program length reaches a computable threshold that is at most exponential in the length of the string. Exponential thresholds are unavoidable: for every adjunction-universal machine with such thresholds and every large $m$, more than three quarters of the $m$-bit strings need a threshold exponential in $m$. For our machine, above the threshold, every program for the string is within three bit flips of a connected set of fastest programs for the string, along a path inside the graph, at every deadline by which that program halts. For this machine, deciding whether two given programs are connected in this graph is $\mathsf{PSPACE}$-complete when the input is the string, the deadline in unary and the two programs; for each fixed string it takes polynomial time.

0.29

Formal Grammars and Generating Functions: From Algebraic Structure to Non-Algebraic and Non-Derivable Series

cs.FL ·2026-10-22 ·Zhijun Wang
theory similarity 0.57
Abstract

This paper investigates how the algebraic and analytic properties of ordinary length generating functions constrain the grammatical and computational complexity of formal languages. We review the Chomsky-Schutzenberger representation, DSV translations for unambiguous context-free grammars, and their stack-indexed extensions, distinguishing finite algebraic systems from more general constructions. Examples and a diagonal argument demonstrate that even a rational generating function need not determine a language's grammatical class. Our central computability result establishes that, for a recursively enumerable language, computability of its length-counting sequence is equivalent to decidability of membership. Consequently, if a recursively enumerable language has a D-finite length generating function over Q(z), it is decidable; equivalently, undecidable recursively enumerable languages cannot have D-finite length generating functions. We then examine coefficient growth and singularities through Pringsheim's theorem, the Polya-Carlson dichotomy, Hadamard gaps, and Siegel G-functions. The resulting picture is asymmetric: analytic properties provide useful one-way constraints on language computability, but length enumeration loses too much information to determine grammatical or computational complexity without additional assumptions.

0.12

Solving polynomial equations over partial discrete dynamical systems

cs.DM ·2026-09-30 ·Maximilien Gadouleau, Sara Riva, Marius Rolland, Marie-Emile Voge
similarity 0.57
Abstract

The analysis of observable phenomena (for instance, in biology or physics) allows the detection of dynamical behaviours. If the conditions are ideal and the number of observations is sufficient, we can represent these phenomena by a dynamical system, also called a functional digraph, that is to say a graph where each node has out-degree exactly one. Up to isomorphism, these dynamical systems, equipped with disjoint union as addition and direct product as multiplication, form a commutative semiring. Several previous studies on this semiring have aimed to establish algebraic properties (primality, injectivity) or complexity results (division, factorisation). However, no work has yet been conducted on graphs derived from imperfect observations that result in missing transitions or nodes, in other words, in cases where each node in the graph has an out-degree of at most one. In this case, we say that the system is partial. In this paper, we show that partial dynamical systems, up to isomorphism and equipped with the same addition and multiplication, still form a commutative semiring. We then characterise the prime elements of this semiring, which differ from those of the semiring of dynamical systems. Finally, we highlight two properties shared by both semirings. First, injective univariate polynomials admit the same characterisation in both. Second, division can be computed in polynomial time for partial dynamical systems if and only if it can be for dynamical systems.

0.34

Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks

cs.LG math.ACmath.AG ·2026-09-11 ·Sepehr Akbari, Shahrzad Jamshidi
similarity 0.57
Abstract · 9 pages, 1 figure

We study exact representability by bias-free shallow polynomial neural networks using algebraic geometry. Over $\mathbb{C}$, a width-$r$ network with activation $z\mapsto z^d$ computes a sum of $r$ $d$-th powers of linear forms, whose Zariski closure is a Veronese secant variety. Ideal elimination therefore yields polynomial certificates of nonrepresentability. We implement this construction as a generic architecture-to-certificate pipeline. For quadratics, we recover the exact symmetric determinantal description and explain its dimension through orthogonal symmetry. In higher degree, the implementation recovers classical catalecticant and secant equations and maps the practical reach of direct elimination across a finite architecture sweep. We also derive the exact population loss floor for a rank-two quadratic network on the sphere, illustrating how an algebraic obstruction induces irreducible approximation error.

0.22

Quantitative Verification of Infinite-State Networks

cs.FL cs.LOcs.PL ·2026-10-08 ·Dhruv Nevatia, David Basin
top venue similarity 0.56
Abstract · Accepted at POPL 2027. Full version with appendices, 46 pages, and 13 figures

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.

0.44