Local Correctability of Expander Codes
Brett Hemenway, rafail Ostrovsky, Mary Wootters
Abstract:
In this work, we present the first local-decoding algorithm for expander codes. This yields a new family of constant-rate codes that cab recover from a constant fraction of errors in the codeword symbols, and where any symbol of the codeword can be recovred with high probability by reading NE from the corrupted codeword, where N is the block-length of the code.
Expander codes introduced by Sipser and Spielman, are formed from an expander graph G=(V, E) of degree d, and an inner code of block-length d over an alphabet Σ. Each edge of the expander graph is associated with a symbol in Σ. A string in ΤE will be a codeword if for each vertex in V, the symbols on the adjacent edges form codeword in the inner code.
We show that if the inner code has a smooth reconstruction algorithm in the noiseless setting, then the corresponding expander code has an efficient local-correction algorithm in the noisy setting. Instantiating our construction with inner codes based on finite geometries, we obtain a novel locally decodable codes with constant rate. This provides an alternative to the multiplicity codes of Kopparty, Saraf and Yekhanin (STOC 11) and the lifted codes of Guo, Kopparty and Sudan (ITCS' 13).
comment: Preliminary version appeared in ICALP 2013 pp: 540-551. Full version appeared in Inf. Comput. 243: 178-190 (2015)
Fetch PDF file of the paper
| Back to Publications List |