Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-166 | 28th November 2013 21:37

On testing affine-invariant properties

RSS-Feed




TR13-166
Authors: Arnab Bhattacharyya
Publication: 28th November 2013 23:54
Downloads: 3492
Keywords: 


Abstract:

An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has seen rapid progress in characterizing the affine-invariant properties which are testable with a constant number of queries. We survey the current state of this project.



ISSN 1433-8092 | Imprint