Better lower bounds for locally decodable codes

  • Deshpande, A.
  • Jain, R.
  • Kavitha, T.
  • Lokam, S. V.
  • Radhakrishnan, J.
ORKG logo Add to ORKG
Publication date
January 2002
Publisher
Institute of Electrical and Electronics Engineers (IEEE)

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 imp...

Extracted data

Loading...

Related items

Better lower bounds for locally decodable codes
  • Deshpande, A.
  • Jain, R.
  • Kavitha, T.
  • Lokam, S. V.
  • Radhakrishnan, J.
January 2002

An error-correcting code is said to be locally decodable if a randomized algorithm can recover any s...

Lower bounds for adaptive locally decodable codes
  • Deshpande, Amit
  • Jain, Rahul
  • Kavitha, T.
  • Lokam, Satyanarayana V.
  • Radhakrishnan, Jaikumar
October 2005

An error-correcting code is said to be locally decodable if a randomized algorithm can recover any s...

Lower bounds for linear locally decodable codes and private information retrieval
  • Goldreich, Oded
  • Karloff, Howard
  • Schulman, Leonard J.
  • Trevisan, Luca
October 2006

We prove that if a linear error-correcting code C:{0, 1}^n→{0, 1}^m is such that a bit of the messag...

We use cookies to provide a better user experience.