Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Local Proofs Approaching the Witness Length

IEEE via YouTube

Overview

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.

Syllabus

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

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

Start your review of Local Proofs Approaching the Witness Length

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.