论文标题
独特的邻居状扩展和与群体无关的宇宙扩张
Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion
论文作者
论文摘要
近年来，已经发现高维扩展器在理论计算机科学中具有多种应用，例如有效的CSP近似，改进的采样和列表解码算法等。在其中，一个重要的高维膨胀概念是\ emph {cesyStolot膨胀}，它在构建有效解码的量子代码以及证明CSP的下限时发现了应用程序。 在一个组上，将变量和方程对应于复合物的面上的方程系统，考虑了宇宙扩展。先前研究的宇宙扩展的作品是针对特定组$ \ mathbb {f} _2 $量身定制的。特别是Kaufman，Kazhdan和Lubotzky（Focs 2014）以及Evra and Kaufman（Stoc 2016）在他们的突破性作品中，他们解决了Gromov的著名公开问题，研究了一个我们称为“ Parity”的概念，“ Parity”的扩展为小型小组。他们表明，一小部分$ k $ faces具有成比例的许多$（k+1）$ - 包含\ emph {一个奇数} $ k $ faces的面孔。小型集合的均衡扩展可用于暗示仅在$ \ mathbb {f} _2 $上方的宇宙扩展。 在这项工作中，我们引入了一个更强的\ emph {unique-neighborlike}扩展小型套件。我们表明，一小部分$ k $ - faces具有成比例的许多$（k+1）$ - 来自集合中包含\ emph {恰好一个} $ k $ face的面孔。这个概念在根本上比平价扩展更强大，因此先前的作品不能暗示。 然后，我们展示了这项工作中介绍的新的独特邻居状扩展概念，可以使界流扩展可以\ emph {group-intepentent}，即，对于小集的独特 - 尼克堡样膨胀，暗示着宇宙界的扩张，这意味着cesiystolic膨胀\ emph \ emph \ emph {coble nothy compl}}。
In recent years, high dimensional expanders have been found to have a variety of applications in theoretical computer science, such as efficient CSPs approximations, improved sampling and list-decoding algorithms, and more. Within that, an important high dimensional expansion notion is \emph{cosystolic expansion}, which has found applications in the construction of efficiently decodable quantum codes and in proving lower bounds for CSPs. Cosystolic expansion is considered with systems of equations over a group where the variables and equations correspond to faces of the complex. Previous works that studied cosystolic expansion were tailored to the specific group $\mathbb{F}_2$. In particular, Kaufman, Kazhdan and Lubotzky (FOCS 2014), and Evra and Kaufman (STOC 2016) in their breakthrough works, who solved a famous open question of Gromov, have studied a notion which we term ``parity'' expansion for small sets. They showed that small sets of $k$-faces have proportionally many $(k+1)$-faces that contain \emph{an odd number} of $k$-faces from the set. Parity expansion for small sets could be used to imply cosystolic expansion only over $\mathbb{F}_2$. In this work we introduce a stronger \emph{unique-neighbor-like} expansion for small sets. We show that small sets of $k$-faces have proportionally many $(k+1)$-faces that contain \emph{exactly one} $k$-face from the set. This notion is fundamentally stronger than parity expansion and cannot be implied by previous works. We then show, utilizing the new unique-neighbor-like expansion notion introduced in this work, that cosystolic expansion can be made \emph{group-independent}, i.e., unique-neighbor-like expansion for small sets implies cosystolic expansion \emph{over any group}.
