Lower bounds for adaptive locally decodable codes
- 2 May 2005
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 27 (3), 358-378
- https://doi.org/10.1002/rsa.20069
Abstract
An error‐correcting code is said to be locally decodable if a randomized algorithm can recover any single bit of a message by reading only a small number of symbols of a possibly corrupted encoding of the message. Katz and Trevisan On the efficiency of local decoding procedures for error correcting codes, STOC, 2000, pp. 80–86 showed that any such code C : {0, 1}n → Σm with a decoding algorithm that makes at most q probes must satisfy m = Ω((n/log |Σ|)q/(q−1)). They assumed that the decoding algorithm is non‐adaptive, and left open the question of proving similar bounds for adaptive decoders. We show m = Ω((n/log |Σ|)q/(q−1)) without assuming that the decoder is nonadaptive. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005Keywords
This publication has 2 references indexed in Scilit:
- Expander codesIEEE Transactions on Information Theory, 1996
- Highly resilient correctors for polynomialsInformation Processing Letters, 1992