Explicit near-Ramanujan graphs of every degree

Sidhanth Mohanty; Ryan O'Donnell; Pedro Paredes

doi:10.1145/3357713.3384231

Explicit near-Ramanujan graphs of every degree

Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 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 language	English (US)
Title of host publication	STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
Editors	Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
Publisher	Association for Computing Machinery
Pages	510-523
Number of pages	14
ISBN (Electronic)	9781450369794
DOIs	https://doi.org/10.1145/3357713.3384231
State	Published - Jun 8 2020
Externally published	Yes
Event	52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States Duration: Jun 22 2020 → Jun 26 2020

Publication series

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

Conference

Conference	52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Country/Territory	United States
City	Chicago
Period	6/22/20 → 6/26/20

All Science Journal Classification (ASJC) codes

Software

Keywords

Explicit Ramanujan graphs

Access to Document

10.1145/3357713.3384231

Cite this

Mohanty, S., O'Donnell, R., & Paredes, P. (2020). Explicit near-Ramanujan graphs of every degree. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 510-523). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3357713.3384231

Mohanty, Sidhanth ; O'Donnell, Ryan ; Paredes, Pedro. / Explicit near-Ramanujan graphs of every degree. STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. editor / Konstantin Makarychev ; Yury Makarychev ; Madhur Tulsiani ; Gautam Kamath ; Julia Chuzhoy. Association for Computing Machinery, 2020. pp. 510-523 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{c6e2b85e858945289d9c92fa5a8ad6cf,

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

keywords = "Explicit Ramanujan graphs",

author = "Sidhanth Mohanty and Ryan O'Donnell and Pedro Paredes",

note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 ; Conference date: 22-06-2020 Through 26-06-2020",

year = "2020",

month = jun,

day = "8",

doi = "10.1145/3357713.3384231",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "510--523",

editor = "Konstantin Makarychev and Yury Makarychev and Madhur Tulsiani and Gautam Kamath and Julia Chuzhoy",

booktitle = "STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing",

}

Mohanty, S, O'Donnell, R & Paredes, P 2020, Explicit near-Ramanujan graphs of every degree. in K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (eds), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 510-523, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, United States, 6/22/20. https://doi.org/10.1145/3357713.3384231

Explicit near-Ramanujan graphs of every degree. / Mohanty, Sidhanth; O'Donnell, Ryan; Paredes, Pedro.
STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Konstantin Makarychev; Yury Makarychev; Madhur Tulsiani; Gautam Kamath; Julia Chuzhoy. Association for Computing Machinery, 2020. p. 510-523 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Explicit near-Ramanujan graphs of every degree

AU - Mohanty, Sidhanth

AU - O'Donnell, Ryan

AU - Paredes, Pedro

PY - 2020/6/8

Y1 - 2020/6/8

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

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

KW - Explicit Ramanujan graphs

UR - http://www.scopus.com/inward/record.url?scp=85086762247&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086762247&partnerID=8YFLogxK

U2 - 10.1145/3357713.3384231

DO - 10.1145/3357713.3384231

M3 - Conference contribution

AN - SCOPUS:85086762247

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 510

EP - 523

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -

Mohanty S, O'Donnell R, Paredes P. Explicit near-Ramanujan graphs of every degree. In Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, editors, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2020. p. 510-523. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3357713.3384231

Explicit near-Ramanujan graphs of every degree

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this