ECCC-Report TR07-006https://eccc.weizmann.ac.il/report/2007/006Comments and Revisions published for TR07-006en-usThu, 18 Jan 2007 13:23:03 +0200
Paper TR07-006
| New Lower Bounds for General Locally Decodable Codes |
David P. Woodruff
https://eccc.weizmann.ac.il/report/2007/006For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For linear 3-query locally decodable codes C: F^n -> F^m, we improve the lower bound further to Omega(n^2/log log n), and our bound holds for any (possibly infinite) field F. Previously, the best lower bound for this case was Omega(n^2/log^2 n), and held only for constant-sized F. We are not aware of any previous non-trivial lower bounds for large F and q > 2 queries.
Our proofs use a random restriction of the message, hypergraph arguments, a new reduction from a q-query code to a generalization of a 2-query code, and quantum arguments. For linear codes our proofs are completely elementary. We work with random linear projections and use additional structure in the hypercube. The idea of using a random restriction (or projection for linear codes) is new in this context, and may be a powerful technique for future work.
Thu, 18 Jan 2007 13:23:03 +0200https://eccc.weizmann.ac.il/report/2007/006