Explicit Near-Ramanujan Graphs of Every Degree
From MaRDI portal
Publication:5856148
DOI10.1137/20M1342112OpenAlexW3129407338MaRDI QIDQ5856148
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
Publication date: 24 March 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1342112
Graph theory (including graph drawing) in computer science (68R10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- Lifts, discrepancy and nearly optimal spectral gap
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Ramanujan graphs
- Eigenvalues and expanders
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Explicit constructions of linear-sized superconcentrators
- The eigenvalues of random symmetric matrices
- On the second eigenvalue of a graph
- Cubic Ramanujan graphs
- The asymptotic number of labeled graphs with given degree sequences
- Some geometric aspects of graphs and their eigenfunctions
- Geometric algorithms and combinatorial optimization.
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- The Moore bound for irregular graphs
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Expanding graphs, Ramanujan graphs, and 1-factor perturbations
- Derandomized constructions of \(k\)-wise (almost) independent permutations
- Symmetric groups and expander graphs.
- On discrete subgroups of the two by two projective linear group over \(p\)-adic fields
- A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Expander graphs and their applications
- A proof of Alon’s second eigenvalue conjecture and related problems
- Expander graphs and gaps between primes
- Simple Constructions of Almost k-wise Independent Random Variables
- Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
- THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
- Ramanujan graphs and Hecke operators
- The threshold for SDP-refutation of random regular NAE-3SAT
- The non-backtracking spectrum of the universal cover of a graph
This page was built for publication: Explicit Near-Ramanujan Graphs of Every Degree
