Arithmetic Circuits and Neural Networks for Regular Matroids

arXiv:2511.02406 · math.CO, cs.CC, cs.DM, cs.LG, math.OC · Submitted 2025-11-04 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Arithmetic Circuits and Neural Networks for Regular Matroids".

Jane: The gist: We prove that there exist uniform (+, ×, /)-circuits of size O(n 3) to compute the basis generating polynomial of regular matroids on n elements,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: This paper, "Arithmetic Circuits and Neural Networks for Regular Matroids", really bridges the gap between pure combinatorial structure and modern machine learning models like neural networks.

Jane: It’s about showing that you can take the complex polynomial describing a matroid structure and translate it into a simpler form that works within a neural network framework.

Lu: The core idea they present is that since these circuits are (+, times, /) based, which are related to tropical functions, we can represent them using ReLU neural networks with the same size complexity.

Meng: So what does this mean for us in terms of deployment? It suggests that problems involving weighted basis maximization over regular matroids can be handled by a neural network of size O(n three) <ref:2511.02406#pg1,of size $O(n^3>.

Lalam: That's the implication. It allows us to use these neural networks to approximate continuous and piecewise linear functions derived from regular matroids, which is useful for optimization tasks.

Tom: But the real kicker is what they show in linear programming theory, connecting this to extension complexity. They get a result that we call a virtual extended formulation of size O(n three) for the matroid base polytope <ref:2511.02406#pg1,extended formulation of size $O(n>.

Jane: That's significant because the best known individual extended formulation for that same polytope is size O(n six), so O(n three) is a substantial improvement, even if it's a virtual one <ref:2511.02406#pg1,the best known individual extended formulation>.

Lu: The construction of this virtual extended formulation relies on combining Corollary two with the relationship between neural networks and extension complexity established in another work twenty-three <ref:2511.02406#pg2>. This gives us that size reduction for the polytope representation.

The paper's summary: Tom: Let's talk about what they actually summarize in "Arithmetic Circuits and Neural Networks for Regular Matroids". It really boils down to proving the existence of these efficient circuits and then using tropicalization to get those neural networks.

Jane: So, they start by defining the basis generating polynomial f M for a regular matroid M with rank r, which is that sum over all bases where each term is a product of variables corresponding to the elements in that basis.

Lu: They then leverage Maurer’s generalization of Kirchhoff’s matrix-tree theorem to view this polynomial as the determinant of an r-dimensional square matrix L. This allows them to use structural properties instead of computing a general determinant directly.

Meng: So they are exploiting the specific structure of that matrix L instead of resorting to a general, expensive determinant calculation for every matroid instance.

Lalam: And then they use an inductive approach, similar to what Fomin et al. used for spanning trees in graphs, where you reduce the size of L by eliminating one vertex at a time while compensating for the lost information.

Tom: That’s a very concrete way to think about how they manage that matrix size reduction step-by-step, which is what makes the circuit construction possible.

The paper's improvements: Jane: So what are the actual improvements this paper suggests over previous work? Beyond just proving the O(n three) circuit exists, they show a few things that change how we look at these problems <ref:2511.02406#pg1>.

Lu: First, they establish Corollary three which states there is a virtual extended formulation of size O(n three) for the matroid base polytope of a regular matroid on n elements <ref:2511.02406#pg1,extended formulation of size $O(n>.

Tom: That’s the comparison point. This is better than the best known extension complexity upper bound from Aprile and Fiorini, which was O(n six) <ref:2511.02406#pg1>.

Jane: So they are showing that taking a single difference of two extended formulations, which is what a virtual extended formulation is, can be more efficient than solving just one ordinary LP formulation.

Meng: That’s a big deal for practical implementation because it means the underlying optimization problem for the matroid polytope might have a much smaller representation size in practice.

Lalam: And they also extend this work to Max-Flow-Min-Cut matroids by defining F7 as a binary matroid and showing that MFMC matroids can be decomposed into regular matroids and copies of F7.

Conclusion: Tom: So to wrap up the "Arithmetic Circuits and Neural Networks for Regular Matroids" paper, we’ve seen they achieved an O(n three) arithmetic circuit for the basis generating polynomial and a corresponding size O(n three) ReLU neural network <ref:2511.02406#pg1,Arithmetic Circuits and Neural Networks for Regular Matroids>.

Jane: And they used that connection to show a virtual extended formulation of size O(n three) for the matroid base polytope, which is better than the previous O(n six) bound <ref:2511.02406#pg1,extended formulation of size $O(n>.

