Document Open Access Logo

Near-Optimal Cayley Expanders for Abelian Groups

Authors Akhil Jalan, Dana Moshkovitz

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.24.pdf
  • Filesize: 0.74 MB
  • 23 pages

Document Identifiers

Author Details

Akhil Jalan
  • Department of Computer Science, University of Texas at Austin, TX, USA
Dana Moshkovitz
  • Department of Computer Science, University of Texas at Austin, TX, USA

Funding

This material is based upon work supported by the National Science Foundation under grants number 1218547 and 1678712.

Cite AsGet BibTex

Akhil Jalan and Dana Moshkovitz. Near-Optimal Cayley Expanders for Abelian Groups. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.24

Abstract

We give an efficient deterministic algorithm that outputs an expanding generating set for any finite abelian group. The size of the generating set is close to the randomized construction of Alon and Roichman [Alon and Roichman, 1994], improving upon various deterministic constructions in both the dependence on the dimension and the spectral gap. By obtaining optimal dependence on the dimension we resolve a conjecture of Azar, Motwani, and Naor [Azar et al., 1998] in the affirmative. Our technique is an extension of the bias amplification technique of Ta-Shma [Ta-Shma, 2017], who used random walks on expanders to obtain expanding generating sets over the additive group of 𝔽₂ⁿ. As a consequence, we obtain (i) randomness-efficient constructions of almost k-wise independent variables, (ii) a faster deterministic algorithm for the Remote Point Problem, (iii) randomness-efficient low-degree tests, and (iv) randomness-efficient verification of matrix multiplication.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Error-correcting codes
Keywords
  • Cayley graphs
  • Expander walks
  • Epsilon-biased sets
  • Derandomization

Metrics

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

Related Versions

