Document Open Access Logo

Expander Random Walks: The General Case and Limitations

Authors Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.43.pdf
  • Filesize: 0.76 MB
  • 18 pages

Document Identifiers

Author Details

Gil Cohen
  • Department of Computer Science, Tel Aviv University, Israel
Dor Minzer
  • Department of Mathematics, Massachusetts Institute of Technology, Cmabridge, MA, USA
Shir Peleg
  • Department of Computer Science, Tel Aviv University, Israel
Aaron Potechin
  • Department of Computer Science, University of Chicago, IL, USA
Amnon Ta-Shma
  • Department of Computer Science, Tel Aviv University, Israel

Funding

  • Cohen, Gil: Supported by ERC starting grant 949499 and by the Israel Science Foundation grant 1569/18.
  • Peleg, Shir: The research leading to these results has received funding from the Israel Science Foundation (grant number 514/20) and from the Len Blavatnik and the Blavatnik Family foundation.
  • Ta-Shma, Amnon: The research leading to these results has received funding from the Israel Science Foundation (grant number 952/18)

Acknowledgements

The authors thank Amir Yehudayoff for pointing out that the analysis of the error of the parity function is tight if the second eigenvector of the graph is Boolean. This remark, several years later, matured to the current paper. We thank Venkat Guruswami and Vinayak Kumar for discussing their results with us. We thank Ron Peled for discussions on the CLT in TVD, and for pointing us to results on local convergence for independent processes. We thank Oded Goldreich for the vanishing with t and λ notation.

Cite AsGet BibTex

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.43

Abstract

