For 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.