The Setting
Let and be matroids of the same rank on the ground set , and let be the number of their common bases, the sets that are a base of both.✦ For a bipartite graph with edge set and vertices on each side, none of them isolated, the partition matroids of the two sides have the perfect matchings as their common bases, and counts them. The matroids are known only through independence oracles. A fully polynomial randomized approximation scheme (FPRAS) for takes , and rationals and returns an estimate within a factor of with probability at least , at a cost polynomial in , the length of the input, and .
The library states that one program of an explicit oracle machine, called the frozen machine below, is such a scheme, with its oracle calls and bit operations counted step by step and its success probability taken as a fraction of tapes of fair bits. The estimator it builds is an annealing product of ratios, each estimated with a Metropolis chain on a ground set of pairs of elements, defined below, amplified by the median trick.
Oracles, Machines and Tapes
An independence oracle on is a map that takes a bit and the indicator vector of a set and returns a bit.✦ An independence oracle on is exact for matroids and on when, for every , exactly when is independent in , and exactly when is independent in .✦
A rational is a relatively -accurate estimate of when (1)✦
A program with registers and states assigns an instruction to each state .✦ An instruction pushes a given bit onto a register and moves to a given state; or pops a register and moves to one of three given states according as the register was empty or the popped bit was or ; or branches on a coin; or queries the oracle with a bit on the contents of a register and branches on the answer; or halts.✦ Registers hold finite words of bits. A configuration of a program is a record of the contents of the registers, the current state, an output, which is a rational number or absent, and the numbers of oracle calls and of bit operations made so far.✦
A tape is a sequence of bits. The run of a program with oracle on from a configuration is the sequence in which comes from by one step of that is handed as its coin.✦ On the input the initial configuration is in state , holds the binary expansions of , and the numerators and denominators of and in registers to , and has the other registers empty, no output and both counts at zero.✦ A tape of length is a word in , continued by zeros.✦
With , the input length, equal to plus the total number of binary digits of these six numbers✦, the size of the input is (2)✦ and for constants and the resource bound is ✦.
The Estimator and the Frozen Machine
The estimator works on the paired ground set , in which the two copies and of each form the pair .✦ A plain state is a set that contains exactly one element of each pair.✦ A defect state of type , for distinct pairs and , is a set that contains no element of , both elements of and exactly one element of every other pair.✦
With and , the deficiency of a set is (3)✦ cut off at zero, where and are the ranks that the greedy algorithm computes from the oracle for and for .
Let ✦ and ✦, where is five more than the number of binary digits of the denominator of . Phase , for , weighs a set by ✦, and, given multipliers , by when is a defect state of type and otherwise✦. The lazy Metropolis chain of phase moves on the plain and defect states. From it stays put with probability ; otherwise it picks and uniformly, and when is again a state it moves to with probability , staying at otherwise.✦
The multipliers start at . After each phase, every is multiplied by the fraction of plain states among the states visited in that phase divided by the fraction of defect states of type among them.✦ Phase goes ahead only when every multiplier learned so far is positive. It draws a start state by a restart procedure, which begins with a uniform plain state and may fail for lack of random bits from the fair bank defined below. It then runs its chain with the multipliers learned from the earlier phases for steps and records as its sample the states visited, where (4)✦ The restart procedure is cut off at a cap, equal to .
After the phases, let be the average of , with as in (3), over the plain states in the sample of phase .✦ The product estimate is (5)✦ A last restart draws one more plain state. The run outputs when that state has deficiency , and when it does not✦, when a phase does not go ahead, or when a draw fails for lack of random bits.
The random bits come from a fair bank: an array of words of bits each, where and and are explicit polynomials in , and .✦ The th uniform draw from uses row , by rejection sampling on the first bits of its words✦; a coin of bias in lowest terms is a uniform draw from that comes up heads when it is below ✦. The output of one run is a function of the fair bank .
Let , where is the number of binary digits of the denominator of .✦ A full bank is an element of the set of -tuples of fair banks✦, and is the number of its bits✦. The bounded output is the median of , the entry of index , counting from , in their sorted list, when , and when .✦
The frozen machine is one fixed program. It runs a preamble that computes from the parameters , , , , and ; reads coin bits from the tape into a register, three steps per bit; and runs a postamble that cuts these bits into fair banks, runs the estimator on each and returns the bounded output. For a time and a tape , is the word whose bit is .
A computation of the preamble or of the postamble keeps within size when its input and every value computed along the way have size at most .✦ For polynomials and in one variable with natural coefficients, the resource polynomial is (6)✦ where is a fixed polynomial and the constants and are determined by the preamble and the postamble.
A map is an output certificate when the postamble, run on each word together with the parameters, returns ; every is nonnegative and equals when ; and for every (7)✦
The Claim
Theorem 1. There are a program and constants and with the following property.✦ Let and be matroids of rank on , let be an exact independence oracle for them, let and be rationals in , and let , with as in (2). Then on every tape, the run of with oracle from the initial configuration on has, after steps, made at most oracle calls and at most bit operations and produced an output , with when . With the output on the tape , (8)✦
In the paper, the result reads: there is a single randomized oracle algorithm that, given independence oracles for arbitrary matroids of rank on and rationals , outputs a nonnegative rational with , always outputs zero when , makes on every execution a number of oracle calls and of other bit operations bounded by a fixed polynomial in , , and , with the encoding length of , and uses only independent unbiased random bits and no representation of either matroid. In the box, the probability is the fraction of the tapes of length and the polynomial is .
What Is Checked
The claim (8) is stated over matroids of rank on , an exact independence oracle, the number of common bases, relative accuracy (1), programs with their configurations, initial configuration and runs on a tape, and the resource bound .
For the estimator, take matroids and of rank on with an exact independence oracle , and rationals and . The library proves that every full bank has , with when , and that (9)✦
The frozen machine reads a certificate off the tape. Let and be polynomials with natural coefficients, , and as above, rationals and , and , and suppose that the preamble keeps within size on and the postamble keeps within size on every word with the parameters. Then there are an output certificate and a time with such that on every tape the run of the frozen machine for steps from the initial configuration makes at most oracle calls and at most bit operations and produces the output (10)✦
On tapes of length , a certificate is accurate on most tapes: for , and as above, rationals and , an output certificate , and times and with , (11)✦