Title: Every Monotone Graph Property is Testable
Speaker: Asaf Shapira
Date: February 1, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
A graph property is called monotone if it is closed under taking (not necessarily induced) subgraphs. In this talk I will present a recent result in which we show that any monotone graph property can be tested with one-sided error, and with query complexity depending only on \epsilon. This result unifies several previous results in the area of property testing, and also implies the testability of well-studied graph properties that were previously not known to be testable. At the heart of the proof is an application of a new variant of Szemeredi's Regularity Lemma. I will also describe some additional interesting applications of the above result in Extremal Graph-Theory and Property-Testing.
Joint work with Noga Alon.