The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the
existence of proofs that can be verified by reading a very small
part of the proof. Since the discovery of the theorem, there has
been a considerable work on improving the theorem in terms...