STOC2022
Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders
Amitay Kamber, Tali Kaufman
被引用 5 次
摘要
The question of finding expander graphs with strong vertex expansion properties such as unique neighbor expansion and lossless expansion is central to computer science. A barrier to constructing these is that strong notions of expansion could not be proven via the spectral expansion paradigm.