## Local Correctability of Expander Codes

Brett Hemenway

University of Pennsylvania

April 14, 2014

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.