Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > KAUFMAN-OPPENHEIM COMPLEXES:
Reports tagged with Kaufman-Oppenheim complexes:
TR25-180 | 13th November 2025
Ryan O'Donnell, Noah Singer

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes

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 ... more >>>




ISSN 1433-8092 | Imprint