Let and be matroids of the same rank on the ground set , each supplied by an exact independence oracle that reports whether a queried subset of , given as an -bit indicator, is independent. Write for the set of bases of a matroid . The quantity to be estimated is the number of common bases, . For , is the number of bases of one matroid. On the edges of a bipartite graph there are two partition matroids: one allows at most one edge at each vertex of the first vertex class, the other at most one edge at each vertex of the second. For a bipartite graph with vertex classes of equal size and no isolated vertex, the common bases of these two partition matroids are its perfect matchings. For , an estimate of is -accurate when . An FPRAS for in the oracle model is a randomized algorithm that, given rational , outputs an -accurate estimate with probability at least , using a number of oracle calls and of other bit operations bounded by a polynomial in , in the binary encoding length of , in and in . The question is whether the number of common bases of two arbitrary matroids given by independence oracles has an FPRAS.
Jerrum, Sinclair and Vigoda gave an FPRAS for the permanent of a nonnegative matrix, which includes the count of perfect matchings of a bipartite graph. Anari, Liu, Oveis Gharan and Vinzant gave an independence-oracle FPRAS for the number of bases of a single arbitrary matroid. Anari, Oveis Gharan and Vinzant gave a deterministic polynomial-time approximation of within a factor for arbitrary rank- matroids given by independence oracles. They also gave an algorithm that outputs an -accurate estimate of for every given , in a running time with dependence. This running time is fully polynomial when but not for unrestricted rank. A common independent set is a subset of independent in both matroids. Cryan, Guo and Mousa asked for a rapidly convergent Markov chain for uniform sampling of common bases or of common independent sets. Liu’s dissertation records the question of an FPRAS for two arbitrary independence-oracle matroids.
Theorem 1.1 of the preprint answers this question: a single randomized oracle algorithm, which uses only independent unbiased random bits and no representation of either matroid, is an FPRAS for whose output is always zero when and whose polynomial bound holds on every execution, not only in expectation. The preprint derives from it an FPRAS for counting common independent sets of a prescribed cardinality, of unrestricted cardinality, or of the largest cardinality a common independent set attains, even when the two ranks differ, and an almost-uniform sampler for each of these families. The Lean library contains none of these.
The results on these pages are those of the Lean library MatroidCounting, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only, and gives the results their order and their names. The model of computation in the Lean library is an explicit machine that reads its random bits from a tape and queries the oracles. For constants and , let . The Lean library states Theorem 1.1 for one fixed program of this machine: there are constants and such that, for all as above, every run of steps has halted, with at most oracle calls and bit operations, on a nonnegative output that is zero when . For the same constants and inputs, at least of the random tapes of length give an -accurate output. The Lean library proves this theorem with no hypothesis beyond the conditions on its input.
MatroidCounting is a Lean library: 21 items, in eight groups. Each has a page written by OctoInform, listed below.
No item matches.