Theory Seminar: On the Semantics of Local Characterizations for Linear-Invariant Properties

Speaker:
Jakob Nordstrom (KTH Royal Institute of Technology)
Date:
Wednesday, 8.12.2010, 12:30
Place:
Room 337-8 Taub Bld.

A property of functions on a vector space is said to be linear-invariant if it is closed under linear transformations of the domain. Linear-invariant properties are some of the most well-studied properties in the field of property testing. Testable linear-invariant properties can always be characterized by so-called local constraints, and of late there has been a rapidly developing body of research investigating the testability of linear-invariant properties in terms of their descriptions using such local constraints. One problematic aspect that has been l argely ignored in this line of research, however, is that syntactically distinct local characterizations need not at all correspond to semantically distinct properties.

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

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

Back to the index of events