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.