We consider the question of whether adaptivity can improve the complexity of  property testing algorithms in the dense graphs model. It is well known that there can be at most a quadratic gap between adaptive and non-adaptive testers in this model, but it was not known whether any gap indeed exists. In this this talk I will discuss such gaps for several properties, amongst them bipartiteness.

In addition to demonstrating that adaptivity can play a role in the dense-graphs model, these results show that testing in the dense-graphs model is not only a question of combinatorITCS. Rather, in some cases, in order to obtain better bounds on the query complexity, algorithmic aspects should come into play.

Biography

Dana Ron is an Associate Professor in the School of Electrical Engineering at Tel Aviv University, Israel. She received her B.A., M.Sc., and Ph.D. from the Hebrew University in 1987, 1989, and 1995, respectively. She was an NSF postdoctoral fellow at MIT between 1995 and 1997, and a Bunting Fellow (ONR Science Scholar) at MIT and Radcliffe during 1997/8. She joined the faculty of Tel Aviv University in 1998. Her research interest includes randomized approximation algorithms and in particular sublinear algorithms.

Back