Probabilistically checkable proofs and arguments

Proofs checked by reading a few bits, and how Merkle trees and hashing make them short.

The PCP theorem: checking a proof by reading a few bits (1992)

The PCP theorem: checking a proof by reading a few bits (1992)

Kilian’s succinct arguments: a Merkle-committed PCP (1992)

Kilian's succinct arguments: a Merkle-committed PCP (1992)

Micali’s computationally sound proofs: hashing the verifier away (1994)

Micali's computationally sound proofs: hashing the verifier away (1994)