check
Combinatorics: Ilan Newman (Haifa) | Einstein Institute of Mathematics

Combinatorics: Ilan Newman (Haifa)

Date: 
Mon, 09/12/201910:00-12:00
Location: 
C-400, CS building

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.