ECCC-Report TR21-091https://eccc.weizmann.ac.il/report/2021/091Comments and Revisions published for TR21-091en-usTue, 29 Jun 2021 10:19:40 +0300
Paper TR21-091
| Expander Random Walks: The General Case and Limitations |
Gil Cohen,
Dor Minzer,
Shir Peleg,
Aaron Potechin,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2021/091Cohen, 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.Tue, 29 Jun 2021 10:19:40 +0300https://eccc.weizmann.ac.il/report/2021/091