<p>Stockmeyer's <a href="https://dl.acm.org/doi/abs/10.1145/800061.808740" rel="nofollow noreferrer">1983 result</a> on approximate counting using a randomness states that if we have some SAT instance <span class="math-container">$x$</span> with <span class="math-container">$C(x)$</span> satisfying assignments, then we can find the minimum set of <span class="math-container">$m$</span> hash functions such that applying the hash functions to the set of satisfying assignments yields different outputs for each assignment and so:</p>
<p><span class="math-container">$$2^{m-c-1} \leq  C(x) \leq m 2^m,$$</span>
where <span class="math-container">$c$</span> is a constant that Stockmeyer mentions is due to <a href="https://dl.acm.org/doi/abs/10.1145/800061.808762" rel="nofollow noreferrer">Sipser</a>. This result is part of Theorem 3.1, under Equation (4). This inequality means we can approximate <span class="math-container">$C(x)$</span> up to a factor of <span class="math-container">$(m2^m) / 2^{m-c-1} = m2^{c+1}$</span>.</p>
<p>I have two related questions:</p>
<p>First, how can we calculate this constant <span class="math-container">$c$</span>? I know the algorithm allows amplification of its results so in some sense this <span class="math-container">$c$</span> 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 <a href="https://www.wisdom.weizmann.ac.il/%7Eoded/PDF/rnd.pdf" rel="nofollow noreferrer">this book</a> it seems like we can use these ideas to get to a factor of <span class="math-container">$2^4 = 16$</span>.</p>
<p>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?</p>

CC BY-SA 4.0
2024-02-07T11:16:11.937Z
idgi, why can't you just calculate it?
mathworker21
CC BY-SA 4.0
2024-02-07T19:44:51.143Z
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
CC BY-SA 4.0
2024-02-07T20:46:28.047Z
what exactly is unclear (when you go through the proof to figure out $c$)?
mathworker21
CC BY-SA 4.0
2024-02-08T14:47:55.740Z
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
<approximation-algorithms><counting-complexity><randomized-algorithms>
Working out the constants and probabilities of Stockmeyer's approximate counting algorithm
Germ
# Working out the constants and probabilities of Stockmeyer's approximate counting algorithm

(Asked by: username_0 on 2024-02-06)

Stockmeyer's [1983 result](https://dl.acm.org/doi/abs/10.1145/800061.808740) 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](https://dl.acm.org/doi/abs/10.1145/800061.808762). 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](https://www.wisdom.weizmann.ac.il/%7Eoded/PDF/rnd.pdf) 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?

**Tags:** approximation-algorithms, counting-complexity, randomized-algorithms

> **Comments:**
> **username_1**: idgi, why can't you just calculate it?  
> **username_0**: It’s not clear to me how Sipser finds this constant $c$, nor how we can find the probability of success in the algorithm.  
> **username_1**: what exactly is unclear (when you go through the proof to figure out $c$)?  
> **username_0**: 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!).  

---

## 0 answers

