Tali Kaufman
ABSTRACT
High dimensional expanders is a vibrant emerging field of study. Nevertheless, the only known construction of bounded degree high dimensional expanders is based on Ramanujan complexes, whereas one dimensional bounded degree expanders are abundant.
In this work we construct new families of bounded degree high dimensional expanders obeying the local spectral expansion property. A property that implies, geometric overlapping, fast mixing of high dimensional random walks, agreement testing and agreement expansion. The construction also yields new families of expander graphs.
The construction is quite elementary and it is presented in a self contained manner; This is in contrary to the highly involved construction of the Ramanujan complexes. The construction is also strongly symmetric; The symmetry of the construction could be used, for example, to obtain good symmetric LDPC codes that were previously based on Ramanujan graphs.
- Martin R. Bridson and André Haefliger. 1999.Google Scholar
- Metric spaces of non-positive curvature. (1999), xxii+643 pages. 3- 662- 12494- 9Google Scholar
- Frank Deutsch. 2001.Google Scholar
- Best approximation in inner product spaces. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Vol. 7. Springer-Verlag, New York. xvi+338 pages. 1- 4684- 9298- 9Google Scholar
- Irit Dinur and Tali Kaufman. 2017. High dimensional expanders imply agreement expanders. Electronic Colloquium on Computational Complexity (ECCC) (2017).Google Scholar
- Jan Dymara and Tadeusz Januszkiewicz. 2002.Google Scholar
- Cohomology of buildings and their automorphism groups. Invent. Math. 150, 3 (2002), 579–627. org/10.1007/s00222- 002- 0242yGoogle Scholar
- Mikhail Ershov and Andrei Jaikin-Zapirain. 2010.Google Scholar
- Property (T) for noncommutative universal lattices. Invent. Math. 179, 2 (2010), 303–347. 009- 0218- 2Google Scholar
- Shai Evra and Tali Kaufman. 2017.Google Scholar
- Bounded Degree Cosystolic Expanders of Every Dimension. https://arxiv.org/abs/1510.00839. (2017).Google Scholar
- https://arxiv.org/abs/ 1510.00839Google Scholar
- Martin Kassabov. 2011. Subspace arrangements and property T. Groups Geom. Dyn. 5, 2 (2011), 445–477.Google ScholarCross Ref
- Tali Kaufman and Alexander Lubotzky. 2012. Edge transitive Ramanujan graphs and symmetric LDPC good codes. In STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing. ACM, New York, 359–365. Google ScholarDigital Library
- Tali Kaufman and David Mass. 2017. High Dimensional Combinatorial Random Walks and Colorful Expansion. In Innovations in Theoretical Computer Science (ITCS).Google Scholar
- Tali Kaufman and Izhar Oppenheim. 2017. High Order Random Walks: Beyond Spectral Gap. https://arxiv.org/abs/1707.02799. (2017).Google Scholar
- https://arxiv.org/abs/1707.Google Scholar
- 02799Google Scholar
- Tali Kaufman and Izhar Oppenheim. 2018. Construction of new local spectral high dimensional expanders. https://arxiv.org/abs/1710.05304. (2018).Google Scholar
- https: //arxiv.org/abs/1710.05304Google Scholar
- Tali Kaufman and Avi Wigderson. 2016. Symmetric LDPC codes and local testing. Combinatorica 36, 1 (2016), 91–120. Google ScholarDigital Library
- Alexander Lubotzky, Beth Samuels, and Uzi Vishne. 2005. Explicit constructions of Ramanujan complexes of type e A d. European J. Combin. 26, 6 (2005), 965–993. Google ScholarDigital Library
- Alexander Lubotzky, Beth Samuels, and Uzi Vishne. 2005.Google Scholar
- Ramanujan complexes of type e A d. Israel J. Math. 149 (2005), 267–299. BF02772543 Probability in mathematics.Google Scholar
- Izhar Oppenheim. 2017.Google Scholar
- Averaged projections, angles between groups and strengthening of Banach property (T). Math. Ann. 367, 1-2 (2017), 623–666. 016- 1413- 2Google Scholar
- Izhar Oppenheim. 2018. Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps. Discrete Comput. Geom. 59, 2 (2018), 293–330. 017- 9948x Google ScholarDigital Library
- Izhar Oppenheim. 2018. Local Spectral Expansion Approach to High Dimensional Expanders Part II: Mixing and Geometrical overlapping. https://arxiv.org/abs/ 1803.01320. (2018).Google Scholar
Index Terms
- Construction of new local spectral high dimensional expanders
Recommendations
Bounded degree cosystolic expanders of every dimension
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of ComputingIn recent years a high dimensional theory of expanders has emerged. The notion of combinatorial expansion of graphs (i.e. the Cheeger constant of a graph) has seen two generalizations to high dimensional simplicial complexes. One generalization, known ...
New High Dimensional Expanders from Covers
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of ComputingWe present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but ...
Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps
We introduce the notion of local spectral expansion of a simplicial complex as a possible analogue of spectral expansion defined for graphs. We then show that the condition of local spectral expansion for a complex yields various spectral gaps in both ...
Comments