Local Proofs Approaching the Witness Length

Explore the latest advancements in Probabilistically Checkable Proofs (PCPs) and Interactive Oracle Proofs in this 27-minute IEEE conference talk. Delve into the PCP Theorem, short PCPs, and the state of the art in the field. Examine the main results, including a revisit of PCP length and achieving O(1) query complexity. Investigate key concepts such as multiplication codes, tensor codes, and high-rate tensor codes. Gain insights from speakers Noga Ron-Zewi and Ron Rothblum as they discuss motivations, warmup examples like 3SAT, and conclude with a summary and open problems in this cutting-edge area of theoretical computer science.

Probabilistically Checkable Proofs (PCPs)
PCP: Definition
PCP Theorem [...,ALMSS92,...]
Short PCPs: State of the Art
Interactive Oracle Proofs BCS16, RRR16
Interactive Oracle Proofs - Motivation
Main Result 1
PCP Length - Revisited
Warmup: 3SAT
Multiplication Codes
Tensor Codes
High Rate Tensor Code
Achieving 0(1) Query Complexity
Summary
Open Problems