## Sublinear Graph Approximation Algorithms

by Krzysztof Onak, based on joint works with Noga Alon, Avinatan Hassidim, Jonathan A. Kelner, Philip N. Klein, and Huy N. Nguyen.

Can the size of a solution to a graph problem be computed faster than the solution itself? I will show that the answer to this question is positive in many cases. For example, I will present an approximation algorithm that for the class of graphs with degree bounded by d, computes the maximum matching size to within $\epsilon * n$ in time that only depends on $d$ and $\epsilon$. I will give an overview of all known results, including some work still in progress.