---
title: "SU-CS254 MAR052025"
source: https://www.jemoka.com/posts/kbhsu_cs254_mar052025/
date: 2025-03-05
---

Review! Probability Let \(A_1 &hellip;, 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&rsquo;s inequality \begin{equation} P\qty [T \not \in\mu \pm k \sigma] \leq \frac{1}{k^{2}} \end{equation}
Pairwise Independence see Universal Hash Family
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 &gt; 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&mdash;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)})\) &hellip;. 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&rsquo;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\).
