Metraipolis › archive › dc_223bf60e34ea

An FPRAS for Counting Common Bases of Two Matroids — arXiv:2610.06724

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.06724
License (as archived): CC0-1.0
Archived: 2026-10-06T13:49:34.302Z
SHA-256 of the archived text: 76b5e275ef847273b7a5af34de7f05bf1e10d9e961735afd5537d362b33612ad
Stable URL of this page: https://metraipolis.com/documento/dc_223bf60e34ea

How to cite

An FPRAS for Counting Common Bases of Two Matroids — arXiv:2610.06724 — arXiv (en), https://arxiv.org/abs/2610.06724 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_223bf60e34ea (Metraipolis archive dc_223bf60e34ea, sha256 76b5e275ef847273b7a5af34de7f05bf1e10d9e961735afd5537d362b33612ad)

BibTeX

@misc{dc223bf60e34ea,
  title = {An FPRAS for Counting Common Bases of Two Matroids — arXiv:2610.06724},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.06724},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_223bf60e34ea; sha256 76b5e275ef847273b7a5af34de7f05bf1e10d9e961735afd5537d362b33612ad},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.06724. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We design the first polynomial-time algorithms for approximately counting and almost 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 study of quantum many-body systems, and beyond. Our approach has two key ingredients. $\bullet$ 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 "$\textit{soft intersection}$" satisfies a Poincare inequality uniformly over all external fields. $\bullet$ 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 Poincare inequality and smallness of the gradient norm. $\textbf{AI Disclosure}$ GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used to develop the ideas in this paper. A more complete discussion is included in the acknowledgments.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2610.06724 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T12:06:32.237Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).