LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Direct Product Testers and PCPs from Coset Complexes
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Direct Product Testers and PCPs from Coset Complexes

77 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Noah Singer, a researcher from Carnegie Mellon University, presents this Institute for Advanced Study discrete mathematics seminar on probabilistically checkable proofs. He opens by defining direct-product testers, the tools used to check whether a function behaves consistently across tuples of inputs, and explains why they matter for building PCPs, a cornerstone of modern complexity theory and cryptography. The core result concerns Kaufman-Oppenheim complexes, algebraically defined objects first introduced in 2018, and answers an open question posed by Kaufman, Oppenheim, and Weinberger earlier in 2025 by showing these complexes are direct-product testers in the low-soundness regime. Singer connects this to work by Bafna, Minzer, and Vyas, demonstrating that the result yields PCPs with small constant soundness and quasilinear length, matching what was previously achievable only through the more complicated Chapman-Lubotzky construction built on number theory and algebraic group theory. The talk assumes only basic probability and group theory, building the definitions from scratch for a seminar audience.

At a glance

Lecture facts

Runtime compared with the other 350 Mathematics lectures
Runtime1 h 17 m
Compared with MathematicsLonger than 60%
Source channelInstitute for Advanced Study (YouTube)
QA · not live