论文标题
封面的新高维扩张器
New High Dimensional Expanders from Covers
论文作者
论文摘要
我们基于覆盖简单络合物的空间的新构建高维扩展器的新结构。高维扩展器（HDXS）是扩展器图的超图类似物。它们在理论计算机科学中有很多用途，但是不幸的是，只有很少的构造是任意的局部光谱扩展。 我们给出了一种随机算法，该算法将输入作为高维扩展器$ x $（满足一些轻度假设）。它输出了一个高维扩展器的子复合物$ y \ subseteq x $，并且具有无限的许多简单盖。这些涵盖构成了有限度高维扩张器的新家族。子复合物$ y $继承$ x $的基础图，其链接是$ x $的链接的稀疏性。当$ x $的链接的大小为$ o（\ log | x |）$时，可以确定此算法。我们的算法基于Lubotzky，Samuels和Vishne（2005）发现的组和生成集，它们用于构建第一个发现的高维扩张器。我们显示这些群体引起了更多``随机''高维扩展器。 此外，我们的技术还为高维扩展器提供了随机的稀疏算法，该算法保持其局部光谱特性。这可能具有独立的利益。
We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but unfortunately only few constructions are known which have arbitrarily small local spectral expansion. We give a randomized algorithm that takes as input a high dimensional expander $X$ (satisfying some mild assumptions). It outputs a sub-complex $Y \subseteq X$ that is a high dimensional expander and has infinitely many simplicial covers. These covers form new families of bounded-degree high dimensional expanders. The sub-complex $Y$ inherits $X$'s underlying graph and its links are sparsifications of the links of $X$. When the size of the links of $X$ is $O(\log |X|)$, this algorithm can be made deterministic. Our algorithm is based on the groups and generating sets discovered by Lubotzky, Samuels and Vishne (2005), that were used to construct the first discovered high dimensional expanders. We show these groups give rise to many more ``randomized'' high dimensional expanders. In addition, our techniques also give a random sparsification algorithm for high dimensional expanders, that maintains its local spectral properties. This may be of independent interest.
