English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the relationship between the underlying structure of posets and thespectral and combinatorial properties of their higher-order random walks. Whilefast mixing of random walks on hypergraphs has led to myriad breakthroughsthroughout theoretical computer science in the last five years, many otherimportant applications (e.g. locally testable codes, 2-2 games) rely on themore general non-simplicial structures. These works make it clear that theglobal expansion properties of posets depend strongly on their underlyingarchitecture (e.g. simplicial, cubical, linear algebraic), but the overallphenomenon remains poorly understood. In this work, we quantify the advantageof different architectures, highlighting how structural regularity controls thespectral 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 numberof approximate eigenvalues controlled by the poset's regularity. This gives asimple condition to identify architectures (e.g. the Grassmann) that exhibitfast (exponential) decay of eigenvalues, versus architectures like hypergraphswith slow (linear) decay -- a crucial distinction in applications to hardnessof approximation and agreement testing such as the recent proof of the 2-2Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead toa tight variance-based characterization of edge-expansion on eposetsgeneralizing (Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay specialattention to the case of the Grassmann where we show our results are tight fora natural set of sparsifications of the Grassmann graphs. We note for claritythat our results do not recover the characterization used in the proof of the2-2 Games Conjecture which relies on $\ell_\infty$ rather than$\ell_2$-structure.

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets