EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE

Sidhanth Mohanty; Ryan O'Donnell; Pedro Paredes

doi:10.1137/20M1342112

EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE

Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes

Research output: Contribution to journal › Article › peer-review

9 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 language	English (US)
Pages (from-to)	1-23
Number of pages	23
Journal	SIAM Journal on Computing
Volume	51
Issue number	3
DOIs	https://doi.org/10.1137/20M1342112
State	Published - 2022
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Keywords

Expander graphs
derandomization
random matrix theory

Access to Document

10.1137/20M1342112

Cite this

@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 = "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",

}

TY - JOUR

T1 - EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE

AU - Mohanty, Sidhanth

AU - O'Donnell, Ryan

AU - Paredes, Pedro

PY - 2022

Y1 - 2022

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

KW - Expander graphs

KW - derandomization

KW - random matrix theory

UR - https://www.scopus.com/pages/publications/85134886050

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

U2 - 10.1137/20M1342112

DO - 10.1137/20M1342112

M3 - Article

AN - SCOPUS:85134886050

SN - 0097-5397

VL - 51

SP - 1

EP - 23

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this