Optimal lower bounds for 2-query locally decodable linear codes

Abstract. This paper presents essentially optimal lower bounds on the size of linear codes C: {0, 1} n →{0, 1} m which have the property that, for constants δ, ɛ> 0, any bit of the message can be recovered with probability 1 + ɛ by an algorithm reading 2 only 2 bits of a codeword corrupted in up to δm positions. Such codes are known to be applicable to, among other things, the construction and analysis of information-theoretically secure private information retrieval schemes. In this work, we show that m must be at least 2 Ω ( δ 1−2ɛ n). Our results extend work by Goldreich, Karloff, Schulman, and Trevisan [GKST02], which is based heavily on methods developed by Katz and Trevisan [KT00]. The key to our improved bounds is an analysis which bypasses an intermediate reduction used in both prior works. The resulting improvement in the efficiency of the overall analysis is sufficient to achieve a lower bound optimal within a constant factor in the exponent. A construction of a locally decodable linear code matching this bound is presented.