Bhattacharyya, Arnab ;
Gopi, Sivakanth
Lower Bounds for Constant Query AffineInvariant LCCs and LTCs
Abstract
Affineinvariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, wellstudied class of codes; they include popular codes such as ReedMuller and ReedSolomon. A particularly appealing feature of affineinvariant codes is that they seem wellsuited to admit local correctors and testers.
In this work, we give lower bounds on the length of locally correctable and locally testable affineinvariant codes with constant query complexity. We show that if a code C subset Sigma^{K^n} is an rquery locally correctable code (LCC), where K is a finite field and Sigma is a finite alphabet, then the number of codewords in C is at most exp(O_{K, r, Sigma}(n^{r1})). Also, we show that if C subset Sigma^{K^n} is an rquery locally testable code (LTC), then the number of codewords in C is at most \exp(O_{K, r, Sigma}(n^{r2})). The dependence on n in these bounds is tight for constantquery LCCs/LTCs, since Guo, Kopparty and Sudan (ITCS 2013) construct affineinvariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for nonlinear codes, whereas previously, BenSasson and Sudan (RANDOM 2011) assumed linearity to derive similar results.
Our analysis uses higherorder Fourier analysis. In particular, we show that the codewords corresponding to an affineinvariant LCC/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems which approximate any bounded function in terms of a finite number of lowdegree nonclassical polynomials, upto a small error in the Gowers norm.
BibTeX  Entry
@InProceedings{bhattacharyya_et_al:LIPIcs:2016:5840,
author = {Arnab Bhattacharyya and Sivakanth Gopi},
title = {{Lower Bounds for Constant Query AffineInvariant LCCs and LTCs}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {12:112:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5840},
URN = {urn:nbn:de:0030drops58400},
doi = {10.4230/LIPIcs.CCC.2016.12},
annote = {Keywords: Locally correctable code, Locally testable code, Affine Invariance, Gowers uniformity norm}
}
19.05.2016
Keywords: 

Locally correctable code, Locally testable code, Affine Invariance, Gowers uniformity norm 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

19.05.2016 