[Colloquium] REMINDER: 5/20 TTIC Colloquium: Ronitt Rubinfeld, MIT and Tel Aviv University

[Mary Marre]

*When:    *  Monday, May 20th at *11:00 am*



*Where:     *TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who:        *Ronitt Rubinfeld, MIT and Tel Aviv University


*Title:   *    Local Algorithms for Sparse Connected Subgraphs

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

*Host:* Avrim Blum <avrim at ttic.edu>


For more information on the colloquium series or to subscribe to the
mailing list,please see http://www.ttic.edu/colloquium.php



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Mon, May 13, 2019 at 4:17 PM Mary Marre <mmarre at ttic.edu> wrote:

> *When:    *  Monday, May 20th at *11:00 am*
>
>
>
> *Where:     *TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526
>
>
>
> *Who:        *Ronitt Rubinfeld, MIT and Tel Aviv University
>
>
> *Title:   *    Local Algorithms for Sparse Connected Subgraphs
>
> *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. In this talk, we
> survey a series of results on local computation algorithms for finding
> sparse connected subgraphs and sparse spanners.
>
> *Host:* Avrim Blum <avrim at ttic.edu>
>
>
> For more information on the colloquium series or to subscribe to the
> mailing list,please see http://www.ttic.edu/colloquium.php
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190519/7e6be10a/attachment-0001.html>