Approximate counting of common bases of two matroids
There is a single randomized oracle algorithm that, given independence oracles for arbitrary rank- matroids on and rational , outputs a nonnegative rational such that , always outputs if , and on every execution has oracle calls and other bit operations bounded by a fixed polynomial in (where is the binary encoding length of ), using only independent unbiased random bits and no representation of either matroid.
The proof is complete and rigorous. All edge cases (, , , ), adaptive multiplier conditioning via fresh restarts, and worst-case bit-operation bounds are handled.
“Theorem 1.1. There is a single randomized oracle algorithm with the following guarantee. Given independence oracles for arbitrary rank-r matroids M1, M2 on [n], and rational ϵ, δ ∈ (0, 1), it outputs a nonnegative rational Zb such that P[(1 − ϵ)Z(M1, M2) ≤ Zb ≤ (1 + ϵ)Z(M1, M2)] ≥ 1 − δ. If Z(M1, M2) = 0, its output is always zero. On every execution, the number of oracle calls and the number of other bit operations are bounded by a fixed polynomial in n, ℓ, ϵ−1, log δ−1, where ℓ is the binary encoding length of n, r, ϵ, δ. The algorithm uses only independent unbiased random bits and does not require a representation of either matroid.” · Show in paper