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.
Another related notion is that of @cite_21 , which are, loosely speaking, codes for which there exists a probabilistic algorithm that accepts valid codewords, and rejects inputs that are far'' in Hamming distance from any codeword, while only probing a small fraction of the input. Much stronger upper bounds are known for locally testable codes than for LDCs, and in particular, there exists @math -local LTCs with blocklength @math @cite_21 (see also @cite_22 @cite_4 ). It is also known that LDCs do imply locally testable codes and vice versa @cite_12 .
@cite_21 @cite_4 @cite_22 @cite_12
2010510058 2550164695 1966671033 2770063945
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. 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. An error-correcting code C is called (q, ϵ)-strong locally testable code (LTC) if there exists a tester that makes at most q queries to the input word. This tester accepts all code words with probability 1 and rejects all non-code words x with probability at least ϵ · δ(x, C), where δ(x, C) denotes the relative Hamming distance between the word x and the code C. The parameter q is called the query complexity and the parameter ϵ is called soundness. In this paper we resolve an open question raised by Gold Reich and Sudan (J. ACM 2006) and construct binary linear strong LTCs with query complexity 3, constant relative distance, constant soundness and inverse polylogarithmic rate. Our result is based on the previous paper of the author (Vide man, ECCC TR12-168), which presented binary linear strong LTCs with query complexity 3, constant relative distance, and inverse polylogarithmic soundness and rate. We show that the "gap amplification" procedure of Dinur (J. ACM 2007) can be used to amplify the soundness of these strong LTCs from inverse polylogarithmic up to a constant, while preserving the other parameters of these codes. Furthermore, we show that under a conceivable conjecture, there exist asymptotically good strong LTCs with poly-log query complexity. 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.