Testing low complexity affine-invariant properties
From MaRDI portal
Abstract: 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. Math. 2008), of the sets of linear forms used to characterize P. A more precise statement of our main result is that for any fixed prime p >=2 and fixed integer R >= 2, any affine-invariant property P of functions f: F_p^n -> [R] is testable, assuming the complexity of the property is less than p. Our proof involves developing analogs of graph-theoretic techniques in an algebraic setting, using tools from higher-order Fourier analysis.
Recommendations
Cited in
(18)- 2-transitivity is insufficient for local testability
- Sparse affine-invariant linear codes are locally testable
- Correlation testing for affine invariant properties on \(\mathbb{F}_p^n\) in the high error regime
- Characterizations of locally testable linear- and affine-invariant families
- On Sums of Locally Testable Affine Invariant Properties
- Algebraic property testing: the role of invariance
- Invariance in property testing
- Optimal testing of Reed-Muller codes
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Testing Linear-Invariant Properties
- Reducing Testing Affine Spaces to Testing Linearity of Functions
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- A characterization of locally testable affine-invariant properties via decomposition theorems
- Correlation testing for affine invariant properties on F p n in the high error regime
- Every locally characterized affine-invariant property is testable
- General systems of linear forms: equidistribution and true complexity
- The Gowers U₃ norm of five classes of power permutations
- Characterizations of locally testable linear- and affine-invariant families
This page was built for publication: Testing low complexity affine-invariant properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741806)
