Description:
A common thread in all the recent results concerning testing dense graphs is the use of Szemer\'edi's regularity lemma. Asaf Shapira of the School of Computer Science at Tel Aviv University shows that in some sense, this is not a coincidence. In this examination of property-testing, Shapira delves into testing for Szemeredi-partitions while resolving one of the main open problems in the area of property-testing.
Speaker(s):
Asaf Shapira, Ph.D. candidate, School of Computer Science, Tel Aviv University
|
