← 研踪 PaperTrailarXiv:2610.06724 · v2
An FPRAS for Counting Common Bases of Two Matroids
首次提交 2026-10-06 01:15
版本更新 2026-11-03 13:47
雷达观测 2026-11-04 23:40
摘要
We design the first fully polynomial-time randomized approximation scheme ($\mathsf{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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 13:47 · 最新观测版本
An FPRAS for Counting Common Bases of Two Matroids
We design the first fully polynomial-time randomized approximation scheme ($\mathsf{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.
查看此版本解读 →查看此版本原文 ↗