Abstract
Proof composition is an essential ingredient of all known constructions of probabilistically checkable proofs (PCPs), first introduced by Arora and Safra in the proof of the PCP Theorem. Informally speaking, proof composition is a recursive procedure applied to PCP constructions to reduce the alphabet size. Proof
composition is applied (possibly several times over) to PCPs over the large alphabet to obtain PCPs over a small (even binary) alphabet. By now, our understanding of proof composition has considerably improved. In particular, composition of PCPs with high soundness error (greater than 1/2) is by now well understood using the notion of PCPs of proximity. To construct PCPs with low soundness error, an alternaten otion of decodable PCPs was introduced. This has led to (1) construction of nearly linear sized 2-query PCPs with subconstant error (improving over parameters that we know to obtain via parallel repetition theorem) and (2) PCPs w/ large query but sub-constant error towards resolving the sliding scale conjecture.
In this talk, I'll survey these composition techniques and the ingredients therein: PCPs of proximity, decodable PCPs and how these objects give rise to verification procedures w/ the best known tradeoffs between alphabet size and soundness error maintaining polynomial proof length.