Can common bases of two matroids be approximately counted in polynomial time?

An FPRAS replaces exact counting with a (1±ε) estimate

Two matroids M and N share a ground set U of size n and have the same rank r. Their bases are the maximal independent sets, and the quantity of interest is |B(M) ∩ B(N)|, the number of sets that are bases of both. The paper's Theorem 1.2 states that an FPRAS exists for this count: given independence oracles for M and N and an accuracy parameter 0 < ε ≤ 1, it returns an estimate Ẑ satisfying (1−ε)·Z ≤ Ẑ ≤ (1+ε)·Z with probability at least 3/4, in time polynomial in the instance size and 1/ε.

The guarantee is multiplicative, not additive, and it is randomized. The paper notes that randomization is necessary in the oracle model: even for a single matroid, no efficient deterministic algorithm can approximate |B(M)| within a simply exponential multiplicative factor. The same theorem also yields a polynomial-time algorithm for sampling a common basis almost uniformly, because the problems considered are self-reducible in the sense of Jerrum, Valiant, and Vazirani, making approximate counting and approximate sampling equivalent under polynomial-time reductions.

The running time is Õ(n^13/ε^2). The authors state explicitly that this is not optimal and that they made no attempt to optimize it, choosing instead to present the algorithms and proofs as simply as possible. That matters for reading the result: the contribution is polynomial-time feasibility, not a competitive constant or exponent.

Common bases are harder than bases of one matroid

Counting and sampling bases of a single matroid already has polynomial-time algorithms, due to Anari, Liu, Oveis Gharan, and Vinzant. The bipartite perfect matching case, which is the intersection of two partition matroids, was solved earlier by Jerrum, Sinclair, and Vigoda, who obtained the first FPRAS for the permanent of a nonnegative matrix. The new result covers the general intersection of two matroids rather than these special classes.

The paper's own account of why the general case resisted earlier techniques is concrete. For the distribution on common independent sets of all sizes weighted by λ^|S|, there are simple examples of matroid pairs whose spectral-independence parameter is Ω(poly(n)); the authors cite an even cycle of length Θ(n^1/3) with each edge replaced by Θ(n^2/3) parallel edges at λ = 1, where the matchings of that bipartite graph are exactly the common independent sets of two partition matroids. Constructing canonical paths or flows with polynomial congestion is also believed to be hard in general. So the obstacle is not a missing optimization but the failure of standard mixing proofs.

A soft intersection replaces the hard constraint with an overlap penalty

The first ingredient relaxes the intersection. Instead of requiring a pair (S, T) with T = U \ S, the algorithm works with a product measure formed from the two input measures and adds a penalty on overlap, controlled by a parameter t. The resulting "soft intersection" measure is the object whose mixing properties are analyzed.

The paper proves that this soft intersection satisfies a Poincaré inequality uniformly over all external fields, using an integrated Bochner-type method that bounds the spectral gap of a Laplacian via its square. The uniform-in-field statement is what makes the rest of the algorithm possible: the same mixing guarantee holds no matter which external field the optimization step later selects.

The relaxation is not free. The hard constraint T = U \ S is only recovered with high probability under the soft measure, so the algorithm must additionally show that this probability is large. That is the job of the second ingredient.

External fields are chosen by a dual maximum entropy program

The second ingredient solves a dual maximum entropy convex program to compute external fields under which the hard constraint holds with high probability under the soft intersection measure. The success probability is bounded directly from the uniform Poincaré inequality together with smallness of the gradient norm.

Concretely, the paper reduces the task to finding a field z with small ∇Φ(log z), where Φ is convex and coordinatewise 1-smooth, and applies stochastic coordinate descent. Corollary 5.12 states that, given value oracles for the two measures, their coefficient ranges R_μ and R_ν, and a supported pair (S_0, T_0), a randomized algorithm returns such a field or reports failure; if the target count Z_∩ is positive, it succeeds with probability at least 31/32 and returns a field satisfying π_{t,z}(T = U \ S) ≥ 1/2, using O(n^10 B^2 log(2B)) arithmetic operations and oracle calls, where B = 2n + ⌈log_2(R_μ R_ν)⌉.

This is where the approach differs from the annealing tradition. The permanent algorithms of Jerrum, Sinclair, and Vigoda and their successors learn correction weights along a carefully designed annealing path; here the fields are chosen directly by stochastic gradient descent. The authors present this as a black box that can serve a broad class of counting problems once the sampling and uniform Poincaré hypotheses are verified.

The count is assembled from two separately estimated factors

Once a good field is fixed, the target quantity is factored as Z_∩ = (Z_{t,z} / z^U) × π_{t,z}(T = U \ S). The first factor is a normalizer, estimated by the standard reduction from sampling to counting of Jerrum, Valiant, and Vazirani applied to the 2n membership bits of the pair (S, T); the second is the probability that a sampled pair is complementary, estimated by drawing pairs and taking an empirical fraction.

