论文标题
posets上的特征性，光谱衰减和边缘膨胀
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
论文作者
论文摘要
我们研究了POSET的潜在结构与它们高阶随机步行的光谱和组合性质之间的关系。在过去五年中，在超图上随机步行的快速混合导致整个理论计算机科学的突破，但许多其他重要应用（例如，本地测试的代码，2-2场游戏）依赖于更一般的非吸烟结构。这些作品清楚地表明，POSET的全球扩展特性在很大程度上取决于它们的基本结构（例如，简单，立方体，线性代数），但总体现象仍然很熟悉。在这项工作中，我们量化了不同体系结构的优势，突出了结构规则性如何控制相应随机步行的光谱衰减和边缘扩张。 特别是，我们展示了扩大波动板（Dikstein，dinur，Filmus，harsha Random 2018）的步行光谱，集中在少数近似近似特征值的条形下，由Poset的规律性控制。 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).我们显示这些结果导致基于方差的Edge-expansion在Esposet上的严格表征（Bafna，Hopkins，Kaufman和Lovett（Soda 2022）），并特别注意Grassmann的案例，我们显示我们的结果很紧张，对于Grassmann图的自然而然的sparsification sear sere。为了清楚地，我们注意到我们的结果未恢复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.
