Suggest edit — SU-CS254 MAR052025

Title

Name

Note

---
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$.