Low-soundness direct-product testers and PCPs from Kaufman–Oppenheim complexes
Ryan O'Donnell and Noah G. Singer
我们研究考夫曼-奥本海姆式复合体(STOC 2018,Eur。 J。 梳。 2023年),具有基本和强烈的明确描述。 在回答考夫曼、奥本海姆和温伯格(STOC 2025)的公开问题时,我们表明他们支持低声条件下稀疏的直接产品测试仪。 我们的证明依赖于Bafna-Minzer和Dikstein-Dinur(均为STOC 2024)协议测试的HDX表征,这是Kaufman等人的最新结果,并遵循Bafna-Lifshitz-Minzer和Dikstein-Dinur-Lbotzky(均为FOCS 2024)的技术。 最终,任务减少到显示KO复合体的某些二维子组的维度无关的共聚扩展;遵循考夫曼和奥本海姆的“Dehn方法”(ICALP 2021),我们通过在多项式环上为某些矩阵组建立高效的演示边界来做到这一点。 正如Bafna,Minzer和Vyas(STOC 2025)所示,我们的直接产品测试结果的结果是,考夫曼-奥本海姆复合物也可用于获得具有任意小常数和准线性长度的五氯苯酚。 因此,在构建这些五氯苯酚时可以使用复杂的数论和代数组理论工具。
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–Lifshit...