4
$\begingroup$

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)$)?

$\endgroup$
  • 5
    $\begingroup$ 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$) $\endgroup$ – David Harris Dec 5 '11 at 14:55
  • $\begingroup$ thanks David. I think your comment answers this question. $\endgroup$ – j.s. Dec 5 '11 at 15:41
  • $\begingroup$ random is better than chosen, nearly always. $\endgroup$ – Steve Uurtamo Nov 28 '17 at 22:40
10
$\begingroup$

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$)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jan 14 '15 at 18:33
  • $\begingroup$ 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')$. $\endgroup$ – SpaceMonkey Jan 14 '15 at 22:54
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jan 15 '15 at 0:10
  • $\begingroup$ Oh you're right. I did not see this. $\endgroup$ – SpaceMonkey Jan 15 '15 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.