Completed
Probabilistically Checkable Proofs (PCPs)
Class Central Classrooms beta
YouTube playlists curated by Class Central.
Classroom Contents
Local Proofs Approaching the Witness Length
Automatically move to the next video in the Classroom when playback concludes
- 1 Probabilistically Checkable Proofs (PCPs)
- 2 PCP: Definition
- 3 PCP Theorem [...,ALMSS92,...]
- 4 Short PCPs: State of the Art
- 5 Interactive Oracle Proofs BCS16, RRR16
- 6 Interactive Oracle Proofs - Motivation
- 7 Main Result 1
- 8 PCP Length - Revisited
- 9 Warmup: 3SAT
- 10 Multiplication Codes
- 11 Tensor Codes
- 12 High Rate Tensor Code
- 13 Achieving 0(1) Query Complexity
- 14 Summary
- 15 Open Problems
