Reducing the number of phone books in PCP (smart random linear combinations)

(Ingredient 5 of 5 in the PCP overview.)

We saw in our toy PCP protocol that we can combine all the $E$ equations from Quad-SAT into a single one by taking a random linear combination. Our goal is to improve this by taking a “random-looking” combination that still has the same property an assignment failing even one of the $E$ equations is going to fail the collated equation with probability close to $1$.

It turns out there is actually a well-developed theory of how to take the “random-looking” linear combination, and it comes from the study of error-correcting codes. We will use this to show that if $q \ge O(E)$ is large enough, one can do this with only $O(E)$ combinations. That’s much better than the $q^E$ we had before.

The construction here comes from Reed–Solomon codes, which are based on the simple fact that a (one-variable) polynomial of degree at most $d$ is determined by its values at $d$ points. So if I tell you the values at more than $d$ points, there is guaranteed to be some redundancy between them.

Linear combinations from polynomials

Again, let’s suppose we have $E$ quadratic equations $\mathcal{E}_1, \dots, \mathcal{E}_E$ in $N$ variables. Actually, each $\mathcal{E}_i$ is a quadratic function of $N$ variables, and the equations say that $\mathcal{E}_i = 0$ for every $i$.

Consider the linear combinations

$$\mathcal{L}_k = k \mathcal{E}_1 + k^2 \mathcal{E}_2 + \dots + k^E \mathcal{E}_E,$$

for $k = 1, 2, \dots, 100E$. (A note for the experts: We can take any $100E$ distinct values for $k$ – the specific values don’t matter. So if $q < 100E$, we can go up to a larger finite field $\mathbb{F}_{q^r}$ that contains $\mathbb{F}_q$, and choose $100E$ values of $k \in \mathbb{F}_{q^r}$.)

If you look at it as a function of $k$, the linear combination $\mathcal{L}_k$ is a polynomial of degree (at most) $E$. Since a nonzero polynomial of degree $E$ has at most $E$ roots, one of the following two things has to happen.

• Either all the $\mathcal{E}_i$’s are zero (so the system is satisfied),
• or at least 99% of the $\mathcal{L}_k$’s are nonzero.

Now we can cut the $q^E$ phone books down to $100E$ phone books, one for each value of $k$. The verifier chooses a $k$ at random, finds the phone book with $k$ on its cover, and then the protocol proceeds as before.