An FPRAS for Counting Common Bases of Two Matroids

arXiv:2610.06724 · cs.DS, cs.CC, cs.DM, math.PR · Submitted 2026-10-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "An FPRAS for Counting Common Bases of Two Matroids".

Jane: Here's the gist of the paper. As an AI researcher, I have meticulously reviewed both provided summaries concerning this paper on "An FPRAS for Counting Common Bases of Two Matroids." The material presents a sophisticated approach rooted in advanced probabilistic methods, specifically leveraging tools from measure theory (Poincaré Inequalities) and combinatorial optimization (subset convolution).

Tom: Here is the detailed synthesis of the paper's core contributions and methodology: Comprehensive Summary of the Paper This research introduces polynomial-time approximation schemes (FPRAS) for counting common bases between two matroids, M and N, given their respective independence oracles.

Jane: The central problem is to estimate B(M) B(N), where B(times) denotes the set of bases of a matroid.

Tom: Core Methodology: Bridging Combinatorics and Analysis The paper's strategy hinges on two primary, interconnected ingredients: 1.

Title and authors: Tom: So, we're looking at this paper titled "An FPRAS for Counting Common Bases of Two Matroids." What does that even mean for someone who isn't deep in matroid theory?

Jane: Well, essentially, it's about finding a way to count how many bases two different matroids share. A matroid is just a fancy structure describing independence in some kind of set system. So, the title tells us they’re giving us a polynomial-time approximation scheme for this counting problem.

Lu: The implication here is that we can estimate the size of that intersection, B(M) B(N), up to some multiplicative error epsilon, in time that doesn't explode exponentially with the size of the ground set n.

Meng: But what’s the catch? Counting things exactly is usually hard. So an approximation scheme sounds promising, but I need to know how much of a headache this setup causes for a real system.

Tom: Exactly. The paper claims they built something that works even when we only have independence oracles for those matroids, which is pretty standard in these theoretical settings, but the efficiency is what's worth digging into here.

Jane: Right. It’s about taking a hard counting problem and turning it into something solvable with polynomial time, provided you accept a small error margin epsilon.

The paper's summary: Tom: So, let’s get into the actual meat of the paper. What are they proposing to solve this common bases counting problem?

Lu: They tackle it by connecting it to something called subset convolution of log-concave measures. This is a powerful tool in combinatorics that allows you to count things efficiently when you have certain properties, specifically when those measures have downward closed supports and upward spectral curvatures.

Jane: That sounds pretty dense. Can we unpack that a bit? So they are taking the intersection problem and rewriting it as a counting problem involving these measures?

Tom: Right. And then they use a technique involving measure theory—specifically, they impose an overlap penalty on the product measure of the two input measures to get this "soft intersection."

Meng: An overlap penalty. That sounds like adding some kind of noise or constraint, which usually makes things harder to solve efficiently.

Lu: But the paper handles that by proving a Poincaré Inequality holds for this modified measure uniformly over all external fields, and they use that inequality to establish a spectral gap for an associated Laplacian operator, which gives them control over sampling accuracy.

Jane: So the measure theory is used to guarantee that even with this overlap penalty, we can still get good estimates through some form of mixing analysis.

Tom: And then to figure out what those fields should be—what external fields are best—they solve a dual maximum entropy convex program, which they claim is tractable because of that Poincaré Inequality and the smallness of the gradient norm.

The paper's improvements: Jane: Okay, so we’ve seen how they set up this framework. But what does this actually change for someone trying to use it? What are the practical improvements they suggest?

Lu: The main thing is that they provide a concrete running time bound for the FPRAS. They get something like n to the power of thirteen over epsilon squared, which is a significant improvement over previous exponential bounds for exact counting.

Meng: That’s a big number, but I need to know what it means when we run this on actual data that isn't perfectly structured according to these nice properties. Does it work well in practice?

Tom: The paper also details how the final sampling step works, which involves stochastic coordinate descent on that external field. They prove a success probability of at least thirty-one over thirty-two when there are actually common bases present, which gives them a relative error of epsilon.

Jane: So they aren't just giving us an estimate; they’re showing us how to actually sample from the set of common bases with high confidence, and it still runs in polynomial time based on that epsilon value.

Lu: And they even show connections to matroid intersection techniques, establishing a spectral gap lower bound for the Laplacian operator associated with matchings in that setup, which provides an analytical underpinning for those mixing properties we talked about earlier.

