Stockmeyer's 1983 result on approximate counting using a randomness states that if we have some SAT instance $x$ with $C(x)$ satisfying assignments, then we can find the minimum set of $m$ hash functions such that applying the hash functions to the set of satisfying assignments yields different outputs for each assignment and so:

$$2^{m-c-1} \leq C(x) \leq m 2^m,$$ where $c$ is a constant that Stockmeyer mentions is due to Sipser. This result is part of Theorem 3.1, under Equation (4). This inequality means we can approximate $C(x)$ up to a factor of $(m2^m) / 2^{m-c-1} = m2^{c+1}$.

I have two related questions:

First, how can we calculate this constant $c$? I know the algorithm allows amplification of its results so in some sense this $c$ is irrelevant, but suppose I don't do any amplification. What kind of bound do we get? I've looked at Sipser's paper, and this is unclear to me. If I look at Theorem 7.14 of this book it seems like we can use these ideas to get to a factor of $2^4 = 16$.

Second, Stockmeyer's algorithm is probabilistic in that it relies on sampling random hash functions. Therefore, the algorithm should only succeed with some probability. What is that probability?

  • 1
    $\begingroup$ idgi, why can't you just calculate it? $\endgroup$ Feb 7 at 11:16
  • $\begingroup$ It’s not clear to me how Sipser finds this constant $c$, nor how we can find the probability of success in the algorithm. $\endgroup$
    – Germ
    Feb 7 at 19:44
  • 1
    $\begingroup$ what exactly is unclear (when you go through the proof to figure out $c$)? $\endgroup$ Feb 7 at 20:46
  • $\begingroup$ In Sipser's paper, I don't see where $c$ even comes from. I imagine it's after Theorem 2, but I can't seem to find mention of it (I could be missing something simple!). $\endgroup$
    – Germ
    Feb 8 at 14:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.