Browse › Theoretical computer science › 114 Approximate counting of common integer polymatroid bases
An FPRAS for Common Integer Polymatroid Bases with Binary Capacities
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give a fully polynomial randomized approximation scheme for counting common integer bases of two polymatroids with the same total rank, supplied by exact rank-value oracles. The total rank and capacities are encoded in binary, and each integer vector is counted once. On every execution, the number of oracle calls and the bit work outside the oracles are bounded by a fixed polynomial in the ground-set size, the binary input length, the inverse relative-error tolerance, and the logarithm of the inverse failure probability. The algorithm handles binary capacities directly, without expanding them into labelled copies.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Lean scope notes for family 114 (lean/docs/114.md). The formalized scope covers only the companion two-matroid FPRAS, and the polymatroid theorem of this paper is not among the comparator statements. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Xiaoyu Chen and Kuikui Liu, An FPRAS for Counting Common Bases of Two Matroids (arXiv:2610.06724, 2026-10-05). An independent proof of the two-matroid FPRAS that this paper builds on (its reference [Parent]), whose appendix treats integer polymatroid intersections with unary capacities (Proposition C.20), for comparison with this paper's binary-capacity claim. It does not cite the OpenAI release and discloses substantial AI assistance.
Digests and expositions
- Latent Seminar, Counting common matroid and integer polymatroid bases (October 7, 2026). An exposition of both family manuscripts' defect states, trace-chain estimates, multiplicity corrections and binary-capacity reduction, limited by its own account to statements and selected proof mechanisms. [family-level]
Elsewhere
- Emergent Mind: family 114
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:An-FPRAS-for-Common-Integer-Polymatroid-Bases-with-Binary-Capacities-October-5-2026,
author = {{OpenAI}},
title = {{An FPRAS for Common Integer Polymatroid Bases with Binary Capacities}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/An-FPRAS-for-Common-Integer-Polymatroid-Bases-with-Binary-Capacities-October-5-2026/polymatroid-fpras.pdf}{OAI:An-FPRAS-for-Common-Integer-Polymatroid-Bases-with-Binary-Capacities-October-5-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/114.md. The Lean statements have not been checked by people against the paper's claims.
Family 114: Approximate counting of common integer polymatroid bases
Gives a fully polynomial randomized approximation scheme for counting common integer bases of two integral polymatroids of equal total rank, supplied by exact rank-value oracles. Capacities are binary-encoded, each integer vector counts once, and oracle calls and bit operations outside the oracles are polynomial on every execution. For matroids presented by independence oracles, the results also cover common independent sets of prescribed, unrestricted, or maximum cardinality, even when the ranks differ.
Other papers in this family:
- Approximate counting of common bases of two matroids · September 23, 2026