Noah Singer (Carnegie Mellon)- Agreement testers and PCPs from coset complexes

Abstract: “Agreement 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. Recent breakthrough works [Bafna–Lifshitz–Minzer, Dikstein–Dinur–Lubotzky 2024] analyzed a certain sophisticated construction and showed that it has strong agreement testing properties. In our work, we establish the same result for the so-called “Kaufman–Oppenheim (KO) complex”, an alternative construction which is more elementary, explicit, and symmetric. Ultimately, our proof boils down to a bound on the ‘complexity’, in a precise sense, of the group of upper triangular matrices with 1’s on the diagonal over a finite field.

In the talk, I will informally define the agreement testing problem and its relationship with “higher-dimensional analogues” of expander graphs, before presenting, from first principles, our bound and some ideas from its proof. Based on joint work with Ryan O’Donnell.