Asaf Shapira: Efficient graph property testing

Tuesday, February 6, 2018 - 4:00pm to 5:00pm
Light Refreshments at 3:45pm
Patil/Kiva G449
Asaf Shapira, Tel Aviv University

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