Ronitt Rubinfeld, Massachusetts Institute of Technology

Abstract

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 generating random objects.

Bio:
Ronitt Rubinfeld is the Edwin Sibley Webster Professor in MIT's Electrical Engineering and Computer Science department, where she has been on the faculty since 2004.   She has held faculty positions at Cornell University and Tel Aviv University, and has been a member of the research staff at NEC Research Institute.
Ronitt's research centers on property testing and sub-linear time algorithms, that provide the foundations for measuring the performance of algorithms that analyze data by looking at only a very small portion of it. Her work has developed the field of sublinear time *property testers* functions, combinatorial objects and distributions.
Ronitt received her PhD from the University of California, Berkeley. Ronitt Rubinfeld was an ONR Young Investigator, a Sloan Fellow, and an invited speaker at the Internal Congress of Mathematics in 2006. She is a fellow of the ACM and of the American Academy of Arts and Sciences.

**Please note special time 4:00PM

Presented Via Zoom: https://rutgers.zoom.us/j/95942717079

Meeting ID: 959 4271 7079

Password: 567797