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 ? {0,1} cannot distinguish t independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and Szemeredi (STOC 1987) is captured by the AND test function, whereas the fundamental expander Chernoff bound due to Gillman (SICOMP 1998), Heally (Computational Complexity 2008) is about test functions indicating whether the weight is close to the mean. In fact, it is known that all threshold functions are fooled by a random walk (Kipnis and Varadhan, Communications in Mathematical Physics 1986). Recently, it was shown that even the highly sensitive PARITY function is fooled by a random walk Ta-Shma (STOC 2017). We focus on balanced labels. Our first main result is proving that all symmetric functions are fooled by a random walk. Put differently, we prove a central limit theorem (CLT) for expander random walks with respect to the total variation distance, significantly strengthening the classic CLT for Markov Chains that is established with respect to the Kolmogorov distance (Kipnis and Varadhan, Communications in Mathematical Physics 1986). Our approach significantly deviates from prior works. We first study how well a Fourier character ?S is fooled by a random walk as a function of S. Then, given a test function f, we expand f in the Fourier basis and combine the above with known results on the Fourier spectrum of f. We also proceed further and consider general test functions - not necessarily symmetric. As our approach is Fourier analytic, it is general enough to analyze such versatile test functions. For our second result, we prove that random walks on sufficiently good expander graphs fool tests functions computed by AC0 circuits, read-once branching programs, and functions with bounded query complexity.

שפה מקוריתאנגלית
כותר פרסום המארחSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
עורכיםSamir Khuller, Virginia Vassilevska Williams
עמודים1643-1655
מספר עמודים13
מסת"ב (אלקטרוני)9781450380539
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 15 יוני 2021
אירוע53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, איטליה
משך הזמן: 21 יוני 202125 יוני 2021

סדרות פרסומים

שםProceedings of the Annual ACM Symposium on Theory of Computing

כנס

כנס53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
מדינה/אזוראיטליה
עירVirtual, Online
תקופה21/06/2125/06/21

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Expander random walks: A Fourier-analytic approach'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי