Dana Ron - On Sublinear Algorithms for Approximating Graph Parameters - Technion lecture

Dana Ron of Tel Aviv University, Technion lecture: On Sublinear Algorithms for Approximating Graph Parameters

When we refer to efficient algorithms, we usually mean polynomial-time algorithms. In particular this is true for graph algorithms, which are considered efficient if they run in time polynomial in the number of vertices and edges of the graph.

However, when considering very large graphs we seek even more efficient algorithms whose running time is sublinear in the size of the input graph.
Such algorithms do not even read the whole entire graph, but rather sample random parts of the graph and compute approximations of various parameters of interest.
In this talk I will survey various such algorithms.