Lower bounds for adaptive locally decodable codes | Zendy

Deshpande Amit | Zendy; Jain Rahul | Zendy; Kavitha T. | Zendy; Lokam Satyanarayana V. | Zendy; Radhakrishnan Jaikumar | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Lower bounds for adaptive locally decodable codes

Author(s) -

Deshpande Amit,

Jain Rahul,

Kavitha T.,

Lokam Satyanarayana V.,

Radhakrishnan Jaikumar

Publication year - 2005

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.20069

Subject(s) - decoding methods , mathematics , encoding (memory) , code (set theory) , discrete mathematics , algorithm , combinatorics , computer science , set (abstract data type) , artificial intelligence , programming language

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 |Σ|) 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. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research