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.