License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.3
URN: urn:nbn:de:0030-drops-75068
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7506/
Go to the corresponding LIPIcs Volume Portal

Rubinfeld, Ronitt

Local Computation Algorithms (Invited Talk)

pdf-format:
LIPIcs-ICALP-2017-3.pdf (0.2 MB)

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 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 sparse spanning graphs.

BibTeX - Entry

@InProceedings{rubinfeld:LIPIcs:2017:7506,
  author =	{Ronitt Rubinfeld},
  title =	{{Local Computation Algorithms (Invited Talk)}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7506},
  URN =		{urn:nbn:de:0030-drops-75068},
  doi =		{10.4230/LIPIcs.ICALP.2017.3},
  annote =	{Keywords: Massive Data Sets, Approximate Solutions, Maximal Independent Set, Sparse Spanning Graphs}
}

Keywords: Massive Data Sets, Approximate Solutions, Maximal Independent Set, Sparse Spanning Graphs
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI