Testing Linear-Invariant Properties
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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145888 |
| _version_ | 1826207606893445120 |
|---|---|
| author | Tidor, Jonathan Zhao, Yufei |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Tidor, Jonathan Zhao, Yufei |
| author_sort | Tidor, Jonathan |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:52:11Z |
| format | Article |
| id | mit-1721.1/145888 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:52:11Z |
| publishDate | 2022 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1458882022-10-19T03:19:46Z Testing Linear-Invariant Properties Tidor, Jonathan Zhao, Yufei Massachusetts Institute of Technology. Department of Mathematics 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. 2022-10-18T16:32:29Z 2022-10-18T16:32:29Z 2022-08 2022-10-18T16:23:40Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/145888 Tidor, Jonathan and Zhao, Yufei. 2022. "Testing Linear-Invariant Properties." SIAM Journal on Computing, 51 (4). en 10.1137/21m1397246 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Tidor, Jonathan Zhao, Yufei Testing Linear-Invariant Properties |
| title | Testing Linear-Invariant Properties |
| title_full | Testing Linear-Invariant Properties |
| title_fullStr | Testing Linear-Invariant Properties |
| title_full_unstemmed | Testing Linear-Invariant Properties |
| title_short | Testing Linear-Invariant Properties |
| title_sort | testing linear invariant properties |
| url | https://hdl.handle.net/1721.1/145888 |
| work_keys_str_mv | AT tidorjonathan testinglinearinvariantproperties AT zhaoyufei testinglinearinvariantproperties |