Krzysztof Onak (IBM TJ Watson Research Center)
Random Local Exploration Techniques for Sublinear-Time Algorithms

Abstract: I will introduce a number of local random exploration
techniques with applications to property testing and sublinear-time
estimation algorithms. First, I will discuss random greedy exploration
and show how it can be used to approximate the size of the optimal
solution for maximum matching, minimum vertex cover, and other
problems that can be approximated using greedy algorithms. Then I will
introduce local partitioning oracles and show how to use them to
construct simple algorithms for testing planarity in bounded-degree
graphs and testing an arbitrary property of bounded-degree planar
graphs. Finally, I will briefly discuss random walks and the role they
play in algorithms for testing bipartiteness, graph expansion, and
clusterability.