Abstract
We study an approximate version of q-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A q-query (α,δ)-approximate LDC is a set V of n points in ℝd so that, for each i ∈ [d] there are Ω(δn) disjoint q-tuples (u 1,…,u q ) in V so that span(u 1,…,u q ) contains a unit vector whose i’th coordinate is at least α. We prove exponential lower bounds of the form \(n \geq 2^{\Omega(\alpha \delta \sqrt{d})}\) for the case q = 2 and, in some cases, stronger bounds (exponential in d).
The full version of this paper is available at http://arxiv.org/abs/1402.6952 .
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ai, A., Dvir, Z., Saraf, S., Wigderson, A.: Sylvester-Gallai type theorems for approximate collinearity. Forum of Mathematics, Sigma 4 (2014)
Ben-Aroya, A., Regev, O., de Wolf, R.: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In: FOCS 2008, pp. 477–486 (2008)
Barak, B., Dvir, Z., Wigderson, A., Yehudayoff, A.: Fractional Sylvester-Gallai theorems. Proceedings of the National Academy of Sciences (2012)
Ben-Aroya, A., Efremenko, K., Ta-Shma, A.: Local list decoding with a constant number of queries. In: FOCS 2010, pp. 715–722 (2010)
Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol. 415, pp. 37–48. Springer, Heidelberg (1990)
Blum, M., Kannan, S.: Designing programs that check their work. J. ACM 42(1), 269–291 (1995)
Briët, J., Naor, A., Regev, O.: Locally decodable codes and the failure of cotype for projective tensor products. Electronic Research Announcements in Mathematical Sciences (ERA-MS) 19, 120–130 (2012)
Chee, Y., Feng, T., Ling, S., Wang, H., Zhang, L.: Query-efficient locally decodable codes of subexponential length. ECCC, TR10-173 (2010)
Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. SIAM J. Comput. 40(4), 1154–1178 (2011)
Dvir, Z., Shpilka, A.: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In: STOC 2005, pp. 592–601 (2005)
Dvir, Z., Saraf, S., Wigderson, A.: Breaking the quadratic barrier for 3-LCCs over the reals. In: STOC 2014 (2014)
Dvir, Z., Saraf, S., Wigderson, A.: Improved rank bounds for design matrices and a new proof of Kelly’s theorem. Forum of Mathematics, Sigma 4 (2014)
Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC 2009, pp. 39–44 (2009)
Goldreich, O., Karloff, H., Schulman, L.J., Trevisan, L.: Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity 15(3), 263–296 (2006)
Itoh, T., Suzuki, Y.: Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions on Information and Systems E93-D(2), 263–270 (2010)
Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences 69(3), 395–420 (2004)
Kindler, G., Rao, A., O’Donnell, R., Wigdersons, A.: Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM 55(10), 90–97 (2012)
Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC 2000, pp. 80–86 (2000)
Kedlaya, K.S., Yekhanin, S.: Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. SIAM J. Comput. 38(5), 1952–1969 (2009)
Lipton, R.J.: Efficient checking of computations. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol. 415, pp. 207–215. Springer, Heidelberg (1990)
Raghavendra, P.: A note on Yekhanin’s locally decodable codes. ECCC, TR07-016 (2007)
Woodruff, D.P.: New lower bounds for general locally decodable codes. ECCC, TR07-006 (2007)
Woodruff, D.P.: A quadratic lower bound for three-query linear locally decodable codes over any field. Journal of Computer Science and Technology 27(4), 678–686 (2012)
Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. Journal of the ACM 55(1), 1–16 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Briët, J., Dvir, Z., Hu, G., Saraf, S. (2014). Lower Bounds for Approximate LDCs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)