TY - GEN

T1 - Breaking the quadratic barrier for 3-LCC's over the Reals

AU - Dvir, Zeev

AU - Saraf, Shubhangi

AU - Wigderson, Avi

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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. At a high level, our proof has two parts, clustering and random restriction. The clustering step uses a powerful geometric theorem of Barthe which finds a basis change (and rescaling) putting the code in nearly isotropic position. 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.

AB - 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. At a high level, our proof has two parts, clustering and random restriction. The clustering step uses a powerful geometric theorem of Barthe which finds a basis change (and rescaling) putting the code in nearly isotropic position. 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.

UR - http://www.scopus.com/inward/record.url?scp=84904353579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904353579&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591818

DO - 10.1145/2591796.2591818

M3 - Conference contribution

AN - SCOPUS:84904353579

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 784

EP - 793

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -