<p>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:</p>

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

<p>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))&lt;\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$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-11-06T08:06:09.507Z
Oh, does the book mean to run $D$ for $O(n)$ times and take the majority to decrease the error probability to $<2^{-n}$, then using average argument to find out such $r$ correct for all $x$ since there are only $2^n$ x's.
c c
CC BY-SA 3.0
2012-11-06T15:43:44.117Z
Also known as $\mathsf{BPP} \subseteq \mathsf{P\backslash poly}$
Sasho Nikolov
CC BY-SA 3.0
2012-11-06T19:16:30.947Z
I think your own comment answers the question.
Mahdi Cheraghchi
<cc.complexity-theory>
Local Decoding and Hardness Amplification
c c
# Local Decoding and Hardness Amplification

(Asked by: username_0 on 2012-11-06)

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

**Tags:** cc.complexity-theory

> **Comments:**
> **username_0**: Oh, does the book mean to run $D$ for $O(n)$ times and take the majority to decrease the error probability to $<2^{-n}$, then using average argument to find out such $r$ correct for all $x$ since there are only $2^n$ x's.  
> **username_1**: Also known as $\mathsf{BPP} \subseteq \mathsf{P\backslash poly}$  
> **username_2**: I think your own comment answers the question.  

---

## 0 answers

