Local Correctability of Expander Codes

An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental tradeoff in locally decodable codes between the rate (the ratio of message length to codeword length) and the locality (the number of symbols read by the decoder). Ideally, one strives for high rate and low locality. Constructions of locally decodable codes can be divided into two categories, low-rate, low-locality and high-rate, high-locality. The Matching Vector codes of Yekhanin and Efremenko have locality 3, but their rate goes to zero super-polynomially. The Multiplicity Codes of Kopparty, Saraf and Yekhanin and the Affine Invariant Codes of Guo, Kopparty and Sudan have high rate (approaching one) and locality \(n^\epsilon\). In this work we provide a local-decoding algorithm for the expander codes of Sipser and Spielman. When appropriately instantiated, this leads to a novel construction of locally decodable codes with rate approaching one and locality \(n^\epsilon\). This work appeared in ICALP '13 and is joint work with Rafail Ostrovsky and Mary Wootters. http://arxiv.org/abs/1304.8129