A locally decodable code (LDC) C: 0,1 ^k -> 0,1 ^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of O(1)-query LDCs have super-polynomial blocklength. The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of O(1)-query relaxed LDCs achieve blocklength n = O(k^ 1+ ) for an arbitrarily small constant . We prove a lower bound which shows that O(1)-query relaxed LDCs cannot achieve blocklength n = k^ 1+ o(1) . This resolves an open problem raised by Goldreich in 2004.
A linear (q, δ, ϵ,m(n))-locally decodable code (LDC) C : ( F ) n → ( F ) m(n) is a linear transformation from the vector space ( F ) n to the space ( F ) m(n) for which each message symbol x i can be recovered with probability at least ( 1 | F | + ) from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to δm(n) positions of C(x) are corrupted. In a recent work of Dvir, the author shows that lower bounds for linear LDCs can imply lower bounds for arithmetic circuits. He suggests that proving lower bounds for LDCs over the complex or real field is a good starting point for approaching one of his conjectures. Our main result is an m(n) = Ω(n 2) lower bound for linear 3-query LDCs over any, possibly infinite, field. The constant in the Ω(·) depends only on e and δ. This is the first lower bound better than the trivial m(n) = Ω(n) for arbitrary fields and more than two queries.  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 spl rarr spl Sigma sup m with a decoding algorithm that makes at most q probes must satisfy m = spl Omega ((n log | spl Sigma |) sup 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 = spl Omega ((n log| spl Sigma |) sup q (q-1) ) even if the decoding algorithm is adaptive. An important ingredient of our proof is a randomized method for smoothing an adaptive decoding algorithm. The main technical tool we employ is the Second Moment Method. We prove new lower bounds for locally decodable codes and private information retrieval. We show that a 2-query LDC encoding n-bit strings over an l-bit alphabet, where the decoder only uses b bits of each queried position, needs code length @math Similarly, a 2-server PIR scheme with an n-bit database and t-bit queries, where the user only needs b bits from each of the two l-bit answers, unknown to the servers, satisfies @math This implies that several known PIR schemes are close to optimal. Our results generalize those of [8], who proved roughly the same bounds for linear LDCs and PIRs. Like earlier work by Kerenidis and de Wolf [12], our classical bounds are proved using quantum computational techniques. In particular, we give a tight analysis of how well a 2-input function can be computed from a quantum superposition of both inputs. A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for m ≥ n, the rank of any (q,k,t)-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least n - (qtn 2k)2. Using this result we derive the following applications: Impossibility results for 2-query LCCs over large fields: A 2-query locally correctable code (LCC) is an error correcting code in which every codeword coordinate can be recovered, probabilistically, by reading at most two other code positions. Such codes have numerous applications and constructions (with exponential encoding length) are known over finite fields of small characteristic. We show that infinite families of such linear 2-query LCCs do not exist over fields of characteristic zero or large characteristic regardless of the encoding length. Generalization of known results in combinatorial geometry: We prove a quantitative analog of the Sylvester-Gallai theorem: Let v1,...,vm be a set of points in Cd such that for every i ∈ [m] there exists at least δ m values of j ∈ [m] such that the line through vi,vj contains a third point in the set. We show that the dimension of v1,...,vm is at most O(1 δ2). Our results generalize to the high-dimensional case (replaceing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).  A locally decodable code (LDC) encodes n-bit strings x in m-bit codewords C(x) in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries require exponential length: m = 2Ω(n). Previously, this was known only for linear codes (, in: Proceedings of 17th IEEE Conference on Computation Complexity, 2002, pp. 175-183). The proof proceeds by showing that a 2-query LDC can be decoded with a single quantum query, when defined in an appropriate sense. It goes on to establish an exponential lower bound on any 'l-query locally quantum-decodable code'. We extend our lower bounds to non-binary alphabets and also somewhat improve the polynomial lower bounds by Katz and Trevisan for LDCs with more than 2 queries. Furthermore, we show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2-server private information retrieval (PIR) scheme with O(n3 10) qubits of communication, beating the O(n1 3) bits of communication of the best known classical 2-server PIR. A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates. We show that any zero-error @math -query locally correctable code @math that can correct a constant fraction of corrupted symbols must have @math . We say that an LCC is zero-error if there exists a non-adaptive corrector algorithm that succeeds with probability @math when the input is an uncorrupted codeword. All known constructions of LCCs are zero-error. Our result is tight upto constant factors in the exponent. The only previous lower bound on the length of 2-query LCCs over large alphabet was @math due to Katz and Trevisan (STOC 2000). Our bound implies that zero-error LCCs cannot yield @math -server private information retrieval (PIR) schemes with sub-polynomial communication. Since there exists a @math -server PIR scheme with sub-polynomial communication (STOC 2015) based on a zero-error @math -query locally decodable code (LDC), we also obtain a separation between LDCs and LCCs over large alphabet. For our proof of the result, we need a new decomposition lemma for directed graphs that may be of independent interest. Given a dense directed graph @math , our decomposition uses the directed version of Szemeredi regularity lemma due to Alon and Shapira (STOC 2003) to partition almost all of @math into a constant number of subgraphs which are either edge-expanding or empty. We prove that if a linear error-correcting code C: 0, 1 sup n spl rarr 0, 1 sup m is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m = 2 sup spl Omega (n) . We also present several extensions of this result. We show a reduction from the complexity, of one-round, information-theoretic private information retrieval systems (with two servers) to locally decodable codes, and conclude that if all the servers' answers are linear combinations of the database content, then t = spl Omega (n 2 sup a ), where t is the length of the user's query and a is the length of the servers' answers. Actually, 2 sup a can be replaced by O(a sup k ), where k is the number of bit locations in the answer that are actually inspected in the reconstruction. A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction I´ of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions. In this work we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p^ I©(I´d) on the length of linear 2-query LCCs over @math , that encode messages of length d. Our bound improves over the known bound of $2^ I©(I´d) GKST06, KdW04, DS07 which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in theoretical computer science. Corollaries of our main theorem are new incidence geometry results over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields SS10 and the second is a new analog of Beck's theorem over finite fields. 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 2 + ? by an algorithm reading 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.