[TITLE] On a connection between distributed algorithms and
sublinear-time algorithms
[SPEAKER] Krzysztof Onak (MIT)
[PLACE] 32-G631
[TIME] 1-2:30pm
[DATE] Friday April 16th, 2010 

[ABSTRACT]
I will present a line of research on sublinear-time algorithms that was
initiated by observing a connection to *local* distributed algorithms
(Parnas, Ron 2007). In particular, whenever there is a local distributed
approximation algorithm for a given graph problem, then there is a
constant-time algorithm that approximates the optimal solution size. 

Sample problems we will look at are vertex cover, maximum matching, and
dominating set. I will present techniques that were developed for sublinear
algorithms, and I will show how the research on sublinear algorithms
contributes back to the research on distributed algorithms.