Arithmetic Circuits and Neural Networks for Regular Matroids

Christoph Hertrich, Stefan Kober, Georg Loho

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…