论文标题
显式下限，与$ω（n）$ - 一轮平价
Explicit Lower Bounds Against $Ω(n)$-Rounds of Sum-of-Squares
论文作者
论文摘要
我们以$ω（n）$的级别（SOS）半定义编程层次结构级别构建了一个3 XOR实例的显式家族。这不仅是第一个击败蛮力搜索的明确结构（超越低阶改进（Tulsiani 2021，pratt 2021））），结合标准差距扩增技术，它还与不完美的完整性（Grigorivev TCS 2001，SchoEneenebeck focs focs focs focs focs focs forces formentive tos toctiqus of and of SchoeNebect formessiques of SchoeNebecs forces formantiques formantiques of Standard Gap扩增技术''。 我们的结果是基于一种新形式的小型高维膨胀（SS-HDX），其灵感来自最新的可当地测试和量子LDPC代码的突破。将最新的Dinur，Filmus，Harsha和Tulsiani（ITCS 2021）的框架改编成从Ramanujan综合体到此环境的SOS下限，我们显示任何（有限的）SS-HDX可以转换为高度不足的3-XOR实例，无法通过$ω级别的$ω级别拒绝。然后，我们向Leverrier和Zémor's（Arxiv 2022）展示了最近的QLDPC构造提供了所需的明确家族的界限SS-HDX。顺便说一句，这给出了迄今为止的双向高维扩展的最强形式。
We construct an explicit family of 3-XOR instances hard for $Ω(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit construction to beat brute force search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined with standard gap amplification techniques it also matches the (optimal) hardness of random instances up to imperfect completeness (Grigoriev TCS 2001, Schoenebeck FOCS 2008). Our result is based on a new form of small-set high dimensional expansion (SS-HDX) inspired by recent breakthroughs in locally testable and quantum LDPC codes. Adapting the recent framework of Dinur, Filmus, Harsha, and Tulsiani (ITCS 2021) for SoS lower bounds from the Ramanujan complex to this setting, we show any (bounded-degree) SS-HDX can be transformed into a highly unsatisfiable 3-XOR instance that cannot be refuted by $Ω(n)$-levels of SoS. We then show Leverrier and Zémor's (Arxiv 2022) recent qLDPC construction gives the desired explicit family of bounded-degree SS-HDX. Incidentally, this gives the strongest known form of bi-directional high dimensional expansion to date.
