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


Algorithms for Property Testing and Related Problems
event speaker icon
Yonatan Goldhirsh, Ph.D. Thesis Seminar
event date icon
Wednesday, 14.5.2014, 14:30
event location icon
Taub 601
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)
[Back to the index of events]