A Property Testing Double-Feature of Short Talks
Speaker: Oded Goldreich , Weizmann Institute of Science, Israel
Date: September 20 2011
Time: 4:15PM to 5:15PM
Location: 32-124
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: I will present two overview talks on the subject of property testing, preceeded by a brief introduction to the area. Abstracts of the two corresponding works, follow.
1. Testing Graph Blow-Up (joint work with Lidor Avigad)
Referring to the query complexity of testing graph properties in the adjacency matrix model, we advance the study of the class of properties that can be tested non-adaptively within complexity that is inversely proportional to the proximity parameter. Arguably, this is the lowest meaningful complexity class in this model, and we show that it contains a very natural class of graph properties. Specifically, for every fixed graph $H$, we consider the set of all graphs that are obtained by a (possibly unbalanced) blow-up of $H$.
2. Proximity Oblivious Testing and the Role of Invariances (joint work with Tali Kaufman)
We present a general notion of properties that are characterized by local conditions that are invariant under a sufficiently rich class of symmetries. Our framework generalizes two popular models of testing graph properties as well as the algebraic invariances studied by Kaufman and Sudan (STOC'08). Our focus is on the case that the property is characterized by a constant number of local conditions and a rich set of invariances. We show that, in the aforementioned models of testing graph properties, characterization by such invariant local conditions is closely related to proximity oblivious testing (as defined by Goldreich and Ron, STOC'09). In contrast to this relation, we show that, in general, characterization by invariant local conditions is neither necessary nor sufficient for proximity oblivious testing.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in September 2011
