Theory of Computing
-------------------
Title     : Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals
Authors   : Zeev Dvir, Shubhangi Saraf, and Avi Wigderson
Volume    : 13
Number    : 11
Pages     : 1-36
URL       : https://theoryofcomputing.org/articles/v013a011

Abstract
--------

We prove that 3-query linear locally correctable codes of dimension
$d$ over the reals require block length $n > d^{2+\alpha}$ for some
fixed, positive $\alpha > 0$. Geometrically, this means that if $n$
vectors in $R^d$ are such that each vector is spanned by a linear
number of disjoint triples of others, then it must be that 
$n > d^{2+\alpha}$. This improves the known quadratic lower bounds 
(e.g., Kerenidis--de Wolf (2004), Woodruff (2007)). While the
improvement is modest, we expect that the new techniques introduced
in this article will be useful for further progress on lower bounds
of locally correctable and decodable codes with more than 2 queries,
possibly over other fields as well.

Several of the new ideas in the proof work over every field. At a high
level, our proof has two parts, _clustering_ and _random restriction_.

The clustering step uses a powerful theorem of Barthe from convex
geometry. It can be used (after preprocessing our LCC to be
_balanced_), to apply a basis change (and rescaling) of the vectors,
so that the resulting unit vectors become _nearly isotropic_. This
together with the fact that any LCC must have many `correlated' pairs
of points, lets us deduce that the vectors must have a surprisingly
strong geometric clustering, and hence also combinatorial clustering
with respect to the spanning triples.

In the restriction step, we devise a new variant of the dimension
reduction technique used in previous lower bounds, which is able to
take advantage of the combinatorial clustering structure above. The
analysis of our random projection method reduces to a simple (weakly)
random graph process, and works over any field.

---

An extended abstract of this paper appeared in the
Proceedings of of the Forty-sixth Annual ACM Symposium 
on Theory of Computing (STOC 2014).