Computer Science/Discrete Mathematics Seminar II

A Property P of functions is said to be locally 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. 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. Last week we have shown that all such properties are testable, whenever they are characterized by local constraints ("local characterization"). This week we'll try to understand when local characterization of linear-invariant families exists. We investigate the general class of linear-invariant families and give a broad structural characterization for them. These turn into coarse bounds on their local characterization. For instance, we show that affine-invariant families possess a local characterization if and only if they possess one local constraint. This result provides support to the general conjecture by Alon et al. that function families that are "two-transitive" and have a local constraint are locally testable. Joint work with Madhu Sudan (MIT) * This talk will be independent of the previous talk, i.e. I don't assume attendance in Part I of my talk.