11/29/2016 Colin Robertson, CS @ ILLINOIS
Dr. Ronitt Rubinfeld will describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed.
Written by Colin Robertson, CS @ ILLINOIS
Is it really necessary to solve the entire computational problem, if one is only interested in small parts of the output at any given time? Is it even necessary to view the whole input? In the Donald B. Gillies Memorial Lecture in Computer Science, Professor Ronitt Rubinfeld will survey recent work in local computational algorithms, describing results on a variety of problems for which sublinear time and space local computation algorithms have been developed. The lecture will take place at 4 pm on December 5, in 2405 Siebel Center. A live stream of this talk will be available at go.cs.illinois.edu/Gillies2016.
Local Computation Algorithms
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.
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.
Bio: Ronitt Rubinfeld joined the MIT faculty in 2004, and is on the faculty at the University of Tel Aviv. Her research interests include randomized algorithms and computational complexity. She co-initiated the fields of Property Testing and Sub-linear time algorithms, providing the foundations for measuring the performance of algorithms that analyze data without looking at all of it. In particular, her work on Linearity Testing has helped build a bridge between Computational Complexity, Analysis of Boolean Functions, and Additive Combinatorics. Rubinfeld has been an ONR Young Investigator, a Sloan Fellow, an invited speaker at the 2006 International Congress of Mathematicians, and is an ACM Fellow.
About the Donald B. Gillies Memorial Lecture
The Lecture honors the memory of Professor Donald B. Gillies. He was among the first mathematicians to become involved in the computer field, helping to calculate the first Sputnik orbit and later discovering three new prime numbers in the course of checking out ILLIAC II. Before his death in 1975, he was experimenting with educational uses and networking possibilities of minicomputers. See the webpage for additional information.