Lu: The paper also generalized the circuit construction technique to Max-Flow-Min-Cut matroids by decomposing them using F7, leading to a polynomial time circuit construction for their basis generating polynomial.

Meng: From an engineering standpoint, this means we might have a much more tractable way to model these types of optimization problems at scale compared to the O(n six) methods we were dealing with before <ref:2511.02406#pg1>.

Lalam: And they established that given an independence oracle, you can construct these circuits and networks in polynomial time. It makes the whole system practical for using in real-world applications where you might not have the full combinatorial structure explicit upfront.

Tom: So, to summarize this paper, we have a uniform O(n three) circuit for regular matroids and an O(n three) neural network representation for weighted basis maximization, and better bounds on polytope formulations in linear programming <ref:2511.02406#pg1>.

Jane: It’s a solid piece of work that connects algebraic structures with modern AI tools like neural networks in a way that offers tangible improvements in complexity bounds.

University of Technology Nuremberg · Université Libre de Bruxelles · Freie Universität Berlin · University of Twente

math.CO, cs.CC, cs.DM, cs.LG, math.OC

Submitted: 2025-11-04

Updated: 2026-10-15

Comments: Extended abstract appeared in IPCO 2026

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 82/100

The gist: The gist: We prove that there exist uniform (+, ×, /)-circuits of size O(n 3) to compute the basis generating polynomial of regular matroids on n elements, which implies the existence of ReLU neural

Key concepts

Basis Generating Polynomial ($f_M$): This polynomial describes the structure of all bases in a regular matroid M. It is calculated by taking the product of terms involving bases and elements, representing a complex combinatorial property that needs to be computed efficiently.
Tropicalization: This is a mathematical technique used to transform problems involving standard arithmetic operations (like addition and multiplication) into problems using tropical operations (like max, +, -). This transformation allows the problem to be solved using structures like neural networks.
Virtual Extended Formulation: This is a method in linear programming theory where a large optimization problem over one polytope can be solved by combining two smaller ones. Instead of solving one complex formulation, you solve two simpler ones and take their difference, potentially leading to a much more efficient solution.

Terminology

Generalization — 12× in this paper · explained in 13 episodes
ReLU Network — 11× in this paper · explained in 2 episodes
Activation Function — 2× in this paper · explained in 1 episode
Combinatorial Optimization — 2× in this paper · explained in 2 episodes
Axioms — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes

Summary

The gist: We prove that there exist uniform (+, ×, /)-circuits of size O(n 3) to compute the basis generating polynomial of regular matroids on n elements, which implies the existence of ReLU neural networks of the same size for weighted basis maximization.

Contribution

The main result is the construction of efficient (+, ×, /)-circuits for the basis generating polynomial of regular matroids For a regular matroid M with n elements, the basis generating polynomial is fM:= P B∈B x B:= P B∈B Q e∈B xe. Given an independence oracle of M, this circuit can be constructed in polynomial time.

Implications on neural networks

Using the idea of tropicalization described above, we obtain the following Corollary 2. For a regular matroid M with basis set B and n elements, there is (i) a (max, +, −)-circuit and (ii) a ReLU neural network of size O(n 3) computing the tropical polynomial maxB∈B P e∈B xe. Given an independence oracle of M, the circuit and the neural network can be constructed in polynomial time. Evaluating this tropical polynomial can be seen as solving the maximum weight basis problem over the regular matroid, which can famously be achieved by the greedy algorithm. However, as described by Hertrich and Sering [24], finding efficient neural network representations to solve combinatorial optimization problems like this remains non-trivial, as the computational model of neural networks is missing simple algorithmic building blocks like if-branchings based on the comparison of real numbers or computing argmins over finite sets.

Implications in linear programming theory

Combining Corollary 2 with the connection between neural networks and extension complexity established in [23], we immediately obtain the following Corollary 3. There exists a virtual extended formulation of size O(n 3) of the matroid base polytope of a regular matroid on n elements. This is in contrast to the best known extension complexity upper bound O(n 6) from [3]. A virtual extended formulation of a polytope P consists of extended formulations for two polytopes Q and R such that P + Q = R, where P + Q is a Minkowski sum. This allows to solve the linear optimization problem over P by solving it over Q and R and taking the difference of the two results [23]. It is an open question whether taking a single difference of two LPs brings an advantage over solving just one LP, that is, whether virtual extended formulations can be more efficient than ordinary ones. To the best of our knowledge, our result provides the first example of virtual extended formulations that are smaller than the best known extended formulations.

