An FPRAS for Counting Common Bases of Two Matroids
Abstract
We design the first fully polynomial-time randomized approximation scheme (FPRAS) 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.
Related
- A simplified proof of the FPRAS for counting perfect matchings
- A rank bound for bases and circuits in binary matroids
- Mutually unbiased bases: common states, completion, and extension obstructions
- Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure
- An FPRAS for Mixed Volumes
BibTeX
@misc{chen2026fpras,
title = {{An FPRAS for Counting Common Bases of Two Matroids}},
author = {Xiaoyu Chen and Kuikui Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06724},
eprint = {2610.06724},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06724},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An FPRAS for Counting Common Bases of Two Matroids
AU - Xiaoyu Chen
AU - Kuikui Liu
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06724
UR - https://arxiv.org/abs/2610.06724
AB - We design the first fully polynomial-time randomized approximation scheme (FPRAS) 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.
ER -