Arithmetic Circuits and Neural Networks for Regular Matroids
This provides an incremental advance in computational complexity and linear programming theory by offering more efficient circuits and formulations for regular matroids.
The paper tackles the problem of computing the basis generating polynomial for regular matroids, achieving uniform circuits of size O(n^3), and extends this via tropicalization to neural networks for weighted basis maximization. This leads to a linear programming result where a difference of extended formulations outperforms the best known individual formulation of size O(n^6).
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.