Sampling

In class, I handwaved over the proof that we can efficiently estimate $E\left[F_{S\subseteq I}\right(x{)}^2]$. The proof is very easy:

$E_x\left[F_{S\subseteq I}\right(x{)}^2]=E_x[\widehat{f_x}\left(S{)}^2\right]$ $=E_x\left[\widehat{f_x}\right(S{)}^2]=E_x[\left(E_w\right[f_x\left(w\right)w_S\left]{)}^2\right]$.

Now we use a trick: Pick two copies of $w$ independently:

... $=E_x\left[E_{w,wʹ}\right[f_x\left(w\right)w_S{f}_x(wʹ)w{ʹ}_S\left]\right]$ $=E_{x,w,wʹ}\left[f\right(w,x\left)w_{S}f\right(wʹ,x\left)w{ʹ}_S\right]$.

And this expectation can be efficiently estimated empirically, since we can sample the random variable inside the expectation, and this r.v. is bounded in $[-1,1]$. (I guess officially what I keep using here is "Hoeffding's Bound".)

--

Also: at the end of class, when showing how to break the one-way permutation $f$ given a PPT algorithm $A$ for guessing the hard-core predicate, we had that if $A$ is deterministic, we get that for a $2\gamma$ fraction of $x$'s, ${\mathrm{Pr}}_r\left[A\right(f\left(x\right),r)=x\cdot r]\ge 1/2+\gamma$. If $A$ is not deterministic, let $$ denote the function which on input $r$ equals $E_A\left[A\right(f\left(x\right),r\left)\right]$, where the expectation is over $A$'s randomness. Now $$ is a function with range in $[-1,1]$, so we can apply Goldreich-Levin to it...

Except not quite, since in GL we assume we actually have access to $$, whereas really, we only have access to a $\{-1,1\}$-valued randomized function whose expectation is $$. But I hope you can convince yourself that that's good enough; basically, we just have to throw in an expectation over $A$'s random coins in the derivation in the first part of this post.