期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by 1. What "test" functions f:1t1 can or cannot distinguish t independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, and proved that all symmetric functions are fooled by random walks on expanders with constant spectral gap. Furthermore, it was shown that functions computable by AC0 circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question and, in particular, resolve all open problems raised by [CPTS'21]. First, we generalize the result to all labelling, not merely balanced. In doing so, we improve the known bound for symmetric functions and prove that the bound we obtain is optimal (up to a multiplicative constant). Furthermore, we prove that a random walk on expanders with constant spectral gap does not fool AC0. In fact, we prove that the bound obtained by [CPTS'21] for AC0 circuits is optimal up to a polynomial factor.
