OAI.common_bases_fpras

The theorem (admitted in the source, not proved here) states that the proposition CommonBasesFPRAS.MainTheorem holds, which asserts the existence of a fixed randomized register machine that is a fully polynomial randomized approximation scheme for counting common bases of two matroids given by independence oracles. Concretely, there exist numbers k and s, a program P with s+1 control states and k+8 bit-string registers (instructions: push a bit, pop a bit with three branches for empty, zero, one, flip a coin, query one of the two oracles on the subset encoded by a register, or halt), and constants C>0 and d such that the following holds for every n, every rank r, every pair of matroids M₁, M₂ on Fin n with ground set all of Fin n and both of rank r, every oracle O that answers exactly the independence questions of M₁ (selector false) and M₂ (selector true), and all rationals ε, δ strictly between 0 and 1. The machine starts with n, r, and the numerators and denominators of ε and δ written in binary in registers 0 to 5, and halts by outputting the ratio of the binary values in registers 6 and 7; a query on a register whose length is not n makes it output 0. Let Z be the number of sets that are a base of both matroids, and let B = C·(1+n+L+⌈1/ε⌉+⌈log₂⌈1/δ⌉⌉)^d, where L is the total bit length of the inputs. Then for every infinite sequence of random bits, after B steps the machine has produced an output, used at most B oracle calls and at most B bit operations, and any output z is nonnegative and equals 0 whenever Z=0. Moreover, among the 2^B choices of the first B random bits, at least a fraction 1−δ give an output z with (1−ε)Z ≤ z ≤ (1+ε)Z.