Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-182 | 16th November 2025 16:03

Proving the PCP Theorem with 1.5 proof compositions (or yet another PCP construction)

RSS-Feed




TR25-182
Authors: Oded Goldreich
Publication: 16th November 2025 16:04
Downloads: 85
Keywords: 


Abstract:

The original proof of the PCP Theorem composes a Reed-Muller-based PCP with itself, and then composes the resulting PCP with a Hadamard-based PCP [Arora, Lund, Motwani, Sudan and Szegedy ({\em JACM}, 1998)].
Hence, that proof applies a (general) proof composition result twice.
(Dinur's alternative proof consists of logarithmically many gap amplification steps, where each step includes an operation akin to proof composition.)

A recent work of Amireddy, Behera, Srinivasan, Sudan, and Willumsgaard ({\em ECCC}, TR25-165) presents a new PCP system such that composing the RM-based PCP with the new PCP yields a new proof of the PCP Theorem.
Essentially, for every $\alpha>0$, they present a (direct) PCP of constant query complexity and randomness complexity $n^\alpha$, where $n$ denotes the length of the input.
(In contrast, recall that the Hadamard-based PCP has quadratic randomness complexity.)
We note that their construction has other merits, beyond the fact that it does not use composition.

Here we present a different PCP system of constant query complexity and randomness $n^\alpha$.
Essentially, we use the RM-based PCP, but with a constant number of dimensions and a large alphabet (equiv., $O(1/\alpha)$-variate polynomials over a field of size $n^{O(\alpha)}$).
We then encode the field elements by the Hadamard code and incorporate a tester akin to the verifier used in the Hadamard-based PCP.
Whether or not this counts as composition is debatable (and this is reflected in the current title), but for sure this is a non-generic composition that does not involve a preparatory parallelization step.



ISSN 1433-8092 | Imprint