Skip to main content

Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals

Author(s): Dvir, Zeev; Saraf, Shubhangi; Wigderson, Avi

To refer to this page use:
Abstract: We prove that 3-query linear locally correctable codes of dimension d over the reals require block length n>d2+α for some fixed, positive α>0. Geometrically, this means that if n vectors in ℝd 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., 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.
Publication Date: 2017
Citation: Dvir, Zeev, Shubhangi Saraf, and Avi Wigderson. "Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals." Theory of Computing 13, no. 11 (2017): pp. 1-36. doi:10.4086/toc.2017.v013a011
DOI: 10.4086/toc.2017.v013a011
ISSN: 1557-2862
Pages: 1 - 36
Type of Material: Journal Article
Journal/Proceeding Title: Theory of Computing
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.