Fetching the paper…

Reading the bibliography…

2016

Ramanujan Graphs in Polynomial Time

Cohen, Michael B.

Original
PDF
Post on X

Understand

The recent work by Marcus, Spielman and Srivastava proves the existence of bipartite Ramanujan (multi)graphs of all degrees and all sizes.

However, that paper did not provide a polynomial time algorithm to actually compute such graphs.
Here, we provide a polynomial time algorithm to compute certain expected characteristic polynomials related to this construction.
This leads to a deterministic polynomial time algorithm to compute bipartite Ramanujan (multi)graphs of all degrees and all sizes.

Ramanujan Graphs in Polynomial Time · Around

Built on

Interlacing families i: Bipartite ramanujan graphs of all degrees
A. Marcus, D. A. Spielman, and N. Srivastava · 2013
Earlier work this paper cites.
Interlacing families ii: Mixed characteristic polynomials and the kadison-singer problem
Original
Adam Marcus, Daniel A Spielman, and Nikhil Srivastava · 2013
Earlier work this paper cites.

Similar

Ramanujan coverings of graphs
Original
Chris Hall, Doron Puder, and William F Sawin · 2015
Cited alongside, same era.
Interlacing families iv: Bipartite ramanujan graphs of all sizes
A. W. Marcus, D. A. Spielman, and N. Srivastava · 2015
Cited alongside, same era.

Then

Finite free convolutions of polynomials
Original
Adam Marcus, Daniel A Spielman, and Nikhil Srivastava · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…