47.05.04 · theoretical-cs / 05-randomized-algorithms

FPRAS for Counting Problems: DNF Counting and the Permanent

shipped3 tiersLean: none

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 17; Jerrum, Sinclair and Vigoda 2004 A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries (JACM) (simulated annealing on the switch-or-stay Markov chain)

Intuition Beginner

Counting is harder than deciding. Asking "does a satisfying assignment exist?" is one thing. Asking "how many satisfying assignments are there?" is another entirely. The first is NP. The second is #P, a class that captures counting problems, and it is believed to be much harder.

But we can often estimate the count without computing it exactly. Think of estimating the number of fish in a lake. You cannot count every fish, but you can catch some, tag them, release them, catch more, and see what fraction are tagged. This Monte Carlo approach gives an estimate whose accuracy improves with more samples.

A Fully Polynomial-Time Randomised Approximation Scheme (FPRAS) does exactly this for counting problems. Given a counting function $f$ and an error parameter $ε$ , it runs in time polynomial in the input size and $1/ ε$ , and outputs an estimate within a factor of $(1 + ε)$ of the true count with high probability. The key insight is that random sampling, done carefully, can turn an intractable exact counting problem into a tractable approximate one.

Two landmark examples drive the theory. Counting satisfying assignments of a DNF formula has a simple FPRAS using the Karp-Luby method. Approximating the permanent of a matrix (equivalent to counting perfect matchings) has a sophisticated FPRAS via Markov chain Monte Carlo.

Visual Beginner

Exact counting vs. approximate counting:

  Formula: (x1 AND x2) OR (x3 AND NOT x4)
  
  Exact: enumerate all 16 assignments, count satisfying ones
    0000: 0    0001: 0    0010: 1    0011: 1
    0100: 0    0101: 0    0110: 1    0111: 1
    1000: 0    1001: 0    1010: 1    1011: 1
    1100: 1    1101: 1    1110: 1    1111: 1
  Count = 9

  FPRAS: sample random assignments, count fraction satisfying
    Sample 100 assignments -> ~56% satisfying -> estimate ~9.0
    (With enough samples, the estimate is within (1+eps) of 9)

Problem	Exact counting	Approximate (FPRAS?)
DNF satisfying assignments	#P-complete	Yes (Karp-Luby)
Perfect matchings (permanent)	#P-complete	Yes (JSV Markov chain)
SAT (CNF) satisfying assignments	#P-complete	No (unless NP = RP)
Independent sets in bipartite graphs	#P-complete	Yes (Markov chain)

Worked example Beginner

We estimate the number of satisfying assignments of a DNF formula using the Karp-Luby method.

Formula: $φ = (x_{1} \land x_{2}) \lor (\overset{x}{ˉ}_{3} \land x_{4})$ over 4 variables.

Step 1: Identify the clauses. $C_{1} = x_{1} \land x_{2}$ has $2^{4 - 2} = 4$ satisfying assignments (the two specified variables are fixed, the other two are free). $C_{2} = \overset{x}{ˉ}_{3} \land x_{4}$ also has $2^{4 - 2} = 4$ satisfying assignments.

Step 2: Compute the union size. The total number of assignments satisfying at least one clause is at most $∣ S_{1} ∣ + ∣ S_{2} ∣ = 4 + 4 = 8$ , but this overcounts assignments satisfying both clauses. Both $C_{1}$ and $C_{2}$ are satisfied when $x_{1} = 1, x_{2} = 1, x_{3} = 0, x_{4} = 1$ — only one assignment. So $∣ S_{1} \cup S_{2} ∣ = 4 + 4 - 1 = 7$ .

Step 3: Estimate via sampling. The Karp-Luby trick: instead of sampling from ${0, 1}^{4}$ , sample uniformly from $S_{1} \cup S_{2}$ (the satisfying assignments) and use the estimator $X = (∣ S_{1} ∣ + ∣ S_{2} ∣) \cdot 1 [sample is in exactly one S_{i}]$ . The simpler version: sample a random clause $C_{i}$ with probability $∣ S_{i} ∣/ (∣ S_{1} ∣ + ∣ S_{2} ∣)$ , then sample a random assignment from $S_{i}$ , and check if it satisfies any earlier clause.

