#### Milestone Year

### 1995

#### The Effect of Parallel Repetition (on games of partial information)

A puzzling question regarding two-prover interactive proofs (see PCP)
is whether their error can be decreased by parallel repetition.
The question may be cast as referring to the success probability
of two-party games in which each party only has partial information.
One would expect the success probability in parallel executions
to decrease exponentially with the number of repetitions,
but WIS scientists demonstrated the existence of a game
that maintains the success probability when repeated twice.

WIS scientists proved that the success probability of any game
decreases exponentially with the number of repetitions, but the base
of the exponent is not the success probability of a single execution
(but rather a quantity that depends on this probability as well as
on the size of the game).

This result has been instrumental in subsequent studies of
local (and probabilistic) proof systems (PCP)
and hardness of approximation.