Events Calendar

YINS Visiting Lecturer: Ronitt Rubinfeld (MIT)

YINS Visiting Lecturer: Ronitt Rubinfeld (MIT)

Event time: 
Wednesday, February 28, 2018 - 12:00pm to 1:00pm
Yale Institute for Network Science See map
17 Hillhouse Ave, 3rd floor
New Haven, CT 06511
Event description: 

“Local computation algorithms”

Speaker:  Ronitt Rubinfeld
Professor of Electrical Engineering and Computer Science, MIT
Professor of Computer Sciences at Tel Aviv University, Israel

Talk Summary: 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 theoutput 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 orderto 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.

Speaker Bio: Ronitt Rubinfeld joined the MIT faculty in 2004, and is on the faculty at the University of Tel Aviv.  Her research interests include sublinear time algorithms, local algorithms and algorithms for testing discrete distributions over large domains.    Ronitt Rubinfeld has been an ONR Young Investigator, a Sloan Fellow, an invited speaker at the Internal Congress of Mathematics (2006) and an ACM Fellow.