Both estimates carry relative error at most β = ε/4, and the conditions needed for them hold jointly with probability at least 1 − 4δ_0 > 3/4, giving (1−β)^2 ≤ Ẑ_∩/Z_∩ ≤ (1+β)^2 and hence relative error ε. If Z_∩ = 0, every supported pair fails the complementary-pair test, so every execution returns zero, either at the field-finding step or because the empirical complementary fraction is zero.

The running-time accounting is explicit. Finding the field costs O(n^10 B^2 log(2B)); the coefficient ranges do not increase during self-reduction; each restricted oracle uses one original query plus O(n) operations; and with t^{-1} = 256n^2 the cost of a conditional sample is O(n^5 (n^2 B + log(n/ε))). Self-reduction uses O(n^3 ε^{-2} log(2n)) samples, and estimating the complementary-pair probability takes O(ε^{-2}) more. Since B = Θ(n + log(R_μ R_ν)), the total is O(n^10 B^2 ε^{-2} log^2(2B/ε)).

The same machinery counts Hadamard products of curved measures

The matroid result is a special case of a more general statement about subset convolution. For nonnegative weight functions μ and ν on subsets of U, the subset convolution is (μ∗ν)(T) = Σ_{S⊆T} μ(S)·ν(T\S), which is the coefficient of x^T in the product of the two multi-affine generating polynomials. Theorem 1.6 gives an FPRAS for any specified coefficient Z_α = [x^α](g_μ(x)·g_ν(x)) with α ∈ {0,1,2}^U, assuming g_μ and g_ν are log-concave, using Õ(n^11·(n + log(R_μ·R_ν))^2 / ε^2) arithmetic operations and evaluation oracle calls.

Theorem 1.2 follows by setting μ(S) = 1[S ∈ B(M)] and ν(T) = 1[U \ T ∈ B(N)], both evaluable from independence oracles; log-concavity of the two generating polynomials was established in prior work, and initializing sets can be found greedily. The paper also develops a Hadamard-product formulation, where (μ ⊙ ν)(S) ∝ μ(S)·ν(S) on a common support, and proves a Poincaré inequality for the associated coordinate-wise Laplacian under a κ-spectral curvature condition on the input measures.

Three further applications of Theorem 1.6 are highlighted because they are not captured directly by the matroid statement: mixed discriminants of positive semidefinite matrices, which the paper says disproves a conjectured nonexistence of an FPRAS; the six-vertex model on loopless 4-regular multigraphs when the nonnegative weights satisfy a ≤ b+c, b ≤ a+c, and c ≤ a+b, which for positive weights completes a general-graph approximation classification left open previously; and Quantum Max-Cut on bipartite graphs together with the EPR model on arbitrary graphs with nonnegative edge weights. The matroid theorem also yields an FPRAS for counting strong orientations and undirected Euler tours, and a weighted variant applies to network reliability, including directed root-to-all reachability and unpaired vertex-disjoint linkages between two terminal sets.

Polynomial time is the claim, not practical speed

The result is stated for matroids given by independence oracles, with each oracle call charged unit cost. The running time depends on the coefficient ranges R_μ and R_ν, and the algorithms require R_μ, R_ν ≤ exp(poly(n)) to be polynomial; the paper notes this is easily satisfied in most applications of interest, and that user-supplied upper bounds may be used instead with the same replacement in the running-time bounds. The Õ(n^13/ε^2) bound for common bases is explicitly described as not optimal.

The paper is also transparent about how the ideas were developed. The acknowledgments state that GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used, that the authors provided many high-level directions while emphasizing that AI contributions were critical, and that the project began with the more modest problem of rapid mixing for Glauber dynamics on common independent sets of all sizes before extending to common bases. This is a disclosure about process, not a qualification of the mathematical claims, but it is part of the record the authors chose to include.

The decisive shift is from special cases to oracle-given matroid pairs

The most useful way to read this paper is as a change in what counts as the general case. Before it, polynomial-time counting and sampling were available for bases of a single matroid and for bipartite perfect matchings, which are the intersection of two partition matroids; the general intersection of two matroids given only by independence oracles had no polynomial-time approximation. The paper closes that gap with a randomized (1±ε)-multiplicative guarantee, and the same proof template extends to subset convolution of log-concave measures and to Hadamard products of measures satisfying a nonnegative curvature condition.

The practical threshold to keep in mind is the pair of hypotheses the black box needs: a sampling procedure and a uniform Poincaré inequality for the relevant measure. Where those can be verified, the field-finding step and the sampling-to-counting reduction apply as stated; where they cannot, the matroid theorem does not by itself supply an algorithm. The exponent of n^13 and the dependence on log(R_μ R_ν) are the price of this generality, and the authors present them as a starting point rather than a finished complexity.

Sources used in this answer