Lower bounds for locally decodable codes

A binary q-query locally decodable code (q-LDC) encodes a k-bit binary message into a n-bit binary codeword, such that given any codeword y and coordinate 1<=i<=k, we can query up to q coordinates of y and recover the i-th bit of the original message with probability strictly greater than 1/2. Finding the optimal tradeoff between the length k of the messages and the length n of the shortest possible encoding satisfying the q-LDC property is a longstanding open problem. We will show a bound of k<=O(n^{1-2/q}) for all q>=3 using the Kikuchi matrix method.