
Direct Product Testers and PCPs from Coset Complexes
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.