Direct Product Testers and PCPs from Coset Complexes

Direct-product testers” are used in the design of (some) probabilistically checkable proofs (PCPs), which, in turn, play a fundamental role in modern complexity theory and cryptography. We investigate the direct-product testability of certain algebraically-defined objects, called Kaufman–Oppenheim (KO) complexes (STOC 2018, Eur. J. Comb. 2023).

Answering an open question of Kaufman–Oppenheim–Weinberger (STOC 2025), we prove that KO complexes are direct-product testers (in the low-soundness regime). This implies, by work of Bafna–Minzer–Vyas (STOC 2025), that KO complexes yield PCPs with arbitrarily small constant soundness and quasilinear length. These results were previously known for a different construction, by Chapman–Lubotzky, that used sophisticated tools from number theory and algebraic group theory; in contrast, KO complexes have an elementary and strongly explicit description. In this talk, I will fully define direct-product testing and KO complexes, and assume no background aside from basic probability and group theory.