×

Lower bounds for adaptive locally decodable codes. (English) Zbl 1085.94024

Summary: 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. J. Katz and L. Trevisan [On the efficiency of local decoding procedures for error correcting codes, Proc. 32nd STOC, 2000, 80–86 (2000)] showed that any such code \(C:\{0,1\}^n\to\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 show \(m=\Omega((n/\log|\Sigma|)^{q/(q-1)}\) without assuming that the decoder is nonadaptive.

MSC:

94B35 Decoding
94B65 Bounds on codes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Upper bounds on the communication complexity of private information retrieval, Proc ICALP, 1997, pp. 401-407. · Zbl 1401.68065
[2] , , and , Checking computations in poly-logartithmic time, Proc 23rd ACM Symp Theory of Computing (STOC), 1991, pp. 21-31.
[3] Babai, Comput Complexity 3(4) pp 370– (1993)
[4] and , Information-theoretic private information retrieval: A unified Construction, ICALP 2001, pp. 912-926. · Zbl 0986.68509
[5] , , and , Breaking the O(n1/(2k - 1)) barrier for information theoretic Private Information Retrieval, Proc 43rd IEEE FOCS, 2002, pp. 261-270.
[6] Chor, J ACM 45(6) (1998)
[7] , , , and , Better bounds for locally decodable codes, IEEE Conf Computational Complexity, 2002, pp. 184-193.
[8] , , , and , Self-testing/correcting for polynomials and for approximate functions, Proc 23rd STOC, 1991, pp. 32-42.
[9] Gemmel, Inform process Lett 43(4) pp 169– (1992)
[10] Personal Communication, cited in [12].
[11] , , and , Lower bounds for linear locally decodable codes and Private Information Retrieval, IEEE Conf Computational Complexity, 2002, 175-183.
[12] and , On the efficiency of local decoding procedures for error-correcting codes, Proc 32nd ACM Symp Theory of Computing (STOC), 2000, pp. 80-86. · Zbl 1296.94171
[13] and , Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proc 35th STOC, 2003, 106-115. · Zbl 1192.81082
[14] , , and , Extractors: Optimal up to constant factors, Proc 35th STOC, 2003, pp. 602-611. · Zbl 1192.68859
[15] Private access to distributed information, Master’s Thesis, Technion, Haifa, Israel, 1998.
[16] Optimal lower bounds for 2-query locally decodable linear codes, Proc 6th RANDOM, 2002, pp. 39-50. · Zbl 1028.94512
[17] and , Nearly linear-size holographic proofs, Proc 26th ACM STOC, 1994, pp. 194-203. · Zbl 1345.68180
[18] and , An optimal lower bound for 2-query locally decodable linear codes, October 2004, submitted.
[19] Sipser, IEEE Trans Inform Theory 42 pp 1710– (1996)
[20] , and , Pseudo-random generators without the XOR Lemma, Proc 31st STOC, 1999, pp. 537-546. · Zbl 1345.68138
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.