PACM Colloquium: Ronitt Rubinfeld, MIT and Tel Aviv University

Mon, Apr 1, 2019, 4:00 pm

Local algorithms for sparse connected subgraphs

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 survey a series of results on local computation algorithms for finding sparse connected subgraphs and sparse spanners.

Ronitt's research interests are in sub-linear time algorithms for discrete distributions over large domains and for combinatorial problems on large inputs. Ronitt is an ACM Fellow and was an invited speaker at the 2006 International Congress of Mathematicians.   Ronitt earned her PhD in Computer Science from U.C. Berkeley.

214 Fine Hall
Event category: 

Upcoming Events

ANALYSIS OF FLUIDS AND RELATED TOPICS: Turbulent solutions of fluid equations: Alexey Cheskidov, University of Illinois at Chicago

PACM Colloquium, Prof. Lin Lin, UC Berkeley University

Mon, Feb 6, 2023, 4:30 pm
Location: 214 Fine Hall

ANALYSIS OF FLUIDS AND RELATED TOPICS: Kevin Zumbrun, Indiana University

Thu, Feb 9, 2023, 3:00 pm
Location: Fine Hall 314