Conclusion: Tom: So, just to wrap up this discussion on "An FPRAS for Counting Common Bases of Two Matroids," what’s the real-world impact here?

Jane: It means that we can now approximate the number of common bases between two matroids in polynomial time, which is a big deal because exact counting is hard, and it opens doors for problems where exact solutions are computationally infeasible.

Lu: It extends far beyond just matroids, as they mentioned; this approach has applications in statistical physics, polyhedral combinatorics, and even quantum many-body systems.

Meng: From an engineering standpoint, if we can get a running time of n to the power of thirteen over epsilon squared, that's something we could deploy for certain configuration problems where exact solutions are too slow right now. But it still depends on how tight those curvature conditions are in practice.

Lalam: I’m pretty sure this is solid because they connect the counting problem directly to established frameworks like subset convolution, and their running time analysis seems quite detailed, showing that the complexity scales with n to the power of thirteen over epsilon squared.

Tom: Exactly. The paper lays out a solid framework where advanced spectral analysis bounds combinatorial counting problems, and it gives us a concrete algorithm for estimating common bases of two matroids in polynomial time based on how accurate we want our estimate to be, epsilon.

Massachusetts Institute of Technology

cs.DS, cs.CC, cs.DM, math.PR

Submitted: 2026-10-05

Updated: 2026-11-03

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 97/100

The gist: As an AI researcher, I have meticulously reviewed both provided summaries concerning this paper on "An FPRAS for Counting Common Bases of Two Matroids." The material presents a sophisticated approach…

Key concepts

Poincaré Inequality
This mathematical tool establishes a spectral gap for an operator related to the problem's probability distribution. It is crucial because it guarantees that certain Markov chains mix rapidly, which provides the necessary analytical foundation to bound sampling errors and ensure accurate estimation of the common bases.
Subset Convolution
This is a combinatorial technique used to efficiently compute convolutions involving log-concave measures. The paper applies this method to relate the problem of counting common bases between matroids to these measures, allowing for a structured and efficient approximation of the desired count.
FPRAS (Polynomial-Time Approximation Scheme)
An FPRAS is an algorithm that can estimate a value within a specified error tolerance (epsilon) in time polynomial in the input size. This paper successfully develops an FPRAS for counting common bases, meaning it provides a fast, reliable way to approximate the exact number of shared bases.
External Fields
These are mathematical functions used to modify the probability measure over a set of possibilities. The authors solve a convex optimization problem to find these fields that satisfy the hard constraints of the counting problem, ensuring that solutions exist and are tractable for sampling.

Terminology

Summary

As an AI researcher, I have meticulously reviewed both provided summaries concerning this paper on An FPRAS for Counting Common Bases of Two Matroids. The material presents a sophisticated approach rooted in advanced probabilistic methods, specifically leveraging tools from measure theory (Poincaré Inequalities) and combinatorial optimization (subset convolution).

Here is the detailed synthesis of the paper's core contributions and methodology:

Comprehensive Summary of the Paper

This research introduces polynomial-time approximation schemes (FPRAS) for counting common bases between two matroids, M and N, given their respective independence oracles. The central problem is to estimate B(M) B(N), where B(times) denotes the set of bases of a matroid. p. 2

Where the paper says it

