Review! Probability
Let \(A_1 …, A_{M}\) be independent events, each with probability \(p\). Let \(T = \sum_{i=1}^{n} A_{i}\), meaning \(T \sim \text{Bin}\qty(n,p)\). \(\mu = \mathbb{E}\qty[T] = np\).
Two facts:
Markov bound
\(P\qty [X \geq k \mathbb{E}[x]] \leq \frac{1}{k}\)
;
Chebyshev’s inequality
\begin{equation} P\qty [T \not \in\mu \pm k \sigma] \leq \frac{1}{k^{2}} \end{equation}
Pairwise Independence
Gouldwasser-Sipsr
Given circuit \(C : \qty {0,1}^{n} \to \qty {0,1}\) and some parameter \(s\), there is an AM (one-round interaction) protocol: if \(\#c > 2s\), we will accept with probability \(\geq \frac{2}{3}\); if \(#c \leq s\), we will reject with probability \(\geq \frac{2}{3}\).
Note that the factor of \(2\) is not important—we can upgrade 64s vs. s protocol to a 2s vs. s protocol.
Notice: given a circuit \(C\), construct \(C^{\wedge 6}\qty(x^{(1)}, \dots, x^{(6)}) = C\qty(x^{(1)}) \wedge C\qty(x^{(2)})\) …. We can observe that, since the number of each of these sub-$C$s multiply, we have \(\#\qty(C^{\wedge 6}, )\)
Consider a choice of \(s = 2^{k}\). Let’s make a random hash function \(h: \qty {0,1}^{n} \to \qty {0,1}^{k+3}\). Authur asks for an \(x\) such that \(C\qty(x) = 1\), and \(h\qty(x) = 0\).