"Testing linear-invariant properties"
Jonathan Tidor (MIT)
Monday, November 29th 2021, 2-3pm
Abstract:
We study the property testing of linear-invariant properties, i.e., properties of functions on a finite field vector space that are preserved under linear automorphisms of the domain. We completely classify the properties that are testable with a constant number of queries to the function and with one-sided error.
This result can be viewed as the arithmetic analogue of Alon and Shapira's classification of testable graph properties. Similar to their result we use regularity-based techniques, specifically an extension of the higher-order Fourier analytic techniques developed earlier by Bhattacharyya, Fischer, Hatami, Hatami, and Lovett. However, regularity-based techniques are known not to be strong enough to solve the full problem. To overcome this barrier, we introduce a novel Ramsey-theoretic technique that we call patching.
Based on joint work with Jacob Fox and Yufei Zhao