Fetching the paper…
Reading the bibliography…
For every constant $d \geq 3$ and $\epsilon > 0$, we give a deterministic $\mathrm{poly}(n)$-time algorithm that outputs a $d$-regular graph on $\Theta(n)$ vertices that is $\epsilon$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2\sqrt{d-1} + \epsilon$ (excluding the single trivial eigenvalue of~$d$).
On discrete subgroups of the two by two projective linear group over 𝔭 {\mathfrak{p}} -adic fields
Yasutaka Ihara · 1966
Earlier work this paper cites.
On the realization of networks in three-dimensional space
Jānis Bārzdi n · 1967
Earlier work this paper cites.
Complexity of an optimum nonblocking switching network without reconnections
Grigory Margulis · 1973
Earlier work this paper cites.
Explicit construction of concentrators
Grigory Margulis · 1973
Earlier work this paper cites.
On the complexity of a concentrator
Mark Pinsker · 1973
Earlier work this paper cites.
Arbres, amalgames, SL 2 {\rm SL}_{2}
Jean-Pierre Serre · 1977
Earlier work this paper cites.
The asymptotic number of labeled graphs with given degree sequences
Edward Bender and Rodney Canfield · 1978
Earlier work this paper cites.
A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
Béla Bollobás · 1980
Earlier work this paper cites.
Explicit constructions of linear-sized superconcentrators
Ofer Gabber and Zvi Galil · 1981
Earlier work this paper cites.
An NP-complete problem – some aspects of its solution and some possible applications
Johan Håstad · 1984
Earlier work this paper cites.
Eigenvalues and expanders
Noga Alon · 1986
Earlier work this paper cites.
Ramanujan graphs
Alexander Lubotzky, Ralph Phillips, and Peter Sarnak · 1988
Earlier work this paper cites.
Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators
Grigory Margulis · 1988
Earlier work this paper cites.
Zeta functions of finite graphs and representations of p p -adic groups
Ki-ichiro Hashimoto · 1989
Earlier work this paper cites.
Ramanujan graphs and Hecke operators
Arnold Pizer · 1990
Earlier work this paper cites.
New algorithms for finding irreducible polynomials over finite fields
Victor Shoup · 1990
Earlier work this paper cites.
On the second eigenvalue of a graph
A. Nilli · 1991
Cited alongside, same era.
Simple constructions of almost k k -wise independent random variables
Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta · 1992
Cited alongside, same era.
The Ihara–Selberg zeta function of a tree lattice
Hyman Bass · 1992
Cited alongside, same era.
Cubic Ramanujan graphs
Patrick Chiu · 1992
Cited alongside, same era.
Some geometric aspects of graphs and their eigenfunctions
Joel Friedman · 1993
Cited alongside, same era.
Small-bias probability spaces: efficient constructions and applications
Joseph Naor and Moni Naor · 1993
Cited alongside, same era.
Symmetric groups and expander graphs
Martin Kassabov · 2007
Later among the works it cites.
Expander graphs and gaps between primes
Sebastian M. Cioabă and M. Ram Murty · 2008
Later among the works it cites.
A proof of Alon’s second eigenvalue conjecture and related problems
Joel Friedman · 2008
Later among the works it cites.
Derandomized constructions of k k -wise (almost) independent permutations
Eyal Kaplan, Moni Naor, and Omer Reingold · 2009
Later among the works it cites.
Graph zeta function in the Bethe free energy and loopy belief propagation
Yusuke Watanabe and Kenji Fukumizu · 2009
Later among the works it cites.
Cutoff phenomena for random walks on random regular graphs
Eyal Lubetzky and Allan Sly · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Moshe Morgenstern · 1994
Cited alongside, same era.
Models of random regular graphs
Nicholas Wormald · 1999
Cited alongside, same era.
Random graphs
Svante Janson, Tomasz Łuczak, and Andrzej Rucinski · 2000
Cited alongside, same era.
Random Graphs
Béla Bollobás · 2001
Cited alongside, same era.
The Moore bound for irregular graphs
Noga Alon, Shlomo Hoory, and Nathan Linial · 2002
Cited alongside, same era.
Entropy waves, the zig-zag graph product, and new constant-degree expanders
Omer Reingold, Salil Vadhan, and Avi Wigderson · 2002
Cited alongside, same era.
A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
Avraham Ben-Aroya and Amnon Ta-Shma · 2011
Later among the works it cites.
Almost k k -wise vs. k k -wise independent permutations, and uniformity for general group actions
Noga Alon and Shachar Lovett · 2013
Later among the works it cites.
The non-backtracking spectrum of the universal cover of a graph
Omer Angel, Joel Friedman, and Shlomo Hoory · 2015
Later among the works it cites.
Interlacing families I: Bipartite Ramanujan graphs of all degrees
Adam Marcus, Daniel Spielman, and Nikhil Srivastava · 2015
Later among the works it cites.
Interlacing families IV: Bipartite Ramanujan graphs of all sizes
Adam Marcus, Daniel Spielman, and Nikhil Srivastava · 2015
Later among the works it cites.
Lecture notes on random graphs and probabilistic combinatorial optimization
Charles Bordenave · 2016
Later among the works it cites.
Ramanujan graphs in polynomial time
Michael Cohen · 2016
Later among the works it cites.
A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts
Charles Bordenave · 2019
Closest in time.
The threshold for SDP-refutation of random regular NAE-3SAT
Yash Deshpande, Andrea Montanari, Ryan O’Donnell, Tselil Schramm, and Subhabrata Sen · 2019
Closest in time.
The SDP value for random two-eigenvalue CSPs
Sidhanth Mohanty, Ryan O’Donnell, and Pedro Paredes · 2019
Closest in time.