I'm trying to understand the statement of the Goldwasser-Sipser Set Low Bound Protocol as presented in "Computational Complexity: A Modern Approach" by Arora and Barak.

In particular, I'm trying to understand why the following claims yield what we would want:

$S \subseteq \{0,1\}^m$ is a set such that members can be certified. Both parties know a number $K$. Let $k$ be an integer such that $2^{k-2} < K \le 2^{k-1}$.

Claim: Let $S \subseteq \{0,1\}^m$ satisfy $|S| \le 2^{k}/2.$ Then for $p=|S|/2^k$ we have $p \ge \mathbf{P}_{h \in_{_R} \mathcal{H}_{m,k}, y \in_{_R} \{0,1\}^k}\left[\exists x \in S: h(x)=y \right] \ge \frac{3p}{4}-\frac{p}{2^k}.$

My understanding is that we want:

  • If $|S| \ge K$ then the verifier should accept (corresponding to the prover finding such an $x$ in the claim) with "high" probability;
  • If $|S| \le K/2$ then the verifier will accept with probability at most 1/2.

I'm getting thrown off by a few things here:

  • the claim assumes that $|S| \le 2^k/2 = 2^{k-1} = 2\times2^{k-2} < 2 K$, so how does this place us in one of the relevant cases?
  • How do we actually use those left ($p$) and right ($3p/4 - p/2^k$) bounds to conclude what we want?

Overall, I understand bits and pieces of this setup, but I'm having trouble seeing how it all fits together. Can someone walk through the logic/algebra here?


1 Answer 1


To succeed in distinguishing the case of $|S|\ge K$ from $|S|\le\frac{K}{2}$, you just need a constant gap (independent of $|S|$) in the acceptance probability in both cases. If you managed to achieve such a gap, then applying Chernoff to multiple executions of the protocol would achieve high success probability.

Observe that the interesting case is $k\le m$, since otherwise $K\ge 2^{k-2}\ge2^{m-2}$, and the verifier can convince himself that $|S|\ge K$ simply by sampling strings in $\{0,1\}^m$ uniformly at random and checking whether they belong to $S$ (in this case $|S|\ge K$ implies that the probability of falling in $S$ is at least $1/4$, so Chernoff with a polynomial number of samples yields the desired result). From now on assume $m\ge k$, and thus the hash functions are $h_{a,b}:GF(2^m)\rightarrow GF(2^k)$ given by $h_{a,b}=(ax+b)_{1...k}$, where $x_{1...k}$ in the truncation of a string obtained by taking the first $k$ bits.

For uniformly distributed $a,b\in GF(2^m)$, and every $x\in GF(2^m)$, $ax+b$ is uniformly distributed. This means that $\forall x\in GF(2^m): \Pr\limits_{\substack{a,b\in GF(2^m)\\y\in GF(2^k)}}\left[(ax+b)_{1...k}=y\right]=\frac{1}{2^k}$. We conclude that $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\le \frac{|S|}{2^k}$. On the other hand, we can lower bound the same probability by:

$$ \Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge\\ \sum\limits_{x\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y\right]-\sum\limits_{x\neq x'\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y \land h_{a,b}(x')=y\right]=\\\frac{|S|}{2^k}-\frac{}{}\binom{|S|}{2}\frac{1}{2^{2k}}\ge \frac{|S|}{2^k}\left(1-\frac{|S|}{2^{k+1}}\right). $$

So far there were no restrictions on the size of $S$. Now, if $|S|\le K\le 2^{k-1}$ then $\frac{|S|}{2^k}\le\frac{1}{2}$, and we obtain $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge \frac{3}{4}\frac{|S|}{2^k}$. We conclude that if $|S|=K$ then the probability of acceptance is at least $\frac{3}{4}\frac{K}{2^k}$ (the bound trivially holds for larger $|S|$, just by taking a subset of size $K$). If on the other hand $|S|\le K/2$ then the acceptance probability is at most $\frac{1}{2}\frac{K}{2^K}$ and we have our constant gap $\ge\frac{1}{4}\frac{K}{2^k}$, and Chernoff completes the proof.

  • $\begingroup$ Thanks for the detailed write-up, this helps clear up some of my confusion. I think what's holding me back from really seeing the final picture is understanding how the Chernoff bounds actually get applied here. Even in the first case you described ($k \le m$) I'm having trouble actually writing down and using Chernoff. Could you help me see how they specifically work in these cases? $\endgroup$
    – theQman
    Jan 9, 2021 at 23:21
  • $\begingroup$ Suppose we are trying to learn the bias of a coin, which is either $p$ or $p'$ such that $|p-p'|\ge\epsilon>0$. Toss the coin $n$ times, and denote $\hat{p}=\frac{1}{n}\sum\limits_{i=1}^n X_i$. Your algorithm then declares $p$ if $|\hat{p}-p|\le\epsilon/2$, otherwise it replies $p'$. If the bias is $p$ then your algorithm answers incorrectly with probability at most $2e^{-\frac{n\epsilon^2}{4}}$. If however the bias is $p'$, then again your algorithm errs with probability at most $2e^{-\frac{n\epsilon^2}{4}}$. $\endgroup$
    – Ariel
    Jan 10, 2021 at 6:47
  • $\begingroup$ In our case we don't really know $p,p'$, but only know a lower bound $p\ge q$ which also satisfies $p'\le q-\epsilon$ (the constant gap), so your algorithm can check whether $\hat{p}\ge q-\frac{\epsilon}{2}$, i.e. it suffices to know $q,\epsilon$, which in our case is $\frac{3}{4}\frac{K}{2^k}$ and $\epsilon=\frac{1}{4}\frac{K}{2^K}$. $\endgroup$
    – Ariel
    Jan 10, 2021 at 7:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.