Explicit near-Ramanujan graphs of every degree

Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 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 2gd-1 + " (excluding the single trivial eigenvalue of d).

Original languageEnglish (US)
Title of host publicationSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
EditorsKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
PublisherAssociation for Computing Machinery
Pages510-523
Number of pages14
ISBN (Electronic)9781450369794
DOIs
StatePublished - Jun 8 2020
Externally publishedYes
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: Jun 22 2020Jun 26 2020

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Country/TerritoryUnited States
CityChicago
Period6/22/206/26/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Explicit Ramanujan graphs

Cite this