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.