Back to PCP
Back to notes

# Low Degree Tests

0%

This note is mainly based on Oded Goldreich’s lecture notes, which are based on the work of Rubinfeld and Sudan (Rubinfeld & Sudan, 1996).

## Introduction and motivation

The goal of low degree polynomial test (LDT) is as follows: Given an oracle access to a function $f:\bbF^m\rightarrow\bbF$, where $\bbF$ is a finite filed of cardinality at least $2d$, is $f$ a degree $d$ polynomial?

As we cannot hope for a perfect text since $f$ could be different to a degree $d$ polynomial at exactly one point. A reasonable goal for a test should have the following properties:

• (perfect completeness) If $f$ is a degree $k$ polynomial, then the test always accepts.
• (soundness) If the test accepts $f$ with probability at least $1-\delta$, then $f$ is $O(\delta)$-close to a degree $k$ polynomial.

Note that we care about the number of randomness used in the test, the number of queries used in the test, and the complexity of the test.

### Error regimes

Also, the value of $\delta$ the test can handle is also important. There are basically two regimes of $\delta$ we care about in the soundness part:

• (high error) If the test accepts with probability close to one.
• (low error) If the test accepts with probability close to zero.

The test we are going to focus on deals with the high error regime while other tests such as (Arora & Sudan, 2003) and (Raz & Safra, 1997) deal with the low error regime.

## Intuitions and some tools

### Univariate LDT

Let’s play with the univariate LDT as a warmup. Given an oracle access to function $f:\bbF\rightarrow\bbF$ where $\bbF$ is a finite prime field of cardinality at least $2d$. Consider the following test:

Univariate LDT

1. Random sample $x,y\in\bbF\backslash\{0\}$.
2. Query $f$’s value on ‘$x,x+y,x+2y,\dots,x+(d+1)y$.
3. Fit $x+y,\dots,x+(d+1)y$ with a degree $d$ polynomial $p$ using Lagrange interpolation.
4. If $f(x)=p(x)$, accepts. Otherwise, rejects.

We can analyze the univariate LDT using the nice properties of polynomial.

The univariate LDT has the following properties:

• (randomness) It requires $2\log\card{\bbF}$ random bits.
• (query) It requires $d+2$ oracle queries to $f$.
• (perfect completeness) For any degree $d$ polynomial $f$, the tests always accepts.
• (soundness) If the test accepts with probability at least $1-\delta$

## References

1. Rubinfeld, R., & Sudan, M. (1996). Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2), 252–271.
2. Arora, S., & Sudan, M. (2003). Improved low-degree testing and its applications. Combinatorica, 23(3), 365–426.
3. Raz, R., & Safra, S. (1997). A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (pp. 475–484). ACM.