3
$\begingroup$

I'm trying to understand the proof of the PCP Theorem in "Complexity and Approximation" by G. Ausiello et al. and came across the low degree test which is used to check if a function $f$ given as oracle (or "auxiliary proof") is close to some degree $d$ polynomial. The test uses another "Lines-Oracle" for retrieving $d+1$ coefficients for univariate polynomials defined on lines. Then the test simply compares the univariate polynomial with respect to a random line on a random point with $f$. Why is this "Lines-Oracle" necessary? I mean one could just interpolate $f$ on a random line (with the same amount of queries) and do the same check. Is this just for convenience?

$\endgroup$
10
$\begingroup$

The lines oracle is used to decrease the query complexity of the test from $d+1$ to $2$, at the expense of using a larger alphabet.

If you don't mind making $d+1$ queries, then the lines oracle is indeed unnecessary. However, it is usually better to make two queries over a large alphabet than $d+1$ queries over a small alphabet.

One reason is that, very roughly speaking, we have a technique, called PCP composition, which can be used to reduce the alphabet size of PCPs, but cannot be used to reduce the query complexity. Hence, it is preferable to have small query complexity and large alphabet size rather than the other way around.

A second reason, which is very related to the first one, is that many hardness-of-approximation results are proved based on $2$-query PCPs, but can not be proved using based on a PCP with more queries.

It should be mentioned that there are also generic techniques for reducing the query complexity at the expense of the alphabet size, so one could avoid the lines oracle and apply those techniques instead. However, using the lines oracle gives a more direct proof.

$\endgroup$

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.