Abstract: Expander graphs have been, during the last five decades, the subject of a most fruitful interaction between pure mathematics and computer science, with influence and applications going both ways. In the last decade, a theory of “high dimensional expanders” has begun to emerge. We will describe some paths of this new area of study.
https://eta.impa.br/dl/PL002.pdf
https://arxiv.org/abs/1712.02526
扩展图来自于半单Lie群表示论中的Kazhdan性质(T)和自守形式中的Ramanujan猜想(Ramanujan图 )。本文讨论构造高维扩展图的方法：(1) 通过Laplace算子的谱间隙性质，(2)几何与拓扑的扩展图，(3) 随机图的方法。最后，作者给出高维扩展图在计算机科学中的应用：概率可检验证明，局部可测试代码， 属性测试，量子计算和量子纠错码。
相关附件
13-PL002 Lubotzky
