Computing, IT & AI
PCP theorem and hardness of approximation
1992 CESanjeev Arora, Rajeev Motwani, Madhu Sudan, with Carsten Lund, Mario Szegedy and Shmuel SafraProof verification and the hardness of approximation problems (FOCS 1992; JACM 1998)Diaspora (work abroad)
1992
Any mathematical proof can be rewritten so that it can be checked by reading only a few randomly chosen bits.
- Dated
- 1992
- As scholars put it
- 1992 CE
- Originator
- Sanjeev Arora, Rajeev Motwani, Madhu Sudan, with Carsten Lund, Mario Szegedy and Shmuel Safra
- Source text
- Proof verification and the hardness of approximation problems (FOCS 1992; JACM 1998)
- Region
- Diaspora (work abroad)
- Discipline
- Computing, IT & AI
- Evidence
- Documented
- Confidence
- High
- Verification
- Verified-web
Background
Building on work on interactive proofs, Arora and Safra, and then Arora, Lund, Motwani, Sudan and Szegedy, proved in 1992 that every problem in NP has probabilistically checkable proofs. Three of the five authors (Arora, Motwani, Sudan) were Indian-born.
Significance
Showed that for many optimisation problems even a good approximate solution is as hard to find as an exact one, which created the field of hardness of approximation. It won the 2001 Gödel Prize.
Path to modern innovation
Underpins modern proof systems, including succinct proofs used in cryptography.
1992PCP theorem and hardness of approximationGlobal impact
- Tells algorithm designers which problems cannot be approximated efficiently.
- Ideas used in verifiable computation and zero-knowledge proof systems.
Primary sources
Further reading
Related
Corrections and additional sources: edit IND-394 on GitHub.