@article{c1b4bac873c44e0983a5a92143043387,
title = "EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE",
abstract = "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).",
keywords = "Expander graphs, derandomization, random matrix theory",
author = "Sidhanth Mohanty and Ryan O'Donnell and Pedro Paredes",
note = "Funding Information: \ast Received by the editors June 4, 2020; accepted for publication (in revised form) November 23, 2020; published electronically February 23, 2021. https://doi.org/10.1137/20M1342112 Funding: The first author was supported by NSF grant CCF-1718695. The second and third authors were supported by NSF grant CCF-1717606. This material is based upon work supported by the National Science Foundation under the grant numbers listed above. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation (NSF). \dagger EECS Department, University of California at Berkeley, Berkeley, CA 94709 USA (sidhanthm@ cs.berkeley.edu). \ddagger Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 USA (odonnell@cs.cmu.edu, preisben@andrew.cmu.edu). Publisher Copyright: {\textcopyright} 2021 Association for Computing Machinery.",
year = "2022",
doi = "10.1137/20M1342112",
language = "English (US)",
volume = "51",
pages = "1--23",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",
}