论文标题
高维扩张器的显式SOS下限
Explicit SoS lower bounds from high-dimensional expanders
论文作者
论文摘要
我们构建了3xor实例的显式族，对于$ o（\ sqrt {\ log n}）$ quares squares层次结构的级别很难。与涉及随机组件的早期结构相反，我们的系统可以在确定性的多项式时间中明确构建。 我们的构造基于Lubotzky，Samuels和Vishne（称为LSV复合物或Ramanujan Complexses）设计的高维扩展器，我们的分析基于这些复合物的两个扩展概念：宇宙膨胀，以及由于Gromov所产生的局部等速度不平等。 我们的建筑与Alev，Jeronimo和最后一位作者〜最近的作品形成了鲜明的对比（Focs 2019）。他们表明，变量对应于高维扩展器中顶点的3xor实例很容易解决。相反，在我们的情况下，变量对应于复合物的边缘。
We construct an explicit family of 3XOR instances which is hard for $O(\sqrt{\log n})$ levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time. Our construction is based on the high-dimensional expanders devised by Lubotzky, Samuels and Vishne, known as LSV complexes or Ramanujan complexes, and our analysis is based on two notions of expansion for these complexes: cosystolic expansion, and a local isoperimetric inequality due to Gromov. Our construction offers an interesting contrast to the recent work of Alev, Jeronimo and the last author~(FOCS 2019). They showed that 3XOR instances in which the variables correspond to vertices in a high-dimensional expander are easy to solve. In contrast, in our instances the variables correspond to the edges of the complex.
