The Taub Faculty of Computer Science Events and Talks

A property of functions on a vector space is said to be linear-invariantif it is closed under linear transformations of the domain.Linear-invariant properties are some of the most well-studied propertiesin the field of property testing. Testable linear-invariant propertiescan always be characterized by so-called local constraints, and of latethere has been a rapidly developing body of research investigating thetestability of linear-invariant properties in terms of their descriptionsusing such local constraints. One problematic aspect that has been l argelyignored in this line of research, however, is that syntactically distinctlocal characterizations need not at all correspond to semanticallydistinct properties.

In fact, there are known fairly dramatic exampleswhere seemingly infinite families of properties collapse into a smallfinite set that was already well-understood.In this work, we therefore initiate a systematic study of the semantics oflocal characterizations of linear-invariant properties. For suchproperties the local characterizations have an especially nice structurein terms of forbidden patterns on linearly dependent sets of vectors,which can be encoded formally as matroid constraints. We developtechniques for determining, given two such matroid constraints, whetherthese constraints encode identical or distinct properties, and show for afairly broad class of properties that these techniques provide necessaryand sufficient conditions for deciding between the two cases. We usethese tools to show that recent ( yntactic) testability results indeedprovide an infinite number of infinite strict hierarchies of)semantically) distinct testable locally characterized linear-invariantproperties.

Joint work with Arnab Bhattacharyya, Elena Grigorescu, and Ning Xie