Expander graphs are sparse but highly connected graphs, which find a variety of uses in CS. If the vertices of an expander are labelled by 0 or 1, a $t$-step walk gives a $t$-bit string. Cohen, Peri and Ta-Shma (2020) consider the question: can a Boolean function on $t$ variables distinguish between a truly random $t$-bit string and a $t$-step walk in a labelled expander? We will see that Majority and other symmetric functions can indeed be fooled by a walk. However, the "fooling" does not seem to improve with $t$; we will see a counterexample from a subsequent paper if time allows.
Zoom link : https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
