The PCP theorem, a jewel of theoretical computer science, establishes that any NP statement can be assessed by a randomized verifier who only checks a vanishing fraction of the proof (indeed, a constant # of characters!)
This has had incredible impact, most notably on how ML reviews are conducted
1 year ago
155
20
7
4