Better lower bounds for locally decodable codes

Deshpande, A. ; Jain, R. ; Kavitha, T. ; Lokam, S. V. ; Radhakrishnan, J. (2002) Better lower bounds for locally decodable codes Proceedings of 17th IEEE Annual Conference on Computational Complexity, 2002 . pp. 152-161.

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...

Related URL: http://dx.doi.org/10.1109/CCC.2002.1004354

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 (2000) 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 improve the results of Katz and Trevisan (2000) in two ways. First, we give a more direct proof of their result. Second, and this is our main result, we prove that m = O((n/log|∑|)q(q-1)/) even if the decoding algorithm is adaptive. An important ingredient of our proof is a randomized method for smoothing an adaptive decoding algorithm. The main technical tool we employ is the Second Moment Method.

Item Type:Article
Source:Copyright of this article belongs to Proceedings of 17th IEEE Annual Conference on Computational Complexity, 2002.
ID Code:89512
Deposited On:27 Apr 2012 13:38
Last Modified:27 Apr 2012 13:38

Repository Staff Only: item control page