Arnab has put together a wonderful survey on testing affine-invariant properties (ECCC). Consider functions \(f:\mathbb{F}^n_p \to R\) (where \(R\) is usually a finite range). A property is called affine-invariant if it closed under affine transformations of the domain. The classic example of such a property is that of being a low-degree polynomial. This is a very rich and beautiful area of research, with the initial inspiration being work in trying to understand what makes a property testable. I will also add that this is a deep (somewhat inaccessible to the non-expert?) area of research, so thanks Arnab for this excellent survey!
Survey on Testing Affine-Invariant Properties
Leave a reply