I am studying the DNF counting problem from the book Randomized Algorithm by Rajeev Motwani.

Then, by Theorem 11.1(Estimator Theorem), in order to have an $\epsilon$-approximation to $\mid G\mid$ with high probability, the sampling size $\begin{equation}N \geq \displaystyle\frac{4}{\epsilon^{2}\rho}\ln\frac{2}{\delta}\end{equation}$, where $\rho = \displaystyle\frac{\mid G\mid}{\mid U\mid}$.

My question is, our goal is to estimate the size of $\mid G\mid$, we need to repeat the sampling process more than $N$ times, so the value of $\rho$ should be probably known. But in that case, we know $\mid G \mid$, exactly. That is what I am confused.


  1. Here is a lecture note from CMU, DNF counting. And above, $G$ denotes the set of satisfying assignments, while denoting by $S$ in CMU note.
  • $\begingroup$ What is the meaning of DNF ? $\endgroup$ – Jean Marie Jun 6 '17 at 0:21
  • $\begingroup$ @Jean Marie, I have added a reference for DNF counting problem. Thank you. $\endgroup$ – JiaMing Lin Jun 6 '17 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.