pdf icon
Volume 20 (2024) Article 5 pp. 1-22
On the Elementary Construction of High-Dimensional Expanders by Kaufman and Oppenheim
Received: June 9, 2020
Revised: November 26, 2022
Published: October 26, 2024
Download article from ToC site:
[PDF (394K)] [PS (1641K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: high-dimensional expanders, groups, cosets
Categories: complexity, expanders, high-dimensional expanders, groups, cosets, exposition
ACM Classification: F.2.2, G.2.2
AMS Classification: 68R10

Abstract: [Plain Text Version]

At STOC 2018, Kaufman and Oppenheim presented an elementary construction of high-dimensional spectral expanders using elementary matrices. We give a short, self-contained elementary proof of the correctness of their construction. As a bonus, this also yields a simple construction and analysis of standard expanders of bounded degree.