Thoughts on LDC's

Zeev’s thoughts

I was thinking a bit about the 2 query case (proving lower bounds). If we define the decoding map for 2-LCC we get a quadratic map Q from R^n to R^n sending the codewords (in +-1) to themselves. Now, the Jacobian of this map can be written (I think) as a combination of permutation matrices with coefficients that are the x_i. Using standard matrix chernoff/Bernstein bounds (see here: http://users.cms.caltech.edu/~jtropp/books/Tro14-Introduction-Matrix-FnTML-rev.pdf) I think you can show that the Jacobian has tiny norm almost everywhere. Which means that, to contain all the codewords, the image of Q must look very `spiky’ (it has small volume but contains a code). But then I started thinking that maybe we can use the fact that it is a low degree mapping to show that it cannot be too spiky. A quick google search came up with this paper:

http://www.math.lsa.umich.edu/~barvinok/product.pdf

Which is not exactly what we need, but seems in the right direction (and uses tools we already discussed before). If it works, this has some chance to generalize to degree 3 maps as well (not using the same tools but maybe something more sophisticated from real AG).