{"ID":2846145,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.02406","arxiv_id":"2511.02406","title":"Arithmetic Circuits and Neural Networks for Regular Matroids","abstract":"We prove that there exist uniform $(+,\\times,/)$-circuits of size $O(n^3)$ to compute the basis generating polynomial of regular matroids on $n$ elements. By tropicalization, this implies that there exist uniform $(\\max,+,-)$-circuits and ReLU neural networks of the same size for weighted basis maximization of regular matroids. As a consequence in linear programming theory, we obtain a first example where taking the difference of two extended formulations can be more efficient than the best known individual extended formulation of size $O(n^6)$ by Aprile and Fiorini. Such differences have recently been introduced as virtual extended formulations. The proof of our main result relies on a fine-tuned version of Seymour's decomposition of regular matroids which allows us to identify and maintain graphic substructures to which we can apply a local version of the star-mesh transformation.","short_abstract":"We prove that there exist uniform $(+,\\times,/)$-circuits of size $O(n^3)$ to compute the basis generating polynomial of regular matroids on $n$ elements. By tropicalization, this implies that there exist uniform $(\\max,+,-)$-circuits and ReLU neural networks of the same size for weighted basis maximization of regular...","url_abs":"https://arxiv.org/abs/2511.02406","url_pdf":"https://arxiv.org/pdf/2511.02406v1","authors":"[\"Christoph Hertrich\",\"Stefan Kober\",\"Georg Loho\"]","published":"2025-11-04T09:37:14Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.CC\",\"cs.DM\",\"cs.LG\",\"math.OC\"]","methods":"[]","has_code":false}