Combinatorics Seminar

When: Sunday, Dec. 26, 10am Where: Schreiber 309 Speaker: Asaf Shapira, Tel Aviv University Title: Extremal graphs, recursive functions and a separation theorem in property testing

Abstract:

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.