Lower bounds for adaptive locally decodable codes

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 12 showed that any such code C : {0, 1}ⁿ → Σ^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., 2005