Will Cook

PCP theorem

Their work
Troy Lee wrote the proof of the PCP theorem in Lean, and a guide to reading it. His Lean follows the algebraic proof by Amireddy, Behera, Srinivasan, Sudan and Willumsgaard.
My work
With AI, I wrote three papers that explain his Lean proof: one through worked examples, one for specialists and one detailed account. In each paper, clicking a linked sentence opens the Lean lines it describes.

The PCP theorem says that any proof a computer can check quickly can be rewritten so that a checker reads only a fixed number of its bits, chosen at random. For a true claim the rewritten proof is always accepted, and every proof of a false claim is rejected at least half the time.

Limits: Lean compiled Lee’s proof. I made the three papers and their links to the Lean with AI. Neither Lee nor the authors of the algebraic proof have reviewed them, and nobody has compared each sentence with the Lean lines it links to.

Lean is a program that checks mathematical proofs.

Open the exposition

I use AI to make AI-written maths and code easier to understand.

All twenty-one projects