# Working out the constants and probabilities of Stockmeyer's approximate counting algorithm

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?

• idgi, why can't you just calculate it? Feb 7 at 11:16
• It’s not clear to me how Sipser finds this constant $c$, nor how we can find the probability of success in the algorithm.
– Germ
Feb 7 at 19:44
• what exactly is unclear (when you go through the proof to figure out $c$)? Feb 7 at 20:46
• 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!).
– Germ
Feb 8 at 14:47