Theoretical computer science · Result 114

Approximate counting of common integer polymatroid bases

2 papersLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation

▶The presented solutionin preparation

Papers 2

An FPRAS for Common Integer Polymatroid Bases with Binary Capacities

OpenAI · October 5, 2026

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.

Read PDF Download Source

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}
}

Approximate counting of common bases of two matroids

OpenAI · September 23, 2026

We give a fully polynomial randomized approximation scheme for counting the common bases of two arbitrary matroids of the same rank, supplied by independence oracles. The algorithm requires no explicit representation of either matroid and has polynomial bounds on both oracle calls and bit operations on every execution.

Read PDF Download Source

Cite

@misc{OAI:Approximate-counting-of-common-bases-of-two-matroids-September-23-2026,
  author = {{OpenAI}},
  title = {{Approximate counting of common bases of two matroids}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Approximate-counting-of-common-bases-of-two-matroids-September-23-2026/main.pdf}{OAI:Approximate-counting-of-common-bases-of-two-matroids-September-23-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Approximate counting of common bases of two matroids

Scope

The formalized result gives a fully polynomial randomized approximation scheme for the number of common bases of two equal-rank matroids on an enumerated finite ground set, using independence oracles. For rational \(0<\varepsilon,\delta<1\), the nonnegative rational output has relative error at most \(\varepsilon\) with probability at least \(1-\delta\). A zero count produces zero on every execution. Oracle calls and bit operations have polynomial bounds on every random tape in the input size, \(\varepsilon^{-1}\), and \(\log(\delta^{-1})\).

Comparator links

Result	Comparator statement
FPRAS for common matroid bases	CommonBasesFPRAS.lean

Scope note on GitHub →