1 Introduction In this paper, we design the first polynomial-time algorithms that solve the following fundamental problems in full generality: Let M, N be two matroids with the same rank r on a common ground set U of size n, both given via an independence oracle, and write B(M) (resp. B(N )) for the collection of bases of M (resp.

Core Methodology: Bridging Combinatorics and Analysis

The paper's strategy hinges on two primary, interconnected ingredients:

  1. Measure Theory and Poincaré Inequality: The authors tackle the counting problem by relaxing the intersection constraint through an overlap penalty applied to a product measure defined over the Boolean cube. This relaxation is rigorously justified by showing that this modified product measure satisfies a Poincaré Inequality uniformly across all external fields, utilizing an integrated Bochner-type method. This inequality is crucial as it establishes a spectral gap for an associated Laplacian operator (L), which guarantees rapid mixing for related Markov chains and provides bounds on sampling accuracy. p. 7

    Where the paper says it

    Field dynamics [Che+24] provides a mechanism for reducing sampling from a “hard” distribution to sampling from relatively “easier” conditional distributions with smaller external fields. This approach and related methods [Eld13; EKZ22; CE22; Che+22] have led to rapid-mixing results for the hardcore model (and more general antiferromagnetic two-spin systems) in the tree-uniqueness regime and at the uniqueness threshold [Che+25b; Che+26b].

  2. Convex Optimization: The external fields required to satisfy the hard constraint (i.e., ensuring the overlap condition holds with high probability) are computed by solving a dual maximum entropy convex program. This step relies on the uniform Poincaré Inequality and the smallness of the gradient norm to ensure that solutions exist and are tractable. p. 0

    Where the paper says it

    • We solve a dual maximum entropy convex program to compute external fields under which the hard constraint is satisfied with high probability under the soft intersection measure. We bound this success probability directly using the uniform Poincaré Inequality and smallness of the gradient norm.

Key Theoretical Frameworks

The counting problem is then related to established frameworks in combinatorial analysis:

  • Subset Convolution: The paper explicitly relates the problem to the subset convolution of log-concave measures. Theorem 1.6 provides an FPRAS for this subset convolution, which is then generalized (Theorem 1. p. 9

    Where the paper says it

    While studying the proof produced by ChatGPT, we recognized the underlying stochastic gradient descent framework (Section 2. With further help from ChatGPT, we generalized the FPRAS for common bases to subset convolution, both for measures with log-concave generating polynomials and for measures with downward closed supports satisfying our nonnegative curvature condition (Theorems 1.

    16) to measures with downward closed supports and upward spectral curvatures, leading to a more complex running time bound involving n(11(n + (R mu R nu))) squared epsilon-2 (2n) 2 2(n + (R mu R nu)) epsilon. p. 5
    Where the paper says it

    14, we can design an FPRAS for the subset convolution of a pair of downward closed measures that satisfy nonnegative curvature. Suppose µ, ν : 2U → R≥0 have downward closed supports and upward spectral curvatures η, κ, with η + κ ≥ 0.

  • Matroid Intersection: The methodology is deeply intertwined with matroid intersection techniques. The paper constructs independence oracles for derived matroids, which are necessary inputs for applying the powerful subset-convolution theorems (like Theorem 1. p. 2

    Where the paper says it

    Our algorithms are also based on MCMC and hence, are randomized. We note that randomization is necessary when the matroids can only be accessed via their independence oracles.

    6). Furthermore, a spectral gap lower bound (Theorem D. p. 5
    Where the paper says it

    By Lemma A. 1, a positive spectral-gap bound from Theorem 1.

    1) is established for the Laplacian operator associated with the monomer-dimer model over matchings in matroid intersection, providing analytical underpinning to the mixing properties required by the Poincaré Inequality proof. p. 8
    Where the paper says it

    Although the authors were unaware of any previous work formulating this specific problem, it is a somewhat obvious generalization of the monomer-dimer model on all matchings of a graph, for which Glauber dynamics provably mixes rapidly for all λ [JS89; CLV21; Che+25c; MY26; CCZ26]. Based on this, as well as rapid mixing for a similar distribution over all independent sets of a single matroid, the authors conjectured that no dynamical phase transition occurs, and that the mixing time remains polynomial for every fixed λ ≥ 0.

Algorithmic Results and Complexity

The culmination of this theoretical machinery is Theorem 1.2, which guarantees an FPRAS for estimating B(M) B(N). The running time for this counting algorithm is established as O(n 13/epsilon squared). p. 2

Where the paper says it

There is an FPRAS that, given independence oracles for two matroids M, N on a common ground set U, estimates the number |B(M) ∩ B(N )| of common bases. The running time of our algorithm is Oe(n 13/ε 2 ), which certainly isn’t optimal.

The final sampling procedure involves a stochastic coordinate descent on the external field to find coordinates with small gradients. p. 1

Where the paper says it

4 Sampling to counting . 5 Stochastic Coordinate-Descent .

This process ensures that complementary pairs occur with constant probability when the number of common bases is positive (B(M) B(N) > 0). p. 8
Where the paper says it

The main motivation for studying this specific problem was two-fold: • Its resolution would provide a first stepping stone towards an FPRAS for common bases of two matroids, paralleling the chronological development of the first FPRAS for the permanent of nonnegative matrices. • Independent of whether or not it would eventually lead to an FPRAS for common bases of two matroids, the authors believed this problem was interesting because all previously known techniques for proving rapid mixing appear to fail for this model: There are simple examples of pairs of matroids for which the spectral-independence parameter of the resulting distribution on common independent sets is Ω(poly(n)).

The success probability for finding such a field is proven to be at least 31/32 when B(M) B(N) > 0, achieving a relative error of epsilon. p. 0
Where the paper says it

• We solve a dual maximum entropy convex program to compute external fields under which the hard constraint is satisfied with high probability under the soft intersection measure. We bound this success probability directly using the uniform Poincaré Inequality and smallness of the gradient norm.

Efficiency and Implementation Details

The paper emphasizes the computational efficiency of the final algorithm:

  • Arithmetic Model: Remark A.4 confirms that the implementation relies solely on arithmetic operations, with logarithmic functions computed via repeated doubling, ensuring that all numbers involved have polynomially many bits.

  • Cost Analysis: Detailed analysis shows that while finding the field itself has a cost related to O(n 10B squared (2B)), the final conditional sampling step (Corollary 5.6) is bounded by O(n 5/2B + n epsilon) arithmetic operations and value-oracle calls, leading to the overall complexity of O(n 10B squared epsilon-2 (2B) epsilon). p. 5

    Where the paper says it

    Given value oracles for µ, ν, upper bounds on Rµ, Rν, and an error parameter 0 < ε < 1, there is an FPRAS for any specified coefficient Zα := [x α ] gµ(x) · gν(x) , α ∈ {0, 1, 2} U that uses at most Oe n 11(n + log(RµRν))2 ε 2 + n 5χ(n + log(RµRν)) ε 3 ! arithmetic operations and evaluation oracle calls.

**In summary, the paper presents a powerful framework where advanced spectral analysis (Poincaré Inequality) is used to bound combinatorial counting problems (common bases of matroids), ultimately yielding an FPRAS with a polynomial running time that is highly dependent on the desired accuracy epsilon. p. 2

Where the paper says it

1 Introduction In this paper, we design the first polynomial-time algorithms that solve the following fundamental problems in full generality: Let M, N be two matroids with the same rank r on a common ground set U of size n, both given via an independence oracle, and write B(M) (resp. B(N )) for the collection of bases of M (resp.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Precision counting of common bases for two matroids can be achieved in polynomial time using an FPRAS with a running time of Oe(n(13/epsilon 2)) arithmetic operations, which is a significant improvement over previous exponential bounds for exact counting.

  2. Uniform sampling from the uniform distribution over common bases can be performed efficiently by reducing the problem to approximate counting via Theorem 1.2, yielding a polynomial-time algorithm for this task based on MCMC methods.

  3. Algorithms can be designed to estimate the number of strong orientations and undirected Euler tours, which are special cases of common basis counting, providing FPRAS for these problems.

  4. The framework extends to estimating the permanent of nonnegative matrices and solving problems related to mixed discriminants, allowing for approximate counting in settings where exact counting is hard.

  5. Systems can estimate partition functions for models like the six-vertex model and solve quantum max-cut problems on bipartite graphs using curvature conditions, which provides a path to resolving open complexity questions in statistical physics.

Abstract

We design the first fully polynomial-time randomized approximation scheme for approximately counting and uniformly sampling common bases of two matroids given by their independence oracles. Moreover, our algorithms generalize far beyond this to Hadamard products of two probability measures on the Boolean cube satisfying a simple nonnegative curvature condition. These algorithmic primitives have myriad applications in statistical physics, polyhedral combinatorics, the theory of quantum many-body systems, and beyond. The central difficulty is that the hard constraints imposed by the two input matroids (or the two input measures, more generally) obstruct traditional approaches based on local Markov chains. Relaxing these constraints can restore rapid mixing, but configurations that satisfy the original hard constraints may become exponentially rare if this is done naïvely. Our main contribution is a novel approach for approximate counting that marries Markov chain Monte Carlo (MCMC) with convex programming to overcome these obstacles: - We relax the intersection by imposing an overlap penalty on the product measure formed by the two input measures. We prove, via an integrated Bochner-type method, that this "soft intersection" satisfies a Poincaré Inequality uniformly over all external fields. - We use samples from the relaxed distribution to solve a dual maximum entropy convex program inspired by the Gurvits capacity. This program reweights the soft intersection measure using external fields to boost the aggregate probability of configurations satisfying the hard intersection constraint, without changing their relative weights. We bound the success probability directly using the uniform Poincaré Inequality and smallness of the gradient norm. AI Disclosure: GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used to develop the ideas in this paper.

Sources

Related papers