Open Research Index

An FPRAS for Counting Common Bases of Two Matroids

Xiaoyu Chen, Kuikui Liu

arXivarxiv/2610.06724Oct 5, 2026cs.DSscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.06724
curl -X POST /api/v1/records/arxiv/2610.06724/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.06724/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'