דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Algorithms for Property Testing and Related Problems
event speaker icon
יונתן גולדהירש, הרצאה סמינריונית לדוקטורט
event date icon
יום רביעי, 14.5.2014, 14:30
event location icon
טאוב 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)
[בחזרה לאינדקס האירועים]