

























For every constant $d \geq 3$ and $ε> 0$, we give a deterministic $\mathrm{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\sqrt{d-1} + ε$ (excluding the single trivial eigenvalue of~$d$).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。