Completed
PCP Theorem [...,ALMSS92,...]
Class Central Classrooms beta
YouTube videos 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