Back to Search
Start Over
Testing Linear-Invariant Properties
- Source :
- arXiv, FOCS
- Publication Year :
- 2022
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 2022.
-
Abstract
- Fix a prime $p$ and a positive integer $R$. We study the property testing of functions $\mathbb F_p^n\to[R]$. We say that a property is testable if there exists an oblivious tester for this property with one-sided error and constant query complexity. Furthermore, a property is proximity oblivious-testable (PO-testable) if the test is also independent of the proximity parameter $\epsilon$. It is known that a number of natural properties such as linearity and being a low degree polynomial are PO-testable. These properties are examples of linear-invariant properties, meaning that they are preserved under linear automorphisms of the domain. Following work of Kaufman and Sudan, the study of linear-invariant properties has been an important problem in arithmetic property testing. A central conjecture in this field, proposed by Bhattacharyya, Grigorescu, and Shapira, is that a linear-invariant property is testable if and only if it is semi subspace-hereditary. We prove two results, the first resolves this conjecture and the second classifies PO-testable properties. (1) A linear-invariant property is testable if and only if it is semi subspace-hereditary. (2) A linear-invariant property is PO-testable if and only if it is locally characterized. Our innovations are two-fold. We give a more powerful version of the compactness argument first introduced by Alon and Shapira. This relies on a new strong arithmetic regularity lemma in which one mixes different levels of Gowers uniformity. This allows us to extend the work of Bhattacharyya, Fischer, Hatami, Hatami, and Lovett by removing the bounded complexity restriction in their work. Our second innovation is a novel recoloring technique called patching. This Ramsey-theoretic technique is critical for working in the linear-invariant setting and allows us to remove the translation-invariant restriction present in previous work.<br />Comment: 40 pages; updated with significantly improved main result
- Subjects :
- FOS: Computer and information sciences
Property testing
Discrete mathematics
Conjecture
General Computer Science
General Mathematics
010102 general mathematics
Field (mathematics)
0102 computer and information sciences
Computational Complexity (cs.CC)
01 natural sciences
Prime (order theory)
Computer Science - Computational Complexity
Compact space
Integer
010201 computation theory & mathematics
Bounded function
FOS: Mathematics
Mathematics - Combinatorics
Degree of a polynomial
Combinatorics (math.CO)
0101 mathematics
Mathematics
Subjects
Details
- ISSN :
- 10957111 and 00975397
- Volume :
- 51
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Computing
- Accession number :
- edsair.doi.dedup.....049ec31abf84440c64530ad39434f725