DocumentCode :
580004
Title :
Sparse Affine-Invariant Linear Codes Are Locally Testable
Author :
Ben-Sasson, Eli ; Ron-Zewi, Noga ; Sudan, Madhu
Author_Institution :
Dept. of Comput. Sci., Technion - Israel Inst. of Technol., Haifa, Israel
fYear :
2012
fDate :
20-23 Oct. 2012
Firstpage :
561
Lastpage :
570
Abstract :
We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field Fq and an extension field Fqn, a property is a set of functions mapping Fqn to Fq. The property is said to be affine-invariant if it is invariant under affine transformations of Fqn, and it is said to be sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. [RANDOM 2009] and followed by Kaufman and Lovett [FOCS 2011]. The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.
Keywords :
computational complexity; linear codes; number theory; randomised algorithms; set theory; affine transformations; arbitrary finite fields; finite sets; functions mapping; locally testable; nonprime cases; nontrivial cases; property testing; sparse affine-invariant linear codes; sparse affine-invariant linear properties; Additives; Calculus; Computer science; Context; Electronic mail; Orbits; Testing; Additive Combinatorics; Affine Invariance; Locally Testable Codes; Sum-product Estimates;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
Conference_Location :
New Brunswick, NJ
ISSN :
0272-5428
Print_ISBN :
978-1-4673-4383-1
Type :
conf
DOI :
10.1109/FOCS.2012.38
Filename :
6375335
Link To Document :
بازگشت