I noticed this paper when it was posted on ECCC, but got intimidated by its abstract. Fortunately, I just saw a brief review of it on the Nov'25 News column of the Property Testing Review, which I reproduce next.
This paper shows an agreement test for direct product testing with two provers in the low soundness regime. Such results were previously known using high dimensional complexes, constructed using deep facts form number theory. This paper proves that a known simpler and strongly explicit complex (KO complex) can be used instead to design the test. Although the methods are elementary, the proof is long and somewhat involved. The featured paper shows a new expansion property of KO complex in the required regime for building the test with low soundness. Additionally, this paper also confirms that their complex can be used to build an alternate efficient PCP with only poly(logn) blow up. Since the methods are elementary, it is more accessible. And, perhaps, we will have easier time to optimize the parameters to build more efficient PCPs.
[Akash; Dec 15, 2025]
Looking at the introduction of the paper, I found it quite friendly (i.e., it provides a good overview of what is going on), although it is still hard to find a concise statement of the results in abstract terms (i.e., in terms of general agreement testers and PCPs). For direct-product testers such results are stated in [BLM24, DDL24], where the PCP result is stated clearly in Thm 1.2 of [BMVY25].
We study the Kaufman--Oppenheim coset complexes (STOC 2018, Eur. J. Comb. 2023), which have an elementary and strongly explicit description. Answering an open question of Kaufman, Oppenheim, and Weinberger (STOC 2025), we show that they support sparse direct-product testers in the low soundness regime. Our proof relies on the HDX characterization of agreement testing by Bafna--Minzer and Dikstein--Dinur (both STOC 2024), the recent result of Kaufman et al., and follows techniques from Bafna--Lifshitz--Minzer and Dikstein--Dinur--Lubotzky (both FOCS 2024). Ultimately, the task reduces to showing dimension-independent coboundary expansion of certain 2-dimensional subcomplexes of the KO complex; following the ``Dehn method'' of Kaufman and Oppenheim (ICALP 2021), we do this by establishing efficient presentation bounds for certain matrix groups over polynomial rings.
As shown by Bafna, Minzer, and Vyas (STOC 2025), a consequence of our direct-product testing result is that the Kaufman--Oppenheim complexes can also be used to obtain PCPs with arbitrarily small constant soundness and quasilinear length. Thus the use of sophisticated number theory and algebraic group-theoretic tools in the construction of these PCPs can be avoided.
See ECCC TR25-180.