Arithmetic Circuits and Neural Networks for Regular Matroids
The paper proves that there are efficient arithmetic circuits of size O(n^3) to compute the basis generating polynomial for regular matroids on n elements. This result implies that there exist ReLU neural networks of the same size for solving weighted basis maximization problems over these matroids. Furthermore, this leads to a virtual extended formulation for the matroid base polytope, which is smaller than previously known bounds.