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
\begin{equation} H = \qty {h: \qty {0,1}^{h} \to \qty {0,1}^{k}} \end{equation}
properties of pairwise independence:
- 1 wise independent: \(\forall y, \forall a\), \(P_{h \sim H}\qty [h\qty(y) = a] = 2^{-k}\)
- 2 wise independent: \(\forall y \neq y’\), \(P_{h \sim H}\qty [h\qty(y) = h\qty(y’)] = 2^{-k}\)
You will notice that this is not full randomness, just that there are some amount of randomness.
Let’s pick \(k\) strings \(r^{(1)} … r^{(k)} \sim \qty {0,1}^{n}\) uniform random things, and \(k\) bits \(b_{1}, …, b_{k} \sim \qty {0,1}\) uniform random bits. This is \(O\qty(kn)\) bits of randomness.
\begin{equation} h\qty(y) = \qty(r^{(1)}y + b_1, r^{(2)} y + b_2, \dots, r^{(k)} y + b_{k}) \end{equation}
This is 1-wise random due to the randomness of \(b_{j}\), since will shift into \(2^{-k}\) random. For 2 wise independenec
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\).