#### Milestone Year

### 1991

#### PCP: Locally (and Probabilistically) Checkable Proofs

WIS scientists and their collaborators showed that proofs can be transformed
into a redundant form that allows probabilistic verification based
on probing the alleged proof in very few locations;
specifically, the number of probed locations
may be polylogarithmic in the length of the assertion being proved.
They also showed a connection between this model of proofs
(later termed PCPs) and the hardness of approximating some natural
combinatorial parameters (i.e., the maximum clique size in a graph).
This connection has revolutionized the study of the complexity
of approximation problems by offering a new avenue for establishing
strong intractability results.

The PCP model is closely related to another model of proof systems
that was proposed by a WIS scientist and her collaborators in 1988;
specifically, the model of multi-prover interactive proofs.

In general, WIS scientists made numerous important contributions
to the study of PCP and the hardness of approximating natural
combinatorial parameters. Notable examples include Parallel Repetition and PCP.