# Statement of the Goldwasser-Sipser Set Low Bound Protocol

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?

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.

• 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? Jan 9 at 23:21
• 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}}$. Jan 10 at 6:47
• 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}$. Jan 10 at 7:01