The Taub Faculty of Computer Science Events and Talks

Property testing algorithms are required to discern between inputs with some property and inputs far from having the property, by only making very few queries into the input. The number of queries used by a property testing algorithm is its query complexity. For many properties we have strong lower bounds for the query complexity, but these properties can be decomposed into few sub-properties for which we do have property testing algorithms with low query complexity. In this talk we will try to answer the following questions: - How good can these decompositions be? (very good) - Can all properties be decomposed in this manner? (no) - Suppose we have such a decomposition, does it tell us something about the property? (yes, under some conditions)