Asaf Shapira: Efficient graph property testing

Abstract: Results from around 10 years ago more or less determined which graph properties can be tested with a constant number of queries. However, in most cases the “constants” involves were enormous. This naturally leads to the problem, raised by Goldreich in 2005 and more recently by Alon and Fox, of deciding which properties can be tested with a polynomial number of queries. In this talk I will describe several results related to this problem.

Based on joint works with L. Gishboliner