Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Algorithms for Property Testing and Related Problems
event speaker icon
Yonatan Goldhirsh (Ph.D. Thesis Seminar)
event date icon
Wednesday, 14.05.2014, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Assoc. Prof. Eldar Fischer
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)