1
$\begingroup$

The BLR linearity test and the low degree test are two common tools in PCPs. By my understanding these tests ensure bounds such that (self-) correctors can be applied. I have two questions regarding the use of both parts:

  1. In the literature those tests are always used to check if e.g. a function is 0.99-'close' to a linear function. What is now exactly meant by 'checking'? Is that approximating the closeness by repeating the test and evaluating the approximation (using Chernoff bounds)?

  2. Are correctors always used in a constructive way? Would it make a difference using them to reject a function that needs to be corrected?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Checking means checking, not approximating. If the function is linear/low degree, output YES, if it is not $\delta$-close, output NO with probability depending on $\delta$. Repeating the test will boost the probability of a correct answer. I have no idea what you mean by "constructive". $\endgroup$
    – Emil Jeřábek
    Commented Oct 23, 2014 at 10:34

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.