The paper examines why standard neural architectures struggle to generalize to longer inputs when solving dynamic programming (DP) problems. It shows that every finite min-plus DP can be represented as a shortest‑path problem on a directed acyclic graph, equivalently as a tropical polynomial whose extended Newton polyhedron captures the decision boundary of the winning path. The authors prove that the graph, polynomial, and polyhedron descriptions form isomorphic semirings at both the formal polynomial and computed function levels, and they demonstrate that the natural dimensionality‑reduction operations in this semiring are neither injective nor closed, revealing structural limitations that hinder length‑generalization.
By Richard F. M. Lim, Ruriko Yoshida
arXiv:2609. 28500v1 Announce Type: cross Abstract: We study exact representability by bias-free shallow polynomial neural networks using algebraic geometry.
By Sepehr Akbari, Shahrzad Jamshidi
The paper introduces a computational tropical geometry framework for symbolically analyzing neural networks with tropical activations. It presents an algorithm that computes the network’s linear regions as explicit unions of polyhedra, proves its correctness, and connects the number of linear regions to the monomials in the tropical expression. The authors also define the Hoffman constant to bound distances to the farthest linear region and release the open‑source Julia library TropicalNN.jl to implement these tools, demonstrating their use on proof‑of‑concept examples.
By Paul Lezeau, Thomas Walker, Yueqi Cao, Shiv Bhatia, Anthea Monod
arXiv:2508. 03867v2 Announce Type: replace-cross Abstract: We introduce a class of algebraic varieties naturally associated with ReLU neural networks, arising from the piecewise linear structure of their outputs across activation regions in input space, and the piecewise multilinear structure in parameter space.
By Yulia Alexandr, Guido Mont\'ufar
arXiv:2607. 11540v1 Announce Type: cross Abstract: We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement $\max$, $+$, or multiplication with a positive constant.
By Christoph Hertrich, Moritz Stargalla
arXiv:2410. 04907v2 Announce Type: replace-cross Abstract: In this paper we contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a difference of two convex CPWL functions.
By Marie-Charlotte Brandenburg, Moritz Grillo, Christoph Hertrich