On the efficiency of local decoding procedures for error-correcting codes 论文

摘要

We consider error-correcting codes where a bit of the message can be probabilistically recovered by looking at a limited number of bits (or blocks of bits) of a (possibly) corrupted encoding. Such codes can be derived from multivariate polynomial encodings, and have several applications in complexity theory, such as worst-case to average-case reductions, probabilistically checkable proofs, and private information retrieval. Such codes could have practical applications if they had at the same time constant information rate, the ability to correct a linear number of errors, and very efficient (ideally, constant-time) reconstruction procedures. In particular they would give fault-tolerant data storage with unlimited scalability. We show a negative result on the existence of such codes; namely, that linear encoding length is incompatible with a decoding procedure making a constant number of queries (which is necessary if one is to have constant reconstruction time). In particular, if a bit of a message of length n can be retrieved by looking at q blocks of length l, and the reconstruction procedure is robust to a fraction 5 of errors, then the encoding is made of m = f/(poly(1/q, 6, e)(n/l) q/(q-t))