Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-091 | 29th June 2021 10:15

Expander Random Walks: The General Case and Limitations


Authors: Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
Publication: 29th June 2021 10:19
Downloads: 1219


Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ 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 $\mathbf{AC}^0$ 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 $\mathbf{AC}^0$. In fact, we prove that the bound obtained by [CPTS'21] for $\mathbf{AC}^0$ circuits is optimal up to a polynomial factor.

ISSN 1433-8092 | Imprint