|COMPUTER SCIENCE/DISCRETE MATH SEMINAR, I|
|Topic:||Extremal graphs, recursive functions and a separation theorem in property testing|
|Affiliation:||Tel Aviv University|
|Date:||Monday, January 31|
|Time/Room:||11:15am - 12:15pm/S-10|
A graph property P is said to be uniformly-testable if there is a property-tester for P that receives the error parameter \epsilon as part of the input, and whose query complexity is a function of \epsilon only. P is said to be non-uniformly-testable if for every fixed \epsilon there is a tester that distinguishes between graphs satisfying P from those that are \epsilon-far from satisfying it. In this talk I will describe a combinatorially natural graph property in coNP, which is non-uniformly-testable but cannot be uniformly tested. The proof combines results and arguments from Extremal Graph Theory, Property Testing and the theory of Recursive Functions. Joint work with Noga Alon.