Ideals, Macaulay Bases, and PCPs

The PCP Theorem is a central result in theoretical computer science, giving query-efficient verifiers for NP. All known proofs of the PCP Theorem rely on (multiple applications of) proof composition, where two sub-optimal PCPs are combined into an optimal one. In this work, we build improved component PCPs strong enough that only a single composition step is needed to recover the PCP Theorem. In particular, we give a new and direct construction (i.e., without composition) of a constant-query PCP with proof size 2^{n^ε} for arbitrarily small constant ε > 0, which is a regime of parameters evaded by prior constructions.

 

Our constructions are based on a new Zero-on-Variety Test for checking whether an oracle f : F^m → F is identically zero on a variety V ⊆ F^m (where F is a finite field). While previous works largely tackle this problem for the setting of V = H^m (a product set), our test applies to much more general varieties, with proof size governed by the Macaulay basis complexity of V. Instantiating this framework with two specific varieties and composing the resulting PCPs thus yields a proof of the PCP Theorem with a single composition.