Explicit near-Ramanujan graphs of every degree
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020•dl.acm.org
… In this work, we obtain explicitd-regular ϵ-near-Ramanujan graphs for every d ⩾ 3 and every
ϵ > 0. As an example, we give the first explicit family of 7-regular graphs with λ2(G), |λn (G)|
⩽ 2 … Essentially, this means we show there exist nearRamanujan graphs whose adjacency
lists are computable in polylogn time, and furthermore there is a polylog(n)-time randomized
algorithm for finding them with high probability. More precisely, the following statement holds: …
ϵ > 0. As an example, we give the first explicit family of 7-regular graphs with λ2(G), |λn (G)|
⩽ 2 … Essentially, this means we show there exist nearRamanujan graphs whose adjacency
lists are computable in polylogn time, and furthermore there is a polylog(n)-time randomized
algorithm for finding them with high probability. More precisely, the following statement holds: …
For every constant d ≥ 3 and є > 0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n) vertices that is є-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2√d−1 + є (excluding the single trivial eigenvalue of d).
ACM Digital Library