Ronitt Rubinfeld: Local Computation Algorithms

Speaker: Ronitt Rubenfeld, MIT

Date: Tuesday, November 01, 2016

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: G449 Patil/Kiva

Event Type:

Room Description:

Host: Aleksander Madry

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Ronitt Rubinfeld: Local Computation Algorithms

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 {\em 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 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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) Seminar Series 2016.

Created by Deborah Goodwin at Tuesday, October 25, 2016 at 12:12 PM.