EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE

Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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).

Original languageEnglish (US)
Pages (from-to)1-23
Number of pages23
JournalSIAM Journal on Computing
Volume51
Issue number3
DOIs
StatePublished - 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • Expander graphs
  • derandomization
  • random matrix theory

Fingerprint

Dive into the research topics of 'EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE'. Together they form a unique fingerprint.

Cite this