this is for holding javascript data
Sean Geronimo Anderson edited question_Linearity_Testing_Suppose_that__.tex
over 8 years ago
Commit id: 6bf37bd6be34104a1e920bcaa0c7f2d574cdedaa
deletions | additions
diff --git a/question_Linearity_Testing_Suppose_that__.tex b/question_Linearity_Testing_Suppose_that__.tex
index 14a2d6d..6ac2bba 100644
--- a/question_Linearity_Testing_Suppose_that__.tex
+++ b/question_Linearity_Testing_Suppose_that__.tex
...
$\Pr[f(z+r_1)+f(r_1)=f(z+r_2)+f(r_2)] \geq 1 - 2\epsilon$. (Hint:
suppose $f(r_1)+f(r_2) = f(r_1+r_2)$; what is the relationship
between $f(z+r_1)$ and $f(z+r_2)$?)
\item[(b)] Show that for every $z \in \{0,1\}^n$, there exists a
value $f'(z)$ such that $\Pr_r[f(z+r)+f(r)=f'(z)] \geq \frac{1}{2} +
\sqrt{\frac{1}{4}-\epsilon}$. (so the probability tends to 1 as
$\epsilon$ approaches zero) \end{itemize}