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)

DNF generation

• 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.