Cohen, Peri and Ta-Shma [Gil Cohen et al., 2021] considered the following question: Assume the vertices of an expander graph are labelled by ± 1. What "test" functions f : {±1}^t → {±1} can or cannot distinguish t independent samples from those obtained by a random walk? [Gil Cohen et al., 2021] considered only balanced labellings, and proved that for all symmetric functions the distinguishability goes down to zero with the spectral gap λ of the expander G. In addition, [Gil Cohen et al., 2021] show that functions computable by AC⁰ circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question. We generalize the result to all labelling, not merely balanced ones. We also improve the upper bound on the error of symmetric functions. More importantly, we give a matching lower bound and show a symmetric function with distinguishability going down to zero with λ but not with t. Moreover, we prove a lower bound on the error of functions in AC⁰ in particular, we prove that a random walk on expanders with constant spectral gap does not fool AC⁰.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Expander Graphs
  • Random Walks
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Miklós Ajtai, János Komlós, and Endre Szemerédi. Deterministic simulation in logspace. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 132-140, 1987. Google Scholar
  2. Noga Alon and Fan RK Chung. Explicit construction of linear sized tolerant networks. Discrete Mathematics, 72(1-3):15-19, 1988. Google Scholar
  3. Noga Alon, Jeff Edmonds, and Michael Luby. Linear time erasure codes with nearly optimal recovery. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 512-519. IEEE, 1995. Google Scholar
  4. Noga Alon and Yuval Roichman. Random cayley graphs and expanders. Random Struct. Algorithms, 5(2):271-285, 1994. URL: https://doi.org/10.1002/rsa.3240050203.
  5. Mihir Bellare, Oded Goldreich, and Shafi Goldwasser. Randomness in interactive proofs. Computational Complexity, 3(4):319-354, 1993. Google Scholar
  6. Avraham Ben-Aroya and Amnon Ta-Shma. A combinatorial construction of almost-Ramanujan graphs using the zig-zag product. SIAM J. Comput., 40(2):267-290, 2011. URL: https://doi.org/10.1137/080732651.
  7. Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica, 26(5):495-519, 2006. URL: https://doi.org/10.1007/s00493-006-0029-7.
  8. Mark Braverman. Polylogarithmic independence fools AC⁰ circuits. J. ACM, 57(5):Art. 28, 10, 2010. URL: https://doi.org/10.1145/1754399.1754401.
  9. Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM J. Comput., 49(5), 2020. URL: https://doi.org/10.1137/18M1197734.
  10. Aviad Cohen and Avi Wigderson. Dispersers, deterministic amplification, and weak random sources. In 30th Annual Symposium on Foundations of Computer Science, pages 14-19. IEEE Computer Society, 1989. Google Scholar
  11. Gil Cohen, Noam Peri, and Amnon Ta-Shma. Expander random walks: a fourier-analytic approach. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1643-1655. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451049.
  12. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):Art. 12, 44, 2007. URL: https://doi.org/10.1145/1236457.1236459.
  13. Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Locally testable codes with constant rate, distance, and locality. CoRR, abs/2111.04808, 2021. URL: http://arxiv.org/abs/2111.04808.
  14. David Gillman. A chernoff bound for random walks on expander graphs. SIAM Journal on Computing, 27(4):1203-1220, 1998. Google Scholar
  15. Venkatesan Guruswami and Vinayak M Kumar. Pseudobinomiality of the sticky random walk. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  16. Alexander D Healy. Randomness-efficient sampling within nc. Computational Complexity, 17(1):3-37, 2008. Google Scholar
  17. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439-561, 2006. URL: https://doi.org/10.1090/S0273-0979-06-01126-8.
  18. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 356-364, 1994. Google Scholar
  19. Russell Impagliazzo and David Zuckerman. How to recycle random bits. In FOCS, volume 89, pages 248-253, 1989. Google Scholar
  20. Claude Kipnis and SR Srinivasa Varadhan. Central limit theorem for additive functionals of reversible markov processes and applications to simple exclusions. Communications in Mathematical Physics, 104(1):1-19, 1986. Google Scholar
  21. Benoît Kloeckner. Effective limit theorems for Markov chains with a spectral gap. arXiv preprint, 2017. URL: http://arxiv.org/abs/1703.09623.
  22. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally correctable and locally testable codes with sub-polynomial query complexity. J. ACM, 64(2):Art. 11, 42, 2017. URL: https://doi.org/10.1145/3051093.
  23. Pascal Lezaud. Chernoff and Berry-Esséen inequalities for markov processes. ESAIM: Probability and Statistics, 5:183-201, 2001. Google Scholar
  24. Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988. Google Scholar
  25. Grigorii Aleksandrovich Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy peredachi informatsii, 24(1):51-60, 1988. Google Scholar
  26. Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. Explicit near-ramanujan graphs of every degree. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 510-523, 2020. Google Scholar
  27. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9781139814782.
  28. Ran Raz, Omer Reingold, and Salil Vadhan. Error reduction for extractors. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 191-201. IEEE, 1999. Google Scholar
  29. Omer Reingold. Undirected ST-connectivity in log-space. In STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 376-385. ACM, New York, 2005. URL: https://doi.org/10.1145/1060590.1060647.
  30. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 3-13. IEEE, 2000. Google Scholar
  31. Eyal Rozenman and Salil Vadhan. Derandomized squaring of graphs. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 436-447. Springer, 2005. Google Scholar
  32. Michael Sipser and Daniel A Spielman. Expander codes. IEEE transactions on Information Theory, 42(6):1710-1722, 1996. Google Scholar
  33. Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In STOC'17 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 238-251. ACM, New York, 2017. URL: https://doi.org/10.1145/3055399.3055408.
  34. Avishay Tal. Tight bounds on the fourier spectrum of ac0. In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  35. Luca Trevisan. Lecture notes on graph partitioning, expanders and spectral methods. University of California, Berkeley, 2017. URL: https://lucatrevisan.github.io/books/expanders-2016.pdf.
  36. Salil P Vadhan. Pseudorandomness, volume 7. Now, 2012. Google Scholar
  37. Leslie G. Valiant. Graph-theoretic properties in computational complexity. J. Comput. System Sci., 13(3):278-285, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80041-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact