Fooling Boolean functions with expander random walks



Friday, 16 July 2021, 17:15 to 18:15


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 :