<p>I also came across this problem studying the $NP \subseteq PCP[poly(n), 1]$ proof in Arora's and Barak's book. Here the mentioned self-correction is always applied even though $x$ is always chosen at random. One problem (not mentioned in the book) is that even though $x$ is chosen at random it is used for multiple and therefore dependent queries. Self-correction is used to retrieve the function values independently by interpolating over other (independently) randomly chosen values.  </p>

CC BY-SA 3.0
2015-01-14T18:33:19.790Z
I was curious about your claim and checked the book. The issue is not as much dependence (after all the union bound works with dependent random variables) as the fact that the linear functions (=Hadamard codewords) are queried at random, but *not always uniformly random* positions. For example, both in steps 2 and 3 of the verifier construction $g$ is queried at positions that do not come from the uniform distribution.
Sasho Nikolov
CC BY-SA 3.0
2015-01-14T22:54:33.783Z
I would agree on step 3 since adding up a random set of equations is dependent on the set of equations we have. But step 2 looks fine to me, $r, r'$ are picked uniformly at random to retrieve $g(r \otimes r')$.
SpaceMonkey
CC BY-SA 3.0
2015-01-15T00:10:20.597Z
Notice that $q := r\otimes r'$ is not a uniformly random $n^2$-bit vector. For one thing, $\mathbb{E}[q_{(i,j)}] = 1/4$ and for another entries of $q$ are not independent.
Sasho Nikolov
CC BY-SA 3.0
2015-01-15T00:37:29.777Z
Oh you're right. I did not see this.
SpaceMonkey
CC BY-SA 3.0
2015-01-14T13:57:18.440Z
2015-01-14T13:57:18.440Z
SpaceMonkey
<p>The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2δ$ for all $x$ (not only random $x$) </p>

CC BY-SA 3.0
2011-12-05T17:59:29.723Z
2011-12-05T17:59:29.723Z
David Harris
<p>Original proof of the PCP theorem, uses self-correction property of linear functions. 
Assume we have $f: \{0,1\}^n \rightarrow \{0,1\}$, a function or table of values,
that is $(1-\delta)$-close to some linear function $L$.
Using $f$ we would like to compute $L(x)$ for any desired $x$ with high accuracy. Such a
procedure is called a self-correction procedure since a small amount of errors in the table $f$ can be corrected using probes only to $f$ to provide access to a noise-free version of the linear function L.</p>

<p>Procedure $\text{SelfCorr}(f,x)$ is:</p>

<ol>
<li>Select $y\in\{0,1\}^n$ uniformly at random.</li>
<li>Return $f(x+y)−f(y)$</li>
</ol>

<p>One can prove if $f$ is $\delta$-close to a linear function $L$ for some $\delta&lt;1/4$, then for any $x\in\{0,1\}^n$ the above procedure $\text{SelfCorr}(f,x)$ computes $L(x)$ with probability at least $1−2\delta$.</p>

<p>My question is: Why we don't probe $f$ at $x$ directly. By this way, error of procedure is at most $\delta$ (that is better than $2\delta$ error of $\text{SelfCorr}(f,x)$)?</p>

CC BY-SA 3.0
2011-12-05T14:55:29.063Z
The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2 \delta$ for all $x$ (not only random $x$)
David Harris
CC BY-SA 3.0
2011-12-05T15:41:59.093Z
thanks David.  I think your comment answers this question.
j.s.
CC BY-SA 3.0
2017-11-28T22:40:02.410Z
random is better than chosen, nearly always.
Steve Uurtamo
<cc.complexity-theory><coding-theory><pcp>
On the need for a self-correcting function in the PCP theorem
j.s.
# On the need for a self-correcting function in the PCP theorem

(Asked by: username_0 on 2011-12-05)

Original proof of the PCP theorem, uses self-correction property of linear functions.
Assume we have $f: \{0,1\}^n \rightarrow \{0,1\}$, a function or table of values,
that is $(1-\delta)$-close to some linear function $L$.
Using $f$ we would like to compute $L(x)$ for any desired $x$ with high accuracy. Such a
procedure is called a self-correction procedure since a small amount of errors in the table $f$ can be corrected using probes only to $f$ to provide access to a noise-free version of the linear function L.

Procedure $\text{SelfCorr}(f,x)$ is:

1. Select $y\in\{0,1\}^n$ uniformly at random.
2. Return $f(x+y)−f(y)$

One can prove if $f$ is $\delta$-close to a linear function $L$ for some $\delta<1/4$, then for any $x\in\{0,1\}^n$ the above procedure $\text{SelfCorr}(f,x)$ computes $L(x)$ with probability at least $1−2\delta$.

My question is: Why we don't probe $f$ at $x$ directly. By this way, error of procedure is at most $\delta$ (that is better than $2\delta$ error of $\text{SelfCorr}(f,x)$)?

**Tags:** cc.complexity-theory, coding-theory, pcp
> **Comments:**
> **username_1**: The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2 \delta$ for all $x$ (not only random $x$)  
> **username_0**: thanks David.  I think your comment answers this question.  
> **username_2**: random is better than chosen, nearly always.  

---

## 2 answers

### Answer by username_1 on 2011-12-05. Score: 10 | Accepted answer

The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2δ$ for all $x$ (not only random $x$)


---

### Answer by username_3 on 2015-01-14. Score: 0

I also came across this problem studying the $NP \subseteq PCP[poly(n), 1]$ proof in Arora's and Barak's book. Here the mentioned self-correction is always applied even though $x$ is always chosen at random. One problem (not mentioned in the book) is that even though $x$ is chosen at random it is used for multiple and therefore dependent queries. Self-correction is used to retrieve the function values independently by interpolating over other (independently) randomly chosen values.

> **Comments:**
> **username_4**: I was curious about your claim and checked the book. The issue is not as much dependence (after all the union bound works with dependent random variables) as the fact that the linear functions (=Hadamard codewords) are queried at random, but *not always uniformly random* positions. For example, both in steps 2 and 3 of the verifier construction $g$ is queried at positions that do not come from the uniform distribution.  
> **username_3**: I would agree on step 3 since adding up a random set of equations is dependent on the set of equations we have. But step 2 looks fine to me, $r, r'$ are picked uniformly at random to retrieve $g(r \otimes r')$.  
> **username_4**: Notice that $q := r\otimes r'$ is not a uniformly random $n^2$-bit vector. For one thing, $\mathbb{E}[q_{(i,j)}] = 1/4$ and for another entries of $q$ are not independent.  
> **username_3**: Oh you're right. I did not see this.  

---

