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}\left(n,p\right). \mu = \mathbb{E}\left[T\right] = np. Two facts: Markov bound P\left[X \geq k \mathbb{E}[x]\right] \leq \frac{1}{k} ; Chebyshev’s inequality \begin{equation} P\left[T \not \in\mu \pm k \sigma\right] \leq \frac{1}{k^{2}} \end{equation} Pairwise Independence see Universal Hash Family Gouldwasser-Sipsr Given circuit C : \left\{0,1\right\}^{n} \to \left\{0,1\right\} 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}\left(x^{(1)}, \dots, x^{(6)}\right) = C\left(x^{(1)}\right) \wedge C\left(x^{(2)}\right) …. We can observe that, since the number of each of these sub-Cs multiply, we have \#\left(C^{\wedge 6}, \right) Consider a choice of s = 2^{k}. Let’s make a random hash function h: \left\{0,1\right\}^{n} \to \left\{0,1\right\}^{k+3}. Authur asks for an x such that C\left(x\right) = 1, and h\left(x\right) = 0.