›› 2012, Vol. 27 ›› Issue (4): 678-686.doi: 10.1007/s11390-012-1254-8

• Special Section on Theoretical Computer Science • Previous Articles     Next Articles

A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field

David P. Woodruff   

  1. IBM Almaden Research Center, Yorktown Heights, N.Y. 10598, U.S.A.
  • Received:2011-03-16 Revised:2012-02-09 Online:2012-07-05 Published:2012-07-05

A linear (q, δ, ?, m(n))-locally decodable code (LDC) C:Fn→Fm(n) is a linear transformation from the vector space Fn to the space Fm(n) for which each message symbol xi 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)=Ω(n2) lower bound for linear 3-query LDCs over any, possibly infinite, field. The constant in the Ω(·) depends only on ? and δ. This is the first lower bound better than the trivial m(n)=Ω(n) for arbitrary fields and more than two queries.

[1] Sipser M, Spielman D A. Expander codes. IEEE Trans. Inform.Theory, 1996, 42(6): 1710-1722.

[2] Katz J, Trevisan L. On the efficiency of local decoding proceduresfor error-correcting codes. In Proc. the 32d STOC,May 2000, pp.80-86.

[3] Goldreich O, Karloff H J, Schulman L J, Trevisan L. Lowerbounds for linear locally decodable codes and private informationretrieval. In Proc. the 17th CCC, May 2002, pp.175-183.

[4] Trevisan L. Some applications of coding theory in computationalcomplexity. Quaderni di Matematica, 2004, 13: 347-424.

[5] Yekhanin S. Locally decodable codes and private informationretrieval schemes [PhD thesis]. MIT, 2007.

[6] Candès E J, Romberg J K, Tao T. Robust uncertainty principles:Exact signal reconstruction from highly incompletefrequency information. IEEE Transactions on InformationTheory, 2006, 52(2): 489-509.

[7] Donoho D L. Compressed sensing. IEEE Transactions onInformation Theory, 2006, 52(4): 1289-1306.

[8] Duarte M, Davenport M, Takhar D, Laska J, Sun T, KellyK, Baraniuk R. Single-pixel imaging via compressing sensing.IEEE Signal Processing Magazine, 2008, 25(2): 83-91.

[9] Dvir Z, Shpilka A. Locally decodable codes with 2 queries andpolynomial identity testing for depth 3 circuits. In Proc. the37th Symposium on the Theory of Computing (STOC), May2005, pp.592-601.

[10] Dvir Z. On matrix rigidity and locally self-correctable codes.In Proc. the 25th IEEE Conference on Computational Complexity(CCC), June 2010, pp.291-298.

[11] Valiant L G. Graph-theoretic arguments in low-level complexity.In Proc. the 6th MFCS, Sept. 1977, pp.162-176.

[12] Kerenidis I, de Wolf R. Exponential lower bound for 2-querylocally decodable codes. In Proc. the 35th STOC, June 2003,pp.106-115.

[13] Woodruff D P. New lower bounds for general locally decodablecodes. Electronic Colloquium on ComputationalComplexity (ECCC), 2007, http://eccc.hpi-web.de/ecccreports/2007/TR07-006/index.html.

[14] Gàl A, Mills A. Three-query locally decodable codes withhigher correctness require exponential length. Transactionson Computation Theory, 2012, 2012, 3(2): Article No.5.

[15] Obata K. Optimal lower bounds for 2-query locally decodablelinear codes. In Proc. the 6th APPROX-RANDOM,Sept. 2002, pp.39-50.

[16] Woodruff D P. Corruption and recovery-efficient locally decodablecodes. In Proc. APPROX-RANDOM, Aug. 2008,pp.584-595.

[17] Efremenko K. 3-query locally decodable codes of subexponentiallength. In Proc. the 41st STOC, May 31-June 2, 2009,pp.39-44.

[18] Itoh T, Suzuki Y. New constructions for query-efficient locallydecodable codes of subexponential length. Transactionon Information and Systems, 2010, E93-D(2): 263-270.

[19] Yekhanin S. Towards 3-query locally decodable codes ofsubexponential length. J. ACM, 2008, 55(1): 1-16.

[20] Dvir Z, Gopalan P, Yekhanin S. Matching vector codes.Electronic Colloquium on Computational Complexity, 2010,http://eccc.hpi-web.de/report/2010/012/.

[21] Gopalan P. A note on Efremenko’s locally decodable codes.Electronic Colloquium on Computational Complexity, 2009,http://eccc.hpi-web.de/report/2009/069/.

[22] Diestel R. Graph theory (Graduate Texts in Mathematics).Springer-Verlag, 2005.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Jin Lan; Yang Yuanyuan;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[2] Fan Zhihua;. Vectorization for Loops with Three-Forked Jumps[J]. , 1988, 3(3): 186 -202 .
[3] Guo Qingping; Y. Paker;. Communication Analysis and Granularity Assessment for a Transputer-Based System[J]. , 1990, 5(4): 347 -362 .
[4] Zhou Yong; Tang Zesheng;. Constructing Isosurfaces from 3D Data Sets Taking Account of Depth Sorting of Polyhedra[J]. , 1994, 9(2): 117 -127 .
[5] Liao Lejian; Shi Zhongzhi;. Minimal Model Semantics for Sorted Constraint Representation[J]. , 1995, 10(5): 439 -446 .
[6] Zhao Yu; Zhang Qiong; Xiang Hui; Shi Jiaosing; He Zhijun;. A Simplified Model for Generating 3D Realistic Sound in the Multimedia and Virtual Reality Systems[J]. , 1996, 11(4): 461 -470 .
[7] Zhu Zhigang; Xu Guangyou;. Neural Networks for Omni-View Road Image Understanding[J]. , 1996, 11(6): 570 -580 .
[8] Wang Yun; Gu Guanqun; Dui Jiyin;. Research on Protocol Migration[J]. , 1996, 11(6): 601 -606 .
[9] Cheng Qi; Zhu Hong;. MNP: A Class of NP Optimization Problems[J]. , 1997, 12(4): 306 -313 .
[10] Mi Thxi;. Constructive Sets in Computable Sets[J]. , 1997, 12(5): 425 -440 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved