Speaker: Ilan Newman (Haifa)

Title:  Some recent results on sublinear algorithms for graph related properties

Abstract:
I will describe property testing of (di)graph properties in bounded degree graph models, and talk about a characterization of the 1-sided error testable monotone graph properties and the 1-sided error testable hereditary graph properties in this model. I will introduce the notion of configuration-free properties and talk about some graph theoretic open problems.

 No prior knowledge of property testing is required.