One of the most important properties of high dimensional expanders is that high dimensional random walks converge rapidly. This property has proven to be extremely useful in variety of fields in the theory of computer science from agreement testing to sampling, coding theory and more. In this paper we present a state of the art result in a line of works analyzing the convergence of high dimensional random walks~\cite{DBLP:conf/innovations/KaufmanM17,DBLP:conf/focs/DinurK17, DBLP:conf/approx/KaufmanO18,DBLP:journals/corr/abs-2001-02827}, by presenting a \emph{structured} version of the result of~\cite{DBLP:journals/corr/abs-2001-02827}. While previous works examined the expansion in the viewpoint of the worst possible eigenvalue, in this work we relate the expansion of a function to the entire spectrum of the random walk operator using the structure of the function; We call such a theorem a Fine Grained High Order Random Walk Theorem. In sufficiently structured cases the fine grained result that we present here can be much better than the worst case while in the worst case our result is equivalent to~\cite{DBLP:journals/corr/abs-2001-02827}. In order to prove the Fine Grained High Order Random Walk Theorem we introduce a way to bootstrap the expansion of random walks on the vertices of a complex into a fine grained understanding of higher order random walks, provided that the expansion is good enough. In addition, our \emph{single} bootstrapping theorem can simultaneously yield our Fine Grained High Order Random Walk Theorem as well as the well known Trickling down Theorem. Prior to this work, High order Random walks theorems and Tricking down Theorem have been obtained from different proof methods.
翻译:高维扩展器的最重要特性之一是高维随机行走 快速交汇 。 此属性已证明在计算机科学理论的各个领域非常有用, 从协议测试到取样、 编码理论等等 。 在本文中, 我们展示了一种高级随机行走的同步结果 {DBLP:conf/ inturations/ KaufmanM17, DBLP: conf/focs/ DinurK17, DBLP: comp/ approx/ KaufmanO18, DBLP: 日记/ corr/ abs- 2001-02827} 。 在分析高维随机随机随机随机行行行走的趋同 。 在本次工作中, 我们将已知的功能扩展与随机行情的全局联系起来 。 在最坏的行距行距行距行距上, 最坏的行距行距行距比 最坏的行走法 。