2021/11/15 by Chen, Xue, Cheng, Kuan, Li, Xin +1
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2111.07629
We study the classical expander codes, introduced by Sipser and Spielman \citeSS96. Given any constants 0< α, ε < 1/2, and an arbitrary bipartite graph with N vertices on the left, M < N vertices on the right, and left degree D such that any left subset S of size at most αN has at least (1-ε)|S|D neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly (αN)/(2 ε ). This is strictly better than the best known previous result of 2(1-ε ) αN \citeSudan2000note, Viderman13b whenever ε < 1/2, and improves the previous result significantly when ε is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever ε < (1)/(4). Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.