I'm reading Arora and Barak's book Computational Complexity, Chapter 19.4 Local Decoding and Hardness Amplification. And I'm confused with the following question:Let $f:\{0,1\}^n\rightarrow\{0,1\}$, then $f$ can also be viewed as a binary string of length $N=2^n$. Using some Error Correcting Code $E:\{0,1\}^N\rightarrow\{0,1\}^M$ with distance $2\rho$ and we get $g=E(f)\in\{0,1\}^M$, let $m=\log M$, then $g$ can be viewed as a function $g:\{0,1\}^m\rightarrow\{0,1\}$. In principle, if $g$ can be computed for $1-\rho$ fraction of $\{0,1\}^m$, then we can compute (maybe not efficiently) $f$ for all $\{0,1\}^n$.If this can be computed efficiently for some $E$, we're done with some worst-case hardness to mild hardness reduction. So we define Local Decoder for $E:\{0,1\}^N\rightarrow\{0,1\}^M$ handling $\rho$ errors to be an algorithm $D$ given random access to a string $v\in\{0,1\}^M$ such that $\triangle(v,E(u))<\rho$ for some $u\in\{0,1\}^N$, and an index $i$, runs for $poly(m)$ time and output $u_i$ with probability $\geq2/3$.But here's the problem, Local Decoder is a probabilistic algorithm correct with probabilistic at least $2/3$ for every index, but what we require is a deterministic circuit that correct for every index.To make it more clear, Local Decoder means we have PPT $D$ that $Pr_r[D(x,r)=f(x)]\geq2/3$ for every $x\in\{0,1\}^n$. $2/3$ here is arbitrary, but we can't find some fixed $r$ that $D$ will be correct for every $x$.
Local Decoding and Hardness Amplification
cc.complexity theory