论文标题
高维随机步行的细粒度分析
Fine Grained Analysis of High Dimensional Random Walks
论文作者
论文摘要
高维扩展器最重要的特性之一是高维随机步行迅速收敛。事实证明，该属性在计算机科学理论的各个领域中非常有用，从协议测试到抽样，编码理论等等。 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 {结构化}〜\ cite {dblp：journals/corr/corr/abs-2001-02827}结果的版本。尽管以前的作品在最糟糕的特征值的角度检查了扩展，但在这项工作中，我们使用函数的结构将函数的扩展与随机步行操作员的整个频谱联系起来。我们称这样的定理为细粒度的高阶随机行走定理。在足够结构化的情况下，我们在这里提出的细性结果可能比最坏的情况要好得多，而在最坏的情况下，我们的结果等同于〜\ cite {dblp：journals/journals/corr/corr/corr/corr/abs-2001-2001-02827}。 为了证明细粒度的高阶随机步行定理，我们引入了一种方法，以使复杂的顶点的随机步行扩展到对高阶随机步行的细性理解中，但前提是扩展足够好。 此外，我们的\ emph {single}引导定理可以同时产生我们的细粒度高阶随机行走定理以及众所周知的滴滴定理。在这项工作之前，从不同的证明方法获得了高阶随机行走定理和欺骗定理。
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.