The estimate is $\hat{N} = ∣ S_{1} ∣ \cdot (fraction of samples unique to C_{1}) + ∣ S_{2} ∣ \cdot (fraction unique to C_{2})$ . With enough samples, this converges to 7.

Check your understanding Beginner

Formal definition Intermediate+

Definition (FPRAS). A fully polynomial-time randomised approximation scheme for a function $f : Σ^{*} \to N$ is a randomised algorithm $A$ that, on input $x \in Σ^{*}$ and $ε, δ \in (0, 1)$ , runs in time $poly (∣ x ∣, 1/ ε, lo g (1/ δ))$ and outputs $A (x)$ satisfying:

Pr [(1 - ε) f (x) \leq A (x) \leq (1 + ε) f (x)] \geq 1 - δ .

Definition (#P). A function $f : Σ^{*} \to N$ is in #P if there exists a polynomial-time nondeterministic Turing machine $M$ such that $f (x) = ∣ accepting paths of M on x ∣$ .

Definition (permanent). The permanent of an $n \times n$ matrix $A$ is:

perm (A) = σ \in S_{n} \sum i = 1 \prod n a_{i, σ (i)} .

Unlike the determinant, the permanent does not include signs from the permutation parity.

Definition (DNF counting). Given a DNF formula $φ = C_{1} \lor C_{2} \lor \dots \lor C_{m}$ over $n$ variables, compute $∣ {x \in {0, 1}^{n} : φ (x) = 1} ∣$ .

Counterexamples to common slips

"FPRAS means the algorithm is always correct." No. It has a failure probability $δ$ that can be made arbitrarily small by repetition. A single run has at least 2/3 success probability.
"The permanent equals the determinant." The determinant has signs: $det (A) = \sum_{σ} sgn (σ) \prod_{i} a_{i, σ (i)}$ . The permanent drops the signs. This small difference makes the determinant computable in polynomial time but the permanent #P-complete.
"If a problem has an FPRAS, then exact counting is also easy." No. DNF counting is #P-complete (so exact counting is hard), but it has an FPRAS. Approximate counting can be much easier than exact counting.

Key theorem with proof Intermediate+

Theorem (Karp-Luby FPRAS for DNF counting). There is an FPRAS for counting the number of satisfying assignments of a DNF formula.

Proof sketch. Let $φ = C_{1} \lor \dots \lor C_{m}$ be a DNF formula over $n$ variables. For each clause $C_{i}$ , let $S_{i} = {x \in {0, 1}^{n} : C_{i} (x) = 1}$ be the set of assignments satisfying $C_{i}$ . We want $∣ ⋃_{i} S_{i} ∣$ .

The estimator. Define $Ω = {(i, x) : x \in S_{i}}$ with $∣Ω∣ = \sum_{i} ∣ S_{i} ∣$ . Each element of $Ω$ is a (clause, satisfying assignment) pair. Sample uniformly from $Ω$ by first picking clause $C_{i}$ with probability $∣ S_{i} ∣/∣Ω∣$ , then picking $x \in S_{i}$ uniformly at random.

Define $Y = ∣Ω∣$ if the sampled pair $(i, x)$ satisfies $x \in / S_{j}$ for all $j < i$ (i.e., $x$ does not satisfy any earlier clause), and $Y = 0$ otherwise.

Expectation. $E [Y] = ∣Ω∣ \cdot Pr [no earlier clause satisfied] = ∣Ω∣ \cdot ∣ ⋃_{i} S_{i} ∣/∣Ω∣ \cdot (correction)$ . More precisely, each assignment $x \in ⋃_{i} S_{i}$ contributes to $Y$ exactly once (when it is sampled with its minimum-index satisfied clause). So $E [Y] = ∣ ⋃_{i} S_{i} ∣$ .

Variance bound. The ratio $E [Y^{2}] / E [Y]^{2}$ is bounded by a polynomial because each clause has at most $2^{n - ∣ C_{i} ∣}$ satisfying assignments, and the number of overlapping clauses is bounded by the formula structure. Taking $O (1/ ε^{2})$ independent samples and averaging gives a $(1 \pm ε)$ estimate with constant probability. Repeating and taking the median boosts to probability $1 - δ$ . $□$

Bridge. The Karp-Luby estimator is the foundational reason DNF counting admits an FPRAS: by sampling from the union of satisfying sets via a weighted clause distribution, the variance is controlled enough for polynomial-sample convergence, and this builds toward the Markov chain methods needed for harder counting problems like the permanent where direct sampling from the solution space is impossible. This is exactly the pattern that appears again in the JSV algorithm where a rapidly-mixing Markov chain replaces uniform sampling, and it generalises to the entire field of approximate counting via self-reducibility. The central insight is that the gap between #P-completeness and approximability is bridged by random sampling with controlled variance, and putting these together with the hashing techniques of 47.05.01 yields the full machinery of approximate counting.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

The self-reducibility of the permanent means $perm (A) = a_{11} \cdot perm (A_{11}) + \dots + a_{1 n} \cdot perm (A_{1 n})$ where $A_{1 j}$ is the minor obtained by deleting row 1 and column $j$ . Show how this self-reducibility can be used to construct a telescoping-product estimator for $perm (A)$ .

Hint

Define $Z_{i} = perm (A_{i})$ where $A_{i}$ is the matrix after fixing the first $i$ rows, and estimate each ratio $Z_{i} / Z_{i - 1}$ separately.

Answer

Define $A^{(0)} = A$ . For $k = 1, \dots, n$ , let $p_{k} = Pr [column j chosen for row k] = a_{k, j} \cdot perm (A_{k j}^{(k - 1)}) / perm (A^{(k - 1)})$ . The self-reducibility gives $perm (A^{(k - 1)}) = \sum_{j} a_{k j} \cdot perm (A_{k j}^{(k - 1)})$ . Define $Z_{k} = perm (A^{(k)})$ where $A^{(k)}$ is the $(n - k) \times (n - k)$ minor after fixing rows $1, \dots, k$ . Then $perm (A) = Z_{0} = (Z_{0} / Z_{1}) \cdot (Z_{1} / Z_{2}) \dots (Z_{n - 1} / Z_{n})$ where $Z_{n} = 1$ .

Each ratio $Z_{k - 1} / Z_{k}$ equals $1/ p_{k}$ where $p_{k}$ is the probability of choosing column $j_{k}$ for row $k$ under the conditional distribution. An FPRAS estimates each $p_{k}$ (hence each ratio) by sampling from the distribution over columns using the JSV Markov chain. The product of $n$ estimated ratios gives the permanent estimate. The total error is controlled because each ratio estimate contributes a multiplicative $(1 \pm ε / n)$ factor, and the product telescopes. Rubric: full credit for setting up the telescoping product and connecting each ratio to the conditional probability.

Exercise 7 (hard, symbolic).

Prove that the Markov chain for sampling perfect matchings (used in the JSV algorithm) is aperiodic and irreducible on the state space of all perfect and near-perfect matchings of a bipartite graph.

Hint

Show that every state has a self-loop (aperiodicity) and that any matching can be reached from any other via a sequence of edge switches (irreducibility).

Answer

The state space consists of all matchings (perfect and near-perfect, where a near-perfect matching misses exactly two vertices, one from each side). The transitions are: (1) select an edge $e$ uniformly at random; if $e \in M$ , remove it with probability $1/2$ ; if $e \in / M$ , add it if both endpoints are free; (2) select a 2-edge path $(e_{1}, e_{2})$ and swap (add $e_{1}$ , remove $e_{2}$ or vice versa).

Self-loop (aperiodicity): For any matching $M$ , the transition "select an edge $e \in M$ and choose not to remove it" gives a self-loop with positive probability. So all states have self-loops, implying aperiodicity.

Irreducibility: Given two matchings $M_{1}$ and $M_{2}$ , we show a path exists. The symmetric difference $M_{1} △ M_{2}$ is a collection of alternating paths and cycles. Each alternating cycle can be traversed by a sequence of swap transitions: walk around the cycle, swapping edges in and out. Each alternating path can be handled by adding the free edge, then swapping along the path. Repeating this for all components of $M_{1} △ M_{2}$ transforms $M_{1}$ into $M_{2}$ . Near-perfect matchings are included because an edge removal creates one. So the chain is irreducible. Rubric: full credit for proving both aperiodicity and irreducibility.

Exercise 8 (hard, short answer).

Explain why the FPRAS for the permanent of nonnegative matrices does not extend to matrices with negative entries. What additional barrier arises?

Answer

The FPRAS for nonnegative permanents relies on the Markov chain sampling matchings from a probability distribution proportional to $\prod_{e} w_{e}$ . When weights are nonnegative, this defines a valid probability distribution. With negative entries, the "distribution" assigns negative weights to some matchings, making it impossible to sample directly. The permanent becomes a signed sum $\sum_{σ} sgn (σ) \prod a_{i, σ (i)}$ , where cancellations between positive and negative terms can reduce the magnitude drastically relative to the individual terms. The signal-to-noise ratio blows up: the permanent might be close to zero while individual terms are large, making relative approximation impossible without exact computation. This is why computing the permanent of general integer matrices is #P-hard to even approximate within any factor.

Lean formalization Intermediate+

Mathlib has no formalization of FPRAS, the Karp-Luby estimator, or Markov chain Monte Carlo methods for counting. The permanent is defined in Mathlib (Matrix.perm), but there is no connection to approximate counting, no rapidly-mixing Markov chain formalization, and no self-reducibility telescoping product construction. A formalization of the Karp-Luby DNF counting FPRAS would be the natural entry point, requiring a FPRAS typeclass, a proof that the Karp-Luby estimator is unbiased, and a variance bound. This unit ships without a lean_module.

Advanced results Master

Three directions extend the basic FPRAS framework.

Result 1 (rapid mixing via canonical paths). The JSV Markov chain achieves rapid mixing in time $O (n^{7} lo g (1/ ε))$ . The proof uses the canonical paths method: for each pair of states $(M_{1}, M_{2})$ , define a canonical path through the state space. The congestion of the canonical paths bounds the spectral gap, which bounds the mixing time. The key technical ingredient is the fact that the space of perfect and near-perfect matchings forms a connected graph under the switch operation, and the number of canonical paths through any transition edge is bounded by a polynomial in $n$ ^{[JSV 2004]}.

Result 2 (FPRAS for other #P-complete problems). Several other #P-complete counting problems admit FPRAS: the number of independent sets in a bipartite graph (via the hard-core model Markov chain), the number of linear extensions of a partial order (via Karzanov-Khachiyan chain), and the partition function of the ferromagnetic Ising model (via Jerrum-Sinclair). The common technique is: identify a Markov chain on the solution space, prove rapid mixing (via canonical paths or coupling), and use the mixing time to bound the sample complexity for the estimator ^{[Arora-Barak Ch. 17]}.

Result 3 (connections to approximate counting and approximate sampling). The equivalence between approximate counting and approximate sampling (Jerrum, Valiant and Vazirani 1986) states that for self-reducible problems, an FPRAS exists iff there is a polynomial-time algorithm for approximate uniform sampling from the solution space. This equivalence is the structural reason why FPRAS constructions always go through a sampling algorithm: the JSV chain samples matchings approximately uniformly, and the telescoping product converts this into a count estimate ^{[Arora-Barak Ch. 17]}.

Synthesis. The FPRAS framework is the foundational reason that #P-completeness does not preclude efficient approximate counting: self-reducibility connects counting to sampling, and rapidly-mixing Markov chains provide the sampling engine. The central insight is that the variance of a well-designed estimator can be bounded independently of the exact count, so a polynomial number of samples suffices for a $(1 \pm ε)$ estimate. This builds toward the derandomisation questions of 47.05.05 where eliminating the randomness from these schemes would imply collapse of the polynomial hierarchy, and this is exactly the pattern that appears again in 47.02.07 where Toda's theorem shows that the counting hierarchy contains the entire polynomial hierarchy. Putting these together with the hashing techniques of 47.05.01 yields the full picture: randomised approximate counting is possible for a rich class of #P-complete problems, and the boundary between approximable and inapproximable counting problems maps to the boundary between NP and harder complexity classes.

Full proof set Master

Proposition 1 (Karp-Luby estimator is unbiased). The Karp-Luby estimator $Y$ for $∣ ⋃_{i = 1}^{m} S_{i} ∣$ satisfies $E [Y] = ∣ ⋃_{i = 1}^{m} S_{i} ∣$ .

Proof. The sample space is $Ω = {(i, x) : x \in S_{i}}$ with uniform distribution. Define $Y (i, x) = ∣Ω∣$ if $x \in / S_{j}$ for all $j < i$ , and $Y (i, x) = 0$ otherwise.

For each $x \in ⋃_{i} S_{i}$ , let $i^{*} (x) = min {i : x \in S_{i}}$ . The pair $(i^{*} (x), x) \in Ω$ satisfies the condition $x \in / S_{j}$ for $j < i^{*} (x)$ , so $Y (i^{*} (x), x) = ∣Ω∣$ .

For any other pair $(i, x)$ with $i > i^{*} (x)$ and $x \in S_{i}$ , we have $x \in S_{i^{*} (x)}$ with $i^{*} (x) < i$ , so $Y (i, x) = 0$ .

For pairs $(i, x)$ with $i < i^{*} (x)$ and $x \in S_{i}$ , this is impossible since $i^{*} (x) = min {i : x \in S_{i}}$ .

So $Y$ is nonzero only on pairs $(i^{*} (x), x)$ , one per element $x \in ⋃_{i} S_{i}$ . Therefore:

E [Y] = \frac{1}{∣Ω∣} (i, x) \in Ω \sum Y (i, x) = \frac{1}{∣Ω∣} \cdot ∣ i ⋃ S_{i} ∣ \cdot ∣Ω∣ = ∣ i ⋃ S_{i} ∣. □

Proposition 2 (sample complexity of FPRAS). If an unbiased estimator $Y$ for $f (x)$ satisfies $E [Y^{2}] \leq c \cdot f (x)^{2}$ for some constant $c$ , then $O (c / ε^{2})$ independent copies of $Y$ suffice to obtain a $(1 \pm ε)$ -estimate of $f (x)$ with probability at least 2/3.

Proof. Let $\overset{ˉ}{Y} = \frac{1}{N} \sum_{k = 1}^{N} Y_{k}$ where the $Y_{k}$ are independent copies of $Y$ . By Chebyshev's inequality:

Pr [∣ \overset{ˉ}{Y} - f (x) ∣ > ε f (x)] \leq \frac{Var ( Y ˉ )}{ε ^{2} f ( x ) ^{2}} = \frac{E [ Y ^{2} ] - f ( x ) ^{2}}{N ε ^{2} f ( x ) ^{2}} \leq \frac{c - 1}{N ε ^{2}} .

Setting $N = 3 (c - 1) / ε^{2}$ makes this at most $1/3$ . So $Pr [(1 - ε) f (x) \leq \overset{ˉ}{Y} \leq (1 + ε) f (x)] \geq 2/3$ . $□$

Connections Master

47.05.01 — Universal and perfect hashing provide the randomness infrastructure used in counting: the Karp-Luby estimator uses random sampling, and the method of conditional expectations can derandomise parts of the scheme.
47.02.07 — #P-completeness of the permanent (Valiant's theorem) establishes that exact counting is #P-hard; this unit shows approximate counting avoids the barrier.
47.03.06 — Hardness of approximation for NP optimisation problems parallels the inapproximability results for #P counting problems (e.g., #SAT has no FPRAS unless NP = RP).
47.05.05 — Derandomisation of FPRAS algorithms would give deterministic approximation schemes; the impossibility of doing so for some problems connects to the derandomisation landscape.

Historical & philosophical context Master

The theory of approximate counting was pioneered by Karp and Luby (1983) who gave the first FPRAS for DNF counting. The broader framework connecting counting and sampling was developed by Jerrum, Valiant and Vazirani (1986), who proved the equivalence of approximate counting and approximate sampling for self-reducible problems. The crowning achievement is the Jerrum-Sinclair-Vigoda algorithm (2004) for the permanent, which resolved a major open problem by providing an FPRAS for one of the most natural #P-complete functions.

The permanent has a storied history: it was defined by Cauchy in 1812 alongside the determinant, and its computational complexity was studied by Marcus and Minc from the 1960s. Valiant's 1979 proof that computing the permanent of a 0-1 matrix is #P-complete (even for 0-1 matrices) established that exact computation is intractable. The JSV algorithm showed that approximate computation is feasible, completing the picture ^{[JSV 2004]}.

The philosophical lesson is that the gap between exact and approximate computation can be vast: a problem can be #P-complete (and hence at least as hard as any NP problem) yet admit an efficient randomised approximation. Randomness, in this context, is not a convenience but a necessity—derandomising the JSV algorithm would imply a collapse of the polynomial hierarchy.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{jerrum2004polynomial,
  author  = {Jerrum, Mark and Sinclair, Alistair and Vigoda, Eric},
  title   = {A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries},
  journal = {Journal of the ACM},
  volume  = {51},
  number  = {4},
  pages   = {671--697},
  year    = {2004},
}
@inproceedings{karpluby1983monte,
  author    = {Karp, Richard M. and Luby, Michael},
  title     = {Monte-Carlo Algorithms for Enumeration and Reliability Problems},
  booktitle = {Proceedings of the 24th IEEE Symposium on Foundations of Computer Science},
  year      = {1983},
  pages     = {56--64},
}
@article{jerrum1986self,
  author  = {Jerrum, Mark R. and Valiant, Leslie G. and Vazirani, Vijay V.},
  title   = {Random Generation of Combinatorial Structures from a Uniform Distribution},
  journal = {Theoretical Computer Science},
  volume  = {43},
  pages   = {169--188},
  year    = {1986},
}

Prerequisites

47.05.01

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 17 (estimating the number of solutions to NP problems using random sampling)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 17 (FPRAS definition, Karp-Luby DNF counting, Markov chain Monte Carlo for the permanent)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 17; Jerrum, Sinclair and Vigoda 2004 A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries (JACM) (simulated annealing on the switch-or-stay Markov chain)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 17 develops fully polynomial-time randomised approximation schemes (FPRAS) for counting problems, defining an FPRAS for a function $f$ as a randomised algorithm that on input $x$ and error parameter $ε \in (0, 1)$ runs in time $poly (∣ x ∣, 1/ ε)$ and outputs $\hat{f}$ with $Pr [(1 - ε) f (x) \leq \hat{f} \leq (1 + ε) f (x)] \geq 2/3$ ; the chapter presents the Karp-Luby framework for DNF counting (estimate $∣ {x : φ (x) = 1} ∣$ for DNF formula $φ$ by sampling clause-satisfying assignments uniformly and using the inclusion-exclusion-like union bound), and the Markov chain Monte Carlo approach to approximating the permanent of a 0-1 matrix (which counts perfect matchings in a bipartite graph) via the Jerrum-Sinclair-Vigoda Markov chain that alternately adds, removes, or swaps edges of a matching with Metropolis-type acceptance probabilities.
Jerrum, M., Sinclair, A. and Vigoda, E. — A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries · Journal of the ACM 51(4):671--697 (2004). Presents a polynomial-time FPRAS for the permanent of an $n \times n$ matrix with nonnegative entries, based on a Markov chain whose state space consists of all near-perfect matchings in a bipartite graph; the chain performs switch operations (replace an edge $(u, v) \in M$ with an edge $(u^{'}, v^{'}) \in / M$ and a double-edge operation) and achieves rapid mixing (mixing time $O (n^{7} lo g (1/ ε))$ ) via the canonical paths argument; the permanent $perm (A) = \sum_{σ} \prod_{i} a_{i, σ (i)}$ is then estimated by self-reducibility and sequential sampling along a telescoping product.

Estimated time

beginner: 15m
intermediate: 40m
master: 90m