Testing Low Complexity Affine-Invariant Properties

Understand

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties.

• In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries.
• This immediately reproves, for instance, that the Reed-Muller code over F_p of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials except that low degree is preserved by composition with affine maps.
• The complexity of an affine-invariant property P refers to the maximum complexity, as defined by Green and Tao (Ann.