Arithmetic Circuits and Neural Networks for Regular Matroids

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 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.