[DMANET] IGAFIT Algorithmic Colloquium - 4pm(!) CEST, June 10: Local Computation Algorithms by Ronitt Rubinfeld

Dear all,
Please note the unusual time(!) for the next talk on the IGAFIT
Algorithmic Colloquium this Thursday:

June 10, 2021, 16:00 CEST (not the usual 14:00 time)
Ronitt Rubinfeld, MIT
Title: 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 "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.

We would like to invite you to take part in the event including the
networking session. This new event aims to integrate the European
algorithmic community and keep it connected during the times of the
pandemic. The meeting will be held using the Airmeet platform and to attend
please go to https://www.airmeet.com/e/eaf99aa0-c780-11eb-8e9e-11157ab1cbe8.
You can find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.

In order to access the Airmeet platform, you will need to register, so that
others know who you are. Then before and after the talk, you will be
located inside a Social Lounge, where discussion tables are visible. Most
of the tables can have up to 8 chairs, and you can join a table by clicking
the "Take a Seat" button on a table. This way you will be able to talk to
people seated currently at the table. When the session starts you will be
automatically switched to see the stage. You can find more instructions on
how to use Airmeet here:
https://www.airmeet.com/hub/step-by-step-guide-use-airmeet-for-attendees/.

We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.

Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Danupon Nanongkai
Adi Rosen
Eva Rotenberg
Piotr Sankowski
Christian Sohler

**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************