Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NOAM PERI:
All reports by Author Noam Peri:

TR20-163 | 5th November 2020
Gil Cohen, Noam Peri, Amnon Ta-Shma

Expander Random Walks: A Fourier-Analytic Approach

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>




ISSN 1433-8092 | Imprint