References

  1. Miklós Ajtai, Henryk Iwaniec, János Komlós, János Pintz, and Endre Szemerédi. Construction of a thin set with small Fourier coefficients. Bull. London Math. Soc., 22(6):583-590, 1990. URL: https://doi.org/10.1112/blms/22.6.583.
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539. SIAM, 2021. Google Scholar
  3. Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. Google Scholar
  4. Noga Alon. Explicit expanders of every degree and size. Combinatorica, pages 1-17, 2021. Google Scholar
  5. Noga Alon and Gil Cohen. On rigid matrices and u-polynomials. In 2013 IEEE Conference on Computational Complexity, pages 197-206. IEEE, 2013. Google Scholar
  6. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289-304, 1992. Google Scholar
  7. Noga Alon and Yishay Mansour. ε-discrepancy sets and their application for interpolation of sparse polynomials. Inform. Process. Lett., 54(6):337-342, 1995. URL: https://doi.org/10.1016/0020-0190(95)00032-8.
  8. Noga Alon, Rina Panigrahy, and Sergey Yekhanin. Deterministic approximation algorithms for the nearest codeword problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 339-351. Springer, 2009. Google Scholar
  9. Noga Alon and Yuval Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271-284, 1994. URL: https://doi.org/10.1002/rsa.3240050203.
  10. Andris Ambainis and Joseph Emerson. Quantum t-designs: t-wise independence in the quantum world. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pages 129-140. IEEE, 2007. Google Scholar
  11. V. Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, and Yadu Vasudev. Expanding generating sets for solvable permutation groups. SIAM J. Discrete Math., 32(3):1721-1740, 2018. URL: https://doi.org/10.1137/17M1148979.
  12. V. Arvind and Srikanth Srinivasan. The remote point problem, small bias spaces, and expanding generator sets. In STACS 2010: 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of LIPIcs. Leibniz Int. Proc. Inform., pages 59-70. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2010. Google Scholar
  13. Vikraman Arvind, Partha Mukhopadhyay, and Prajakta Nimbhorkar. Erdős-rényi sequences and deterministic construction of expanding cayley graphs. In Latin American Symposium on Theoretical Informatics, pages 37-48. Springer, 2012. Google Scholar
  14. Yossi Azar, Rajeev Motwani, and Joseph Naor. Approximating probability distributions using small sample spaces. Combinatorica, 18(2):151-171, 1998. URL: https://doi.org/10.1007/PL00009813.
  15. Eric Bach and Jonathan Sorenson. Explicit bounds for primes in residue classes. Mathematics of Computation, 65(216):1717-1735, 1996. Google Scholar
  16. Avraham Ben-Aroya and Amnon Ta-Shma. A combinatorial construction of almost-ramanujan graphs using the zig-zag product. SIAM Journal on Computing, 40(2):267-290, 2011. Google Scholar
  17. Avraham Ben-Aroya and Amnon Ta-Shma. Constructing small-bias sets from algebraic-geometric codes. Theory Comput., 9:253-272, 2013. URL: https://doi.org/10.4086/toc.2013.v009a005.
  18. Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pages 612-621. ACM, New York, 2003. URL: https://doi.org/10.1145/780542.780631.
  19. Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal. Rigid matrices from rectangular pcps or: Hard claims have complex proofs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 858-869. IEEE, 2020. Google Scholar
  20. Emmanuel Breuillard and Alexander Lubotzky. Expansion in simple groups. arXiv preprint, 2018. URL: http://arxiv.org/abs/1807.03879.
  21. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms, 5(3):Art. 32, 14, 2009. URL: https://doi.org/10.1145/1541885.1541893.
  22. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom generators from polarizing random walks. Theory Comput., 15:Paper No. 10, 26, 2019. URL: https://doi.org/10.4086/toc.2019.v015a010.
  23. Sixia Chen, Cristopher Moore, and Alexander Russell. Small-bias sets for nonabelian groups: derandomizations of the Alon-Roichman theorem. In Approximation, randomization, and combinatorial optimization, volume 8096 of Lecture Notes in Comput. Sci., pages 436-451. Springer, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_31.
  24. Tobias Christiani and Rasmus Pagh. Generating k-independent variables in constant time. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 196-205. IEEE, 2014. Google Scholar
  25. Gil Cohen, Noam Peri, and Amnon Ta-Shma. Expander random walks: A fourier-analytic approach. In Electron. Colloquium Comput. Complex, volume 27, page 6, 2020. Google Scholar
  26. Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Veličković. Efficient approximation of product distributions. Random Structures Algorithms, 13(1):1-16, 1998. URL: https://doi.org/10.1002/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W.
  27. Rusins Freivalds. Probabilistic machines can use less running time. In IFIP congress, volume 839, page 842, 1977. Google Scholar
  28. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  29. Akhil Jalan and Dana Moshkovitz. Near-optimal cayley expanders for abelian groups. arXiv preprint, 2021. URL: http://arxiv.org/abs/2105.01149.
  30. Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani. Unique decoding of explicit epsilon-balanced codes near the gilbert-varshamov bound. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 434-445. IEEE, 2020. Google Scholar
  31. Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18(5):652-656, 1972. Google Scholar
  32. Nicholas M. Katz. An estimate for character sums. J. Amer. Math. Soc., 2(2):197-200, 1989. URL: https://doi.org/10.2307/1990974.
  33. Ivan Korec and Jiří Wiedermann. Deterministic verification of integer matrix multiplication in quadratic time. In International Conference on Current Trends in Theory and Practice of Informatics, pages 375-382. Springer, 2014. Google Scholar
  34. Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988. Google Scholar
  35. Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput., 22(4):838-856, 1993. URL: https://doi.org/10.1137/0222053.
  36. A. Razborov, E. Szemerédi, and A. Wigderson. Constructing small sets that are uniform in arithmetic progressions. Combin. Probab. Comput., 2(4):513-518, 1993. URL: https://doi.org/10.1017/S0963548300000870.
  37. 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
  38. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  39. Amir Shpilka and Avi Wigderson. Derandomizing homomorphism testing in general groups. SIAM Journal on Computing, 36(4):1215-1230, 2006. Google Scholar
  40. 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.
  41. Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In TR 17-041. Electronic Colloqium on Computational Complexity, 2017. Google Scholar
  42. Salil Vadhan. Pseudorandomness, volume 7. Now Delft, 2012. Google Scholar
  43. Leslie G Valiant. Graph-theoretic arguments in low-level complexity. In International Symposium on Mathematical Foundations of Computer Science, pages 162-176. Springer, 1977. Google Scholar
  44. Avi Wigderson and David Xiao. Derandomizing the ahlswede-winter matrix-valued chernoff bound using pessimistic estimators, and applications. Theory of Computing, 4(1):53-76, 2008. Google Scholar
  45. Triantafyllos Xylouris. Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, volume 404 of Bonner Mathematische Schriften [Bonn Mathematical Publications]. Universität Bonn, Mathematisches Institut, Bonn, 2011. Dissertation for the degree of Doctor of Mathematics and Natural Sciences at the University of Bonn, Bonn, 2011. Google Scholar
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