Ideals, Macaulay Bases, and PCPs

All known proofs of the PCP theorem rely on multiple ”composition” steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. Algebraic proofs, starting with the work of Arora, Lund, Motwani, Sudan, and Szegedy use at least 2 such composition steps, whereas the ”Gap amplification” proof of Dinur uses Θ(logn) such composition steps. In this work, we present the first PCP construction using just one composition step. The key ingredient, missing in previous work and finally supplied in this paper, is a basic PCP (of Proximity) of size 2nε, for any ε > 0, that makes Oε(1) queries. At the core of our new construction is a new class of alternatives to ”sum-check” protocols. As used in past PCPs, these provide a method by which to verify that an m-variate degree d polynomial P evaluates to zero at every point of some set S ⊆ Fqm. Previous works had shown how to check this condition for sets of the form S = Hm using O(m) queries with alphabet Fqd assuming d ≥ |H|. Our work improves this basic protocol in two ways: First we extend it to broader classes of sets S (ones closer to Hamming balls rather than cubes). Second, it reduces the number of queries from O(m) to an absolute constant for the settings of S we consider. Specifically when S = (0,1≤ 1m/c)c, where T = 0,1≤ ba ⊆ Fqa denotes the set of Boolean vectors of Hamming weight at most b in Fqa, we give such an alternate to the sum-check protocol with O(1) queries with alphabet FqO(c+d), using proofs of size qO(m2/c). Our new protocols use the notion of Macaulay bases to extend previously known protocols to these new settings with surprising ease. In doing so, they highlight why these notions from algebra may be of further use in complexity theory.