Computer Science/Discrete Mathematics Seminar II

A Property P of functions is said to be testable if there exists a probabilistic algorithm that makes few (constant) queries for the value of f and accepts those satisfying P while rejecting functions that are far from any function satisfying P. In this work we investigate property testing for algebraic properties with the aim of finding a broad class of properties that are locally testable. We consider functions mapping a vector space over a field F to the field. The class of properties we consider are those that are closed under linear-transformations. We show all such properties are testable, whenever they are characterized by local constraints ("local characterization"). This unifies previous results in linearity testing, low-degree testing, and testing of Reed-Muller codes. We then turn to analyzing the locality of characterizations of linear-invariant families. We show some function families of *high*-degree polynomials that possess very local characterizations (and hence are testable). We also investigate the general class of linear-invariant families and give a broad structural characterization for them. These turn into coarse bounds on their local characterizability. For instance, we show that affine-invariant families possess a local characterization if and only if they possess a local constraint. This result provides support to the general conjecture that function families that are "two-transitive" and have a local constraint are locally testable. Joint work with Madhu Sudan (MIT)