The Setting
Let and be matroids on the ground set , known only through independence oracles, and let be the number of their common bases. A fully polynomial randomized approximation scheme (FPRAS) for is a randomized algorithm that takes an accuracy and a failure probability and runs in time polynomial in , and . Bounding the running time and the oracle calls of such an algorithm needs a machine; the one here is a register machine whose registers are stacks of bits and whose random choices are read from a tape.
Oracles and Bit Strings
An independence oracle on elements is a map .✦ The oracle of and has exactly when the set with indicator vector is independent in , and exactly when it is independent in .
A bit string has length , and is the empty string. The binary value of a bit string is the natural number (1)✦ and for a natural number , is the string of binary digits of , lowest digit first, with .
The Definition
Definition 1. Fix natural numbers and ; the registers are and the states are . An instruction is one of (2)✦ where is a register, and are bits, and are states; is the set of instructions. A program is a map (3)✦ that assigns an instruction to each state. A configuration is a tuple (4)✦ of the register contents , bit strings read as stacks whose first bit is the top, a state , an output that is a rational number or undefined (), the number of oracle calls and the number of bit operations.
The machine takes as input natural numbers and , where is a second natural-number parameter of the input, and rationals and in lowest terms with ; the input length is (5)✦ and the initial configuration is (6)✦
For a program , an independence oracle on elements and a bit , the transition map sends a configuration to itself when , and when to (7)✦ Here is with the listed entries replaced, and is the top bit of . A query reads its register as the vector , and a halt with outputs .
The run of with oracle from a configuration on a tape of bits is the sequence of configurations (8)✦ A bit string of length is read as the infinite tape that agrees with on its first bits and is afterwards: (9)✦
For natural numbers and , the resource bound is the function of given by (10)✦ where is the least natural number at least and is the least natural number with .
In the paper, the model reads: a randomized oracle algorithm, whose oracle calls are counted apart from its other bit operations.
What Is Checked
The machine model is stated over the independence oracle on elements, which the query instruction consults, and over the binary value , through which the halt instruction reads registers and as its output.