Extremal graphs, recursive functions and a separation theorem in property testing

COMPUTER SCIENCE/DISCRETE MATH SEMINAR, I
Topic:Extremal graphs, recursive functions and a separation theorem in property testing
Speaker:Asaf Shapira
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.