Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion

Authors Tali Kaufman, David Mass



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.56.pdf
  • Filesize: 0.66 MB
  • 17 pages

Document Identifiers

Author Details

Tali Kaufman
  • Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel
David Mass
  • Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel

Cite AsGet BibTex

Tali Kaufman and David Mass. Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.56

Abstract

In recent years, high dimensional expanders have been found to have a variety of applications in theoretical computer science, such as efficient CSPs approximations, improved sampling and list-decoding algorithms, and more. Within that, an important high dimensional expansion notion is cosystolic expansion, which has found applications in the construction of efficiently decodable quantum codes and in proving lower bounds for CSPs. Cosystolic expansion is considered with systems of equations over a group where the variables and equations correspond to faces of the complex. Previous works that studied cosystolic expansion were tailored to the specific group 𝔽₂. In particular, Kaufman, Kazhdan and Lubotzky (FOCS 2014), and Evra and Kaufman (STOC 2016) in their breakthrough works, who solved a famous open question of Gromov, have studied a notion which we term "parity" expansion for small sets. They showed that small sets of k-faces have proportionally many (k+1)-faces that contain an odd number of k-faces from the set. Parity expansion for small sets could then be used to imply cosystolic expansion only over 𝔽₂. In this work we introduce a stronger unique-neighbor-like expansion for small sets. We show that small sets of k-faces have proportionally many (k+1)-faces that contain exactly one k-face from the set. This notion is fundamentally stronger than parity expansion and cannot be implied by previous works. We then show, utilizing the new unique-neighbor-like expansion notion introduced in this work, that cosystolic expansion can be made group-independent, i.e., unique-neighbor-like expansion for small sets implies cosystolic expansion over any group.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • High dimensional expanders
  • Unique-neighbor-like expansion
  • Cosystolic expansion

Metrics

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

References

  1. V. L. Alev, F. G. Jeronimo, D. Quintana, S. Srivastava, and M. Tulsiani. List decoding of direct sum codes. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1412-1425. SIAM, 2020. Google Scholar
  2. V. L. Alev, F. G. Jeronimo, and M. Tulsiani. Approximating constraint satisfaction problems on high-dimensional expanders. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 180-201, 2019. Google Scholar
  3. V. L. Alev and L. C. Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1198-1211, 2020. Google Scholar
  4. N. Anari, K. Liu, and S. O. Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.00303.
  5. N. Anari, K. Liu, S. O. Gharan, and C. Vinzant. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1-12, 2019. Google Scholar
  6. Z. Chen, A. Galanis, D. Štefankovič, and E. Vigoda. Rapid mixing for colorings via spectral independence. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548-1557. SIAM, 2021. Google Scholar
  7. Z. Chen, K. Liu, and E. Vigoda. Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.02075.
  8. Z. Chen, K. Liu, and E. Vigoda. Rapid mixing of glauber dynamics up to uniqueness via contraction. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.09083.
  9. Y. Dikstein and I. Dinur. Agreement testing theorems on layered set systems. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1495-1524. IEEE, 2019. Google Scholar
  10. I. Dinur, Y. Filmus, P. Harsha, and M. Tulsiani. Explicit SoS lower bounds from high-dimensional expanders. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.05218.
  11. I. Dinur, P. Harsha, T. Kaufman, I. L. Navon, and A. Ta Shma. List decoding with double samplers. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2134-2153. SIAM, 2019. Google Scholar
  12. I. Dinur and T. Kaufman. High dimensional expanders imply agreement expanders. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 974-985, 2017. Google Scholar
  13. Irit Dinur and Roy Meshulam. Near coverings and cosystolic expansion-an example of topological property testing. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.08507.
  14. S. Evra and T. Kaufman. Bounded degree cosystolic expanders of every dimension. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 36-48, 2016. Google Scholar
  15. S. Evra, T. Kaufman, and G. Zemor. Decodable quantum LDPC codes beyond the √n distance barrier using high dimensional expanders. In 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020. to appear. Google Scholar
  16. W. Feng, H. Guo, Y. Yin, and C. Zhang. Rapid mixing from spectral independence beyond the boolean domain. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1558-1577. SIAM, 2021. Google Scholar
  17. M. Gromov. Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry. Geometric And Functional Analysis, 20(2):416-526, 2010. Google Scholar
  18. T. Kaufman, D. Kazhdan, and A. Lubotzky. Ramanujan Complexes and Bounded Degree Topological Expanders. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 484-493, 2014. Google Scholar
  19. T. Kaufman and D. Mass. Local-To-Global Agreement Expansion via the Variance Method. In 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151, pages 74:1-74:14, 2020. Google Scholar
  20. N. Linial and R. Meshulam. Homological connectivity of random 2-complexes. Combinatorica, 26(4):475-487, 2006. Google Scholar
  21. A. Lubotzky. Ramanujan complexes and high dimensional expanders. Japanese Journal of Mathematics, 9(2):137-169, 2014. Google Scholar
  22. A. Lubotzky, R. Meshulam, and S. Mozes. Expansion of building-like complexes. Groups, Geometry, and Dynamics, 10(1):155-175, 2016. Google Scholar
  23. A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988. Google Scholar
  24. A. Lubotzky, B. Samuels, and U. Vishne. Explicit constructions of ramanujan complexes of type Ã_d. European Journal of Combinatorics, 26(6):965-993, 2005. Google Scholar
  25. A. Lubotzky, B. Samuels, and U. Vishne. Ramanujan complexes of type Ã_d. Israel Journal of Mathematics, 149(1):267-299, 2005. 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