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

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

2 Answers 2

Reset to default
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$)

Improve this answer
$\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.

Improve this answer
$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 at 0:10
  • $\begingroup$ Oh you're right. I did not see this. $\endgroup$
    – SpaceMonkey
    Jan 15, 2015 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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