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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 15 يونيو 2021
الحدث53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, إيطاليا
المدة: ٢١ يونيو ٢٠٢١٢٥ يونيو ٢٠٢١

سلسلة المنشورات

الاسمProceedings of the Annual ACM Symposium on Theory of Computing

!!Conference

!!Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
الدولة/الإقليمإيطاليا
المدينةVirtual, Online
المدة٢١/٠٦/٢١٢٥/٠٦/٢١

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Expander random walks: A Fourier-analytic approach'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا