Abstract:

My talk will focus on sublinear-time algorithms, which are my main research interest. As an example, I will address the following question.

Can computing the size of a solution to a combinatorial graph problem be faster than finding the solution itself? I will answer the question in the affirmative for multiple problems. For instance, I will present the first approximation algorithm that for the class of graphs with average degree bounded by d, computes the maximum matching size to within an additive epsilon*n in time that only depends on d and epsilon, and does not depend directly on n, where n is the number of vertices.

The vertex cover size and the minimum dominating set size cannot be approximated this well in time that does not depend on the number of vertices. Nevertheless, I will show that this is possible for a certain important class of graphs, namely the hyperfinite class of graphs, which include planar graphs and graphs of subexponential growth. Our techniques imply a simple proof of the result of Benjamini, Schramm, and Shapira (STOC 2008) that every minor-closed property of constant-degree graphs can be tested in constant time, and also yield constant-time algorithms for approximating the distance to hereditary properties in hyperfinite graphs. Finally, I will briefly talk about a few other problems in the sublinear-time computation model. I will use them to advertise the sublinear-time computation model as a useful tool for solving classical problems and understanding their hardness, as well as a great source of inspiration for other computation models.

Joint work with multiple authors whose names will be mentioned in the talk.