Lower bounds and correctness results for locally decodable codes

Abstract

We study fundamental properties of Locally Decodable Codes (LDCs). LDCs are motivated by the intuition that traditional codes do not have a good tradeoff between resistance to arbitrary error and probe complexity. For example, if you apply a traditional code on a database, the resulting codeword can be resistant to error even if a constant fraction of it was corrupted; however, to accomplish this, the decoding procedure would typically have to analyze the entire codeword. For large data sizes, this is considered computationally expensive. This may be necessary even if you are only trying to recover a single bit of the database! This motivates the concept of LDCs, which encode data in such a way that up to a constant fraction of the result could be corrupted; while the decoding procedures only need to read a sublinear, ideally constant, number of codeword bits to retrieve any bit of the input with high probability. Our most exciting contribution is an exponential lower bound on the length of three query LDCs (binary or linear) with high correctness. This is the first strong length lower bound for any kind of LDC allowing more than two queries. For LDCs allowing three or more queries, the previous best lower bound, given by Woodruff, is below [omega](n2). Currently, the best upper bound is sub-exponential, but still very large. If polynomial length constructions exist, LDCs might be useful in practice. If polynomial length constructions do not exist, LDCs are much less likely to find adoption -- the resources required to implement them for large database sizes would be prohibitive. We prove that in order to achieve just slightly higher correctness than the current best constructions, three query LDCs (binary or linear) require exponential size. We also prove several impossibility results for LDCs. It has been observed that for an LDC that withstands up to a delta fraction of error, the probability of correctness cannot be arbitrarily close to 1. However, we are the first to estimate the largest correctness probability obtainable for a given delta. We prove close to tight bounds for arbitrary numbers of queries.