Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)

DOI10.1007/s00037-023-00235-yOpenAlexW4362670070MaRDI QIDQ6113103

Rishabh Batra, Devansh Shringi, Nitin Saxena

Publication date: 10 July 2023

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-023-00235-y

zbMATH Keywords

finite fieldsexpanderslinear groupsCayleyRamanujan graphsSchreier\(\mathrm{NC}^0\)constant localityresiduosityunique-neighbor expanders

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• Explicit constructions of linear-sized superconcentrators
• On the second eigenvalue of a graph
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Local expanders
• Expander codes
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Expander graphs and their applications
• Undirected connectivity in log-space
• Towards a Study of Low-Complexity Graphs
• Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
• Error exponents of expander codes
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Graph Connectivities, Network Coding, and Expander Graphs
• Cryptography in $NC^0$
• The PCP theorem by gap amplification

This page was built for publication: Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)