this is for holding javascript data
Sean Geronimo Anderson added question_Linearity_Testing_Suppose_that__.tex
over 8 years ago
Commit id: 72f60e08556084651e2f2120ca5fdda181528de0
deletions | additions
diff --git a/question_Linearity_Testing_Suppose_that__.tex b/question_Linearity_Testing_Suppose_that__.tex
new file mode 100644
index 0000000..14a2d6d
--- /dev/null
+++ b/question_Linearity_Testing_Suppose_that__.tex
...
\question{Linearity Testing.} Suppose that the function $f : \{0,1\}^n
\to \{0,1\}$ satisfies the linearity test over $GF(2)$ with
probability $1-\epsilon$, i.e. $\Pr_{x,y}[f(x)+f(y)=f(x+y)] \geq
1-\epsilon$.
\begin{itemize}
\item[(a)] Prove that for any fixed $z$,
$\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}
