complexity theory – 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 yields what we would want:

$S subseteq {0,1}^m$ is a set such that membership 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} = 2times2^{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 conlude what we want?

Overall, I’m 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?