High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
复制标题
DOI：
10.1137/1.9781611977073.47
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Mitali Bafna;Max Hopkins;T. Kaufman;Shachar Lovett
中科院分区：
文献类型：
--
作者：
Mitali Bafna;Max Hopkins;T. Kaufman;Shachar Lovett
自从 Kaufman 和 Mass [KM16] 引入以来，高维扩展器 (HDX) 上的高阶随机游走 (HD-walks) 已经得到了大量的研究和应用，但它们更广泛的组合和光谱特性仍然知之甚少。我们开发了双边局部光谱扩展器 [DK17] 上 HD 行走光谱结构的组合表征，它提供了经过充分研究的约翰逊和格拉斯曼图的广泛概括。我们的表征表明，HD-walks 的光谱紧密集中在几个组合结构条带中，从而得出新颖的结构定理，例如边缘扩展的紧密 $\ell_2$ 表征，以及对 HDX 上的局部到全局算法的新理解。对于后者，我们引入了一种称为“剥离阈值等级”的谱复杂性度量，并展示了它如何取代（大得多的）阈值等级来控制结构化对象上的算法性能。结合前一个 $\ell_2$ 表征的平方和证明，我们将该框架具体应用于 HD-walks 上独特游戏的算法，在许多情况下将最先进的技术 [RBS11，ABS15] 从近指数时间改进为多项式时间（例如，用于约翰逊图或 $q$ 元超立方体切片的稀疏化）。我们的扩展特征也与近似硬度有着有趣的联系，其中格拉斯曼图的 $\ell_\infty$ 变体最近被用来解决 2-2 Games 猜想 [KMS18]。我们从相关的 $\ell_\infty$ 变体到我们的 $\ell_2$ 表征进行了简化，但它失去了感兴趣的硬度范围中的因素，其中 $\ell_2$ 和 $\ell_\infty$ 结构之间的差距很大。尽管如此，我们还是为在近似硬度和独特游戏中使用 HDX 的进一步工作打开了大门。
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16], yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders [DK17], which offer a broad generalization of the well-studied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight $\ell_2$-characterization of edge-expansion, as well as to a new understanding of local-to-global algorithms on HDX. Towards the latter, we introduce a spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank in controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof of the former $\ell_2$-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, in many cases improving the state of the art [RBS11, ABS15] from nearly-exponential to polynomial time (e.g. for sparsifications of Johnson graphs or of slices of the $q$-ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an $\ell_\infty$-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture [KMS18]. We give a reduction from a related $\ell_\infty$-variant to our $\ell_2$-characterization, but it loses factors in the regime of interest for hardness where the gap between $\ell_2$ and $\ell_\infty$ structure is large. Nevertheless, we open the door for further work on the use of HDX in hardness of approximation and unique games.