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).
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Expander graphs
- random matrix theory