## DNF counting

Define

- disjunction $m$ clauses
- each a conjunction

Complexity:

- $\SP$-complete.
- Define PRAS, FPRAS

Rare events

- Idea: choose random assignment, count satisfying fraction
- if $p$ small, huge sample size
- importance sampling biases samples toward event.

Coverage algorithm

- given $m$ sets $A_i \subseteq V$, count $\cup A_i$
- problem: random $a \in V$ too rarely satisfies
- Idea:
**Bias**sample to create better odds of interesting event- work in $\uplus A_i$
- size $n$ known
- can sample uniformly from it
- dense subset of right size
- “canonical” assignment is “first” copy of assignment for given clause
- canonical items number same as $\cup A_i$

- Analysis
- assignment $a$, satisfies $s_a$ clauses.
- $\sum_a (s_a/n)(1/s_a) = m/n$
- We know $n$, so can deduce $m$
- How many trials needed? Till get $O(\mu_{\epsilon\delta})$ success
- prob. OK at least $1/m$, so $\Olog(m)$ trials suff.

- unbiased estimator (expectation equals correct value)

### Counting Versus Generation

Counting via generation

- DNF-counting uses
*generation*to (approximately)*count* - Counting is basically probability estimation
- If can generate samples from known set
- Can estimate probability $p$ of event $A$
- As special case (uniform sampling), can count number of points in $A$

- Limiting factor: $p$ cannot be too small
- Sometimes can change sample space to achieve this

Converse: if you can count, you can generate

- Most basic, if can enumerate items in set, can pick one
- Because then you just need to pick a random integer
- And then map to corresponding enumerated item

Generalize beyond direct enumeration:

- e.g., generate a permutation
- could do an $n!$ enumeration
- instead, use knowledge that first item is uniformly distributed
- i.e., use
*counting*knowledge of how many samples have each first item - So, uniformly generate first item
- Then recurse (this is using self-reducibility)

- We already have a satisying assignment generator implicitly
- But suppose we just have a black box for counting satisfying assignments
- Count how many have $x_1$ true and how many have $x_1$ false
- Flip an appropriately biased coin to set $x_1$
- Recurse on other variables
- This approach works for any self-reducible problem

We'll dive deeper into this later.