# Arithmetic Circuits and Neural Networks for Regular Matroids

arXiv: https://arxiv.org/abs/2511.02406 · HTML: https://mlsanity.com/paper/2511.02406/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 4 Nov 2025.

## Builds on (most cited first, 20 of 20)

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [A Tropical Approach to Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/1805.08749/) (2018)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size](https://mlsanity.com/paper/2005.14105/) (2020)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [On Minimal Depth in Neural Networks](https://mlsanity.com/paper/2402.15315/) (2024)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [On the Depth of Monotone ReLU Neural Networks and ICNNs](https://mlsanity.com/paper/2505.06169/) (2025)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid](https://mlsanity.com/paper/1811.01816/) (2018)
- [Convexity in ReLU Neural Networks: beyond ICNNs?](https://mlsanity.com/paper/2501.03017/) (2025)
- [Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids](https://mlsanity.com/paper/1807.00929/) (2018)
- [Strengthening Convex Relaxations of 0/1-Sets Using Boolean Formulas](https://mlsanity.com/paper/1711.01358/) (2017)
- [Integer programs with nearly totally unimodular matrices: the cographic case](https://mlsanity.com/paper/2407.09477/) (2024)

## Built on by (most cited first, 2 of 2)

- [Tropical Circuits with Scalar Multiplication Gates](https://mlsanity.com/paper/2607.11540/) (2026)
- [Two Linear Programs are Better than One](https://mlsanity.com/paper/2610.15909/) (2026)

## Abstract (arXiv)

We prove that there exist uniform (+,×,/)-circuits of size O(n3) 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 for the base polytope of regular matroids of size O(n6) 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.