LIPIcs.FSTTCS.2022.4.pdf
- Filesize: 292 kB
- 1 pages
Document
Expanders in Higher Dimensions (Invited Talk)
Author
-
Part of:
Volume:
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
Cite AsGet BibTex
Irit Dinur. Expanders in Higher Dimensions (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.4
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.4
Abstract
Expander graphs have been studied in many areas of mathematics and in computer science with versatile applications, including coding theory, networking, computational complexity and geometry.
High-dimensional expanders are a generalization that has been studied in recent years and their promise is beginning to bear fruit. In the talk, I will survey some powerful local to global properties of high-dimensional expanders, and describe several interesting applications, ranging from convergence of random walks to construction of locally testable codes that prove the c³ conjecture (namely, codes with constant rate, constant distance, and constant locality).
Subject Classification
ACM Subject Classification
- Theory of computation → Expander graphs and randomness extractors
Keywords
- Expanders
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads