Breaking the quadratic barrier for 3-LCC's over the reals
Zeev Dvir, Shubhangi Saraf, Avi Wigderson · 2014
We prove that 3-query linear locally correctable codes over the Reals of dimension d require block length n > d2+λ for some fixed, positive λ > 0. Geometrically, this means that if n vectors in Rd are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that n > d2+λ. This improves the known quadratic lower bounds (e.g. [20, 28]). While a modest improvement, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries.