Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
复制标题
DOI：
10.48550/arxiv.2205.00644
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
J. Gaitonde;Max Hopkins;T. Kaufman;Shachar Lovett;Ruizhe Zhang
中科院分区：
文献类型：
--
作者：
J. Gaitonde;Max Hopkins;T. Kaufman;Shachar Lovett;Ruizhe Zhang
研究偏序集的基本结构与其高阶随机游动的谱性质和组合性质之间的关系。在过去的五年里，超图上随机游走的快速混合导致了整个理论计算机科学的无数突破，许多其他重要的应用（例如局部可测试代码，2 - 2游戏）依赖于更一般的非单纯结构。这些工作清楚地表明，偏序集的全局扩展性质强烈依赖于它们的底层结构（例如单纯，三次，线性代数），但整体现象仍然知之甚少。在这项工作中，我们量化了不同架构的优势，突出了结构规律性如何控制相应随机游动的谱衰减和边扩展。特别地，我们展示了扩展偏序集上的行走谱（Dikstein，Dinur，Filmus，Harsha RANDOM 2018）集中在由偏序集的正则性控制的少量近似特征值周围的条带中。这给出了一个简单的条件来识别表现出特征值快速（指数）衰减的架构（例如格拉斯曼），而不是像超图这样具有缓慢（线性）衰减的架构-这是应用于近似和一致性测试硬度的关键区别，例如最近证明的2 - 2游戏猜想（Khot，Minzer，Safra FOCS 2018）。我们表明，这些结果导致了eposets广义上边扩展的基于方差的严格特征（Bafna、霍普金斯、考夫曼和洛维特（SODA 2022）），并特别注意格拉斯曼的情况，我们表明我们的结果对于格拉斯曼图的一组自然稀疏化来说是严格的。为了清楚起见，我们注意到我们的结果没有恢复2 - 2博弈猜想的证明中使用的特征，该猜想依赖于$\ell_\infty $而不是$\ell_2 $-结构。
We study the relationship between the underlying structure of posets and the spectral and combinatorial properties of their higher-order random walks. While fast mixing of random walks on hypergraphs has led to myriad breakthroughs throughout theoretical computer science in the last five years, many other important applications (e.g. locally testable codes, 2-2 games) rely on the more general non-simplicial structures. These works make it clear that the global expansion properties of posets depend strongly on their underlying architecture (e.g. simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different architectures, highlighting how structural regularity controls the spectral decay and edge-expansion of corresponding random walks. In particular, we show the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the poset's regularity. This gives a simple condition to identify architectures (e.g. the Grassmann) that exhibit fast (exponential) decay of eigenvalues, versus architectures like hypergraphs with slow (linear) decay -- a crucial distinction in applications to hardness of approximation and agreement testing such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight variance-based characterization of edge-expansion on eposets generalizing (Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization used in the proof of the 2-2 Games Conjecture which relies on $\ell_\infty$ rather than $\ell_2$-structure.