Proof techniques

A key ingredient to prove our main result is Maurer’s generalization [37] of Kirchhoff’s celebrated matrix-tree theorem [34] in order to view the basis generating polynomial of a regular matroid M as the determinant of an r-dimensional square matrix L, where r is the rank of M. Since a general determinant cannot be computed with a (+, ×, /)-circuit, we need to exploit the specific structure of the matrix L. We can understand the approaches by Fomin et al. [18] and Hertrich and Sering [24] for the case of spanning trees in graphs as an inductive approach to reduce the number of rows of L by one in each step. In terms of graphs, this strategy corresponds to eliminating one vertex at a time, and compensating for the lost information by introducing additional edges between neighbors of the removed vertex.

Generalization to MFMC matroids

While our original motivation for the problem was for regular matroids, in fact it is easy to check that our algorithm to construct arithmetic circuits for the basis generating polynomial works more broadly in matroids that can be decomposed via 1- and 2-sums into base blocks that admit the efficient construction of such an arithmetic circuit. One central such class of matroids is the Max-Flow-Min-Cut (MFMC) matroids, which were introduced by Seymour [41], and admit a similar decomposition theorem to regular matroids. To be more precise, we define the matroid F7 as the binary matroid with representation matrix A:= (I3 A7), with A7:= [1 0 1 1; 1 1 0 1; 0 1 1 1]. Then, the class of MFMC matroids is defined to be the class of matroids that can be decomposed into regular matroids and copies of F7 by repeated 1-, and 2-sum decompositions. As such, MFMC matroids form a proper minor-close subclass of binary matroids, that contains all regular matroids. Since F7 has bounded size, and our construction for the 1- and 2-sum works for general matroids, see Proposition 10 and Proposition 11, we obtain the following corollary Corollary 25. For a MFMC matroid M with n elements, there is a (+, ×, /)-circuit of size O(n 3) computing the basis generating polynomial fM. Given an independence oracle of M, this circuit can be constructed in polynomial time.

Theorem 1

For a regular matroid M with n elements, there is a (+, ×, /)-circuit of size O(n 3) computing the basis generating polynomial fM. Given an independence oracle of M, this circuit can be constructed in polynomial time.

Proof (Proof sketch of Theorem 1)

We prove by induction on the number n of elements of the matroid M that fM can be represented by a (+, ×, /)-circuit of size g(n):= n cubed. If M is graphic, the statement was proven by Fomin et al. [18]. For the cographic case, we additionally apply Lemma 13. Finally, R10 has exactly 162 bases and rank 5, so implementing fR10 naively via its definition results in a circuit of size 809. If M is graphic, the statement was proven by Fomin et al. [18]. For the cographic case, we additionally apply Lemma 13. Finally, R10 has exactly 162 bases and rank 5, so implementing fR10 naively via its definition results in a circuit of size 809.

Proposition 8 (B´erczi et al. [11, Proposition 5.7])

Let M be a 3-connected regular matroid, such that M is not graphic, cographic or isomorphic to R10. Then there are 3-connected regular matroids M1 and M2, such that E(M2) ≥ 9, M2 is graphic and M1 ⊕∆ M2 ∈ [M, M∗].

Improvements for AI systems

No-P Complexity Circuit Construction: Implement an arithmetic circuit of size O(n3) to compute the basis generating polynomial of a regular matroid on n elements, which is essential for efficiently solving combinatorial optimization problems related to matroids.
Tropical Neural Network Representation: Utilize the tropicalization technique to construct ReLU neural networks of size O(n3) for weighted basis maximization, allowing these networks to approximate continuous and piecewise linear (CPWL) functions derived from regular matroids.
Virtual Extended Formulation Discovery: Employ a virtual extended formulation of size O(n3) for the matroid base polytope, providing a potentially more efficient alternative to best-known individual formulations of size O(n6) in linear programming theory applications.
MFMC Matroid Circuit Solving: Extend the circuit construction algorithm to Max-Flow-Min-Cut (MFMC) matroids by defining F7 as a binary matroid and decomposing MFMC matroids into regular matroids and copies of F7, enabling a polynomial-time circuit construction for their basis generating polynomial.
Polynomial Time Oracle Construction: Given an independence oracle of a matroid, the algorithm can be constructed in polynomial time, which is crucial for practical application in machine learning and optimization where real-world problems are often modeled via oracles rather than explicit combinatorial data.