The ACO Seminar (2025–2026)

“Direct-product testers” are objects used in the design of (some) probabilistically checkable proofs, which, in turn, play a fundamental role in modern complexity theory and cryptography. We gently introduce the direct-product testing problem and its relationship with expansion properties of simplicial complexes. Then, we discuss the so-called “Kaufman—Oppenheim coset complex” and our proof that it has direct-product testing properties which were previously known only for less-elementary constructions. We only assume a basic background in finite group theory (and no prior knowledge of theoretical computer science).

Based on joint work with Ryan O’Donnell.