OctoInformBeta

Approximate counting of common integer polymatroid bases

Let M1M_1 and M2M_2 be matroids of the same rank rr on the ground set [n]={1,…,n}[n]=\{1,\ldots,n\}, each supplied by an exact independence oracle that reports whether a queried subset of [n][n], given as an nn-bit indicator, is independent. Write ℬ(M)\mathcal B(M) for the set of bases of a matroid MM. The quantity to be estimated is the number of common bases, Z=Z(M1,M2)=|ℬ(M1)∩ℬ(M2)|Z=Z(M_1,M_2)=|\mathcal B(M_1)\cap\mathcal B(M_2)|. For M1=M2M_1=M_2, ZZ 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 0<ϵ<10<\epsilon<1, an estimate Ẑ\widehat Z of ZZ is ϵ\epsilon-accurate when (1−ϵ)Z≤Ẑ≤(1+ϵ)Z(1-\epsilon)Z\le\widehat Z\le(1+\epsilon)Z. An FPRAS for ZZ in the oracle model is a randomized algorithm that, given rational ϵ,δ∈(0,1)\epsilon,\delta\in(0,1), outputs an ϵ\epsilon-accurate estimate with probability at least 1−δ1-\delta, using a number of oracle calls and of other bit operations bounded by a polynomial in nn, in the binary encoding length ℓ\ell of n,r,ϵ,δn,r,\epsilon,\delta, in ϵ−1\epsilon^{-1} and in log⁡δ−1\log\delta^{-1}. 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 ZZ within a factor 2O(r)2^{O(r)} for arbitrary rank-rr matroids given by independence oracles. They also gave an algorithm that outputs an ϵ\epsilon-accurate estimate of ZZ for every given ϵ\epsilon, in a running time with 2O(r)2^{O(r)} dependence. This running time is fully polynomial when r=O(log⁡n)r=O(\log n) but not for unrestricted rank. A common independent set is a subset of [n][n] 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 ZZ whose output is always zero when Z=0Z=0 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 C>0C>0 and dd, let B=C(1+n+ℓ+⌈1/ϵ⌉+⌈log⁡2⌈1/δ⌉⌉)dB=C(1+n+\ell+\lceil1/\epsilon\rceil+\lceil\log_2\lceil1/\delta\rceil\rceil)^d. The Lean library states Theorem 1.1 for one fixed program of this machine: there are constants C>0C>0 and dd such that, for all M1,M2,ϵ,δM_1,M_2,\epsilon,\delta as above, every run of BB steps has halted, with at most BB oracle calls and BB bit operations, on a nonnegative output that is zero when Z=0Z=0. For the same constants and inputs, at least (1−δ)2B(1-\delta)2^B of the 2B2^B random tapes of length BB give an ϵ\epsilon-accurate output. The Lean library proves this theorem with no hypothesis beyond the conditions on its input.

The Lean library: MatroidCounting

MatroidCounting is a Lean library: 21 items, in eight groups. Each has a page written by OctoInform, listed below.

§1. Introduction 3 items
  1. Matroids, independence oracles and the common-basis count The input and the target of counting common bases. §1
  2. The machine model A randomized oracle machine on stacks of bits. §1
  3. Theorem 1.1 One machine program approximately counts common bases of two matroids.
§2. The paired-ground-set reduction 3 items
  1. Dual rank (2.1) On sets of rank size, dual rank is complement rank. §2, (2.1)
  2. The paired matroid and transversals Common bases of two matroids as transversal bases of one matroid. §2
  3. Rank weights and defect types (2.2) to (2.4) Rank weights and slot totals over plain and defect states. §2, (2.2) to (2.4)
§3. Quadratic signature inequalities 4 items
  1. The quadratic signature property A signature condition on the face Hessians of slot totals. §3
  2. Theorem 3.1 Matroid rank weights with 0<q≤10<q\le 1 have the slot signature property.
  3. F and F^∨ have the quadratic signature property For 0<q≤10<q\le 1, matroid rank weights have the slot signature property. §3
  4. Lemma 3.2 Quadratic inequalities between slot totals and defect totals.
§4. A transport inequality 1 item
  1. Lemma 4.1 Two energies bound the gap between root means.
§5. A chain and its observable Poincaré bound 6 items
  1. Chain weights, good multipliers and type masses (5.1) to (5.3) Good multipliers give each state type mass at least 1/(20n2)1/(20n^2). §5, (5.1) to (5.3)
  2. The Metropolis chain and its Dirichlet form (5.4), (5.5) The energy of the Metropolis chain as an edge sum. §5, (5.4) and (5.5)
  3. Lemma 5.1 A Poincaré bound for the variance on transversals.
  4. Lemma 5.2 Dirichlet energy ties defect class means to the transversal mean.
  5. The projection Q Averaging over defect classes and under the chain’s law. §5
  6. Proposition 5.3 An observable Poincaré bound on plain and defect states.
§6. Two consequences for simulation 2 items
  1. Lemma 6.1 Warm-started Metropolis time averages have mean squared error O(1/N)O(1/N).
  2. Lemma 6.2 The Metropolis chain watched on transversals is lazy and reversible.
§7. Annealing and learning the multipliers 1 item
  1. Annealing schedule, estimation and accuracy Annealing schedule and error bounds for counting common bases. §7
§8. Oracle implementation, bit bounds, and amplification 1 item
  1. Oracle ranks, fair bits and amplification Oracle ranks are exact and medians of fair runs accurate. §8

No item matches.