Low-degree testing

(Ingredient 2 of 5 in the PCP overview.)

The issue

In the general sum-check protocol we just described, we have what looks like a pretty neat procedure, but the elephant in the room is that we needed to make a call to some oracle to evaluate a low-degree polynomial. Just one call, which we denoted $P(r_1, \dots, r_n)$, but you need an oracle nonetheless. Also, the protocol we just described was interactive; but it would be nice to make it non-interactive.

When we do PCP, the eventual plan we are going to replace both the oracle call and Peggy’s answers with a printed phone book. The phone book contains, among other things, a big table mapping every $n$-tuple $(r_1, \dots, r_n) \in \mathbb{F}_q^n$ to its value $P(r_1, \dots, r_n)$ that Peggy mails to Victor via Fedex or whatever. This is of course a lot of work for Peggy to print and mail this phone book. However, Victor doesn’t care about Peggy’s shipping costs. After all, it’s not like he’s reading the phone book; he’s just checking the entries he needs. (That’s sort of the point of a phone book, right?)

But now there’s a new issue. How can we trust the entries of the phone book are legitimate? After all, Peggy is the one putting it together. If Peggy was trying to fool Victor, she could write whatever she wanted (“hey Victor, the value of $P$ is $42$ at every input”) and then just lie during the sum-check protocol. After all, she knows Victor isn’t actually going to read the whole phone book.

The goal

The answer to this turns out be low-degree testing. Victor will spot-check the table of values of $P$ (which is supposed to be a polynomial), and test whether the values “look like a polynomial”.

For example, in the case where $|\mathbb{H}| = 2$ we described earlier, there is a promise that $P$ is supposed a multilinear polynomial. For example, this means that

$$\frac58 P(100, r_2, \dots, r_n) + \frac38 P(900, r_2, \dots, r_n) = P(400, r_2, \dots, r_n)$$

should be true. If Victor randomly samples equations like this, and they all check out, he can be confident that $P$ is probably “mostly” a polynomial.

I say “mostly” because, well, there’s no way to verify the whole phone book. By definition, Victor is trying to avoid reading. Imagine if Peggy makes a typo somewhere in the phone book — well, there’s no way to notice it, because that entry will never see daylight. However, Victor also doesn’t care about occasional typos in the phone book. For his purposes, he just wants to check the phone book is 99\% accurate, since the sum-check protocol only needs to read a few entries anyhow.

The procedure — the line-versus-point test

This is now a self-contained math problem, so I’ll just write the statement and not prove it (the proof is quite difficult). Suppose $g \colon \mathbb{F}_q^m \to \mathbb{F}_q$ is a function and we want to see whether or not it’s a polynomial of total degree at most $d$.

The procedure goes as follows. The prover prints out two additional posters containing large tables $B_0$ and $B_1$, whose contents are defined as follows:

• In the table $B_0$, for each point $\vec b \in \mathbb{F}_q^m$, the prover writes $g(\vec b) \in \mathbb{F}_q$. We denote the entry of the table by $B_0[\vec b]$.

• In the table $B_1$, for each line

  $$\left\{ \vec b + t \vec m \mid t \in \mathbb{F}_q \right\}.$$

  the prover writes the restriction of $g$ to the line $\ell$, which is a single-variable polynomial of degree at most $d$ in $\mathbb{F}_q [t]$. We denote the entry of the table by $B_1[\ell]$.

The verifier then does the obvious thing: pick a random point $\vec b$, a random line $\ell$ through it, and check the tables $B_0$ and $B_1$ are consistent.

This simple test turns out to be good enough, though proving this is hard and requires a lot of math. But the statement of the theorem is simple:

---

Theorem (The line-versus-point test):

There are absolute constants $C, D$ such that:

Let $d \ge 1$ be an integer. Suppose the tables $B_0$ and $B_1$ pass the line-versus-point test with probability at least $1 - \varepsilon > 1 - D$.

Then there in fact does exist a polynomial $P \in \mathbb{F}_q^m \to \mathbb{F}_q$ of degree at most $d$, such that

• At least $1 - C \varepsilon$ fraction of the entries of the table $B_0$ satisfy $B_0[\vec b] = P(\vec b)$
• At least $1 - C \varepsilon$ fraction of the entries of the table $B_1$ satisfy $B_1[\ell] = P|_\ell$.

---

So to check the tables, Victor just has to run the line-versus-point test a large number of times – say $N$. Take $\varepsilon$ so small that $C \varepsilon < 1 / 100$. Then either the table agrees with some polynomial $P$ at 99\% of values, or a single iteration of the line-versus-point test will fail with probability $\varepsilon$. Now take $N$ so large that $(1 - \varepsilon)^N < 1/100$. If there is no polynomial $P$ – if Peggy is cheating – then running the line-versus-point test $N$ times will catch Peggy with probability 99\%.