Very Fast Approximation Algorithms for Big Graphs

Sublinear-time algorithms attempt to infer information from a data set by accessing only a miniscule fraction of it. I will present examples of such algorithms with a particular focus on algorithms for approximating graph parameters. I will show a local computation technique that can be used to transform many classic greedy algorithms into sublinear-time algorithms. One example is an algorithm that computes a good additive approximation to the size of the maximum matching in time that depends only on the average degree of the graph and not the total number of vertices. Another example is a near-optimal algorithm for approximating the vertex cover size that runs in sublinear time even for very dense graphs. Our techniques also find applications to property testing, distributed algorithms, and local computation algorithms.
Krzysztof Onak is a Simons Postdoctoral Fellow at Carnegie Mellon University. He received his Ph.D. degree from the Massachusetts Institute of Technology in 2010. He is mostly interested in computation with limited resources, including sublinear-time algorithms, property testing, and streaming algorithms.