## ملخص

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

!!Conference | 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 |
---|---|

الدولة/الإقليم | إيطاليا |

المدينة | Virtual, Online |

المدة | ٢١/٠٦/٢١ → ٢٥/٠٦/٢١ |

## All Science Journal Classification (ASJC) codes

- !!Software