Deshpande, Amit ; Jain, Rahul ; Kavitha, T. ; Lokam, Satyanarayana V. ; Radhakrishnan, Jaikumar (2005) Lower bounds for adaptive locally decodable codes Random Structures & Algorithms, 27 (3). pp. 358-378. ISSN 1042-9832
Full text not available from this repository.
Official URL: http://onlinelibrary.wiley.com/doi/10.1002/rsa.200...
Related URL: http://dx.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 |S|)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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to John Wiley and Sons. |
| ID Code: | 57652 |
| Deposited On: | 29 Aug 2011 08:38 |
| Last Modified: | 29 Aug 2011 08:38 |
Repository Staff Only: item control page
