Local Computation Algorithms
Ronitt Rubinfeld, MIT and Tel Aviv University
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of “local computation algorithms” which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms.
In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed — we will give special focus to finding maximal independent sets and sparse spanning graphs.
Biography: Ronitt Rubinfeld is a professor of Electrical Engineering and Computer Science at MIT and a professor of Computer Science at Tel-Aviv University. Her research interests include randomized algorithms and computational complexity. She works in the fields of Property Testing and Sub-linear Time Algorithms, which provide the foundations for measuring the performance of algorithms that analyze data without looking at all of it. Ronitt Rubinfeld was an invited speaker at the International Congress of Mathematicians in 2006 and is an ACM Fellow.