#### Milestone Year

### 2006

#### PCP: Gradual gap amplification

A central result in complexity theory states that proofs can be
transformed into a redundant form that allows probabilistic
verification based on probing the alleged proof at a constant number
of locations (independently of the length of the assertion being proved).
This result is knows as the PCP Theorem (see PCP ),
and its original proof was very complicated and non-intuitive.

A WIS scientist found an alternative proof of the PCP Theorem.
The alternative proof uses a quantified version of the PCP Theorem,
in which parameter is the gap between the error probability
of the proof systems and 1.

The PCP Theorem refers to a proof system in which the value of the gap
is a constant (say, 1/2), whereas it is very easy to construct a proof
system in which the gap is inversely proportional to the length
of the assertion. Hence, the PCP Theorem asserts that proof systems
with such a small gap can be transformed into proof systems
with a constant gap.

The alternative proof of the PCP Theorem consists of an iterative
process in which the gap is amplified until reaching a constant value.
In each iteration, the gap is increased by a factor of two,
and this increase is obtained in a very intuitive manner.