Given some set $S \subseteq \{0,1\}^n$, suppose we want to approximate $|S|$. One approach is hashing-based approximate counting, which exploits the structure of hash functions to approximately halve $|S|$ in each iteration $i$ of the algorithm. When $i \approx \log_2 |S|$, only one element will remain with some finite probability. Using this insight, we can build a counter.

I'm following the presentation in Goldreich's Computational Complexity: A Conceptual Perspective, Theorem 6.27. The hash family is denoted $H_n^i$, which is a function from $n$-bits to $i$-bits, and we uniformly sample $h$ from this family. Goldreich then uses the following (Equation 6.8), which applies for pairwise independent hash functions:

$$\mathrm{Pr}_{h \in H_n^i}\left[ |\{ y \in S \, : \, h(y) = 0^i \}| \notin \left(1 - \epsilon, 1 + \epsilon \right) \cdot 2^{-i} |S| \right] < \frac{2^i}{\epsilon^2 |S|},$$ for some $\epsilon > 0$. (The choice of $0^i$ is arbitrary, as shown in Appendix D.2.)

If we define $S_i \equiv \{ y \in S \, : \, h(y) = 0^i \}$, the algorithm works as follows. For iteration $1 \leq i \leq n$, sample $h \in H_n^i$ and then check if $|S_i| = 0$ (or some small constant $c$). If the answer is "No", continue to the next iteration. At the first answer of "Yes", output $c2^i$ as the approximation. Goldreich shows that we can upper bound the probability that the iteration in which the algorithm stops is far from $\log_2|S|$, which gives us an approximation to the count (in the textbook case, the approximation is up to a factor of $16$.

For example, to bound the probability that the output is $i < \lfloor \log_2|S| \rfloor - 3$, Goldreich uses the above inequality on the probability and adds the contributions up for all $i < \lfloor \log_2|S| \rfloor - 3$. A similar argument works for $i \geq \lfloor \log_2|S| \rfloor + 4$.

My question is: What if we simply sample a single hash function $h \in H_n^n$ at the beginning, and then at each iteration $i$, we use the "prefix slice" $h_{:i}$, which is the first $i$-bits of the hash function?

This construction would imply $S_{1} \supseteq S_{2} \supseteq \cdots \supseteq S_{n}$. It would also mean the hash functions at each iteration aren't independent, yet $h_{:i}$ is uniformly chosen from $H_n^i$. It seems to me that Goldreich's analysis should go through, but I'm unsure if I'm missing some piece about independence in each iteration of the algorithm.

I've seen papers where they bring this issue up (see Section 5 in "Probabilistic Model Counting with Short XORs" and the paragraph before Algorithm 2 and Section 4.2 in "Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls", which discusses "prefix slices" of $h$). In those cases though, they are looking for other improvements by using this construction.



Your Answer

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