2021/12/02 by Fernando Granha Jeronimo, Tushant Mittal, Jeronimo, Fernando Granha +7 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.DM #cs.DS #cs.IT #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.2112.01647
31 pages
arxiv created 2021/12/02 · arxiv updated 2021/12/06
For an abelian group H acting on the set [ℓ], an (H,ℓ)-lift of a graph G0 is a graph obtained by replacing each vertex by ℓ copies, and each edge by a matching corresponding to the action of an element of H. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H \leqslant Sym(ℓ), constant degree d ≥ 3 and ε> 0, we construct explicit d-regular expander graphs G obtained from an (H,ℓ)-lift of a (suitable) base n-vertex expander G0 with the following parameters: (i) λ(G) ≤ 2√(d-1) + ε, for any lift size ℓ ≤ 2nδ where δ=δ(d,ε), (ii) λ(G) ≤ ε⋅ d, for any lift size ℓ ≤ 2^nδ0 for a fixed δ0 > 0, when d ≥ d0(ε), or (iii) λ(G) ≤ \widetildeO(√(d)), for lift size ``exactly'' ℓ = 2Θ(n). As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing'" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.