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

• Published in: Computational complexity 2023-06, Vol.32 (1), Article 2
• Main Authors: Batra, Rishabh, Saxena, Nitin, Shringi, Devansh
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Computational Mathematics and Numerical Analysis; Computer Science; Construction; Expanders; Graph theory; Graphs
• ISSN: 1016-3328; 1420-8954
• DOI: 10.1007/s00037-023-00235-y

A constant locality function is one in which each output bit depends on just a constant number of input bits. Viola and Wigderson (2018) gave an explicit construction of bipartite degree-3 Ramanujan graphs such that each neighbor of a vertex can be computed using a constant locality function. In this work, we construct the first explicit local Ramanujan graph (bipartite) of degree q + 1, where q > 2 is any prime power. Alon and Capalbo (2002) used 4-regular, 8-regular and 44-regular Ramanujan graphs to construct unique-neighbor expanders that were 3-regular, 4-regular, 6-regular and `bipartite' (respectively). Viola and Wigderson (2018) had asked if a local construction of such unique-neighbor expanders exists. Our construction gives local 4-regular, 8-regular and 44-regular Ramanujan graphs, which also solves the corresponding open problem of the construction of local unique-neighbor expanders. The only known explicit construction of Ramanujan graphs exists for degree q + 1, where q is a prime-power. In this paper, we essentially localize the explicit Ramanujan graphs for all these degrees. Our results use the explicit Ramanujan graphs by Morgenstern (1994) and a significant generalization of the ideas used in Viola and Wigderson (2018).