Better lower bounds for 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 [KT] showed that any such code C {0, 1} --> Sigma(m) with a decoding algorithm that makes at most q probes must satisfy m = Omega((n/log \Sigma\)(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 improve the results of [KT] in two ways. First, we give a more direct proof of their result. Second, and this is our main result, we prove that in = Omega((n/log\Sigma\)(q/(q-1))) even if the decoding algorithm is adaptive. An important ingredient of our proof is a randomized method for smoothening an adaptive decoding algorithm. The main technical tool we employ is the Second Moment Method.