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.2019.5
URN: urn:nbn:de:0030-drops-105812
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10581/
Go to the corresponding LIPIcs Volume Portal

Yannakakis, Mihalis

Fixed Point Computation Problems and Facets of Complexity (Invited Talk)

pdf-format:
LIPIcs-ICALP-2019-5.pdf (0.2 MB)

Abstract

Many problems from a wide variety of areas can be formulated mathematically as the problem of computing a fixed point of a suitable given multivariate function. Examples include a variety of problems from game theory, economics, optimization, stochastic analysis, verification, and others. In some problems there is a unique fixed point (for example if the function is a contraction); in others there may be multiple fixed points and any one of them is an acceptable solution; while in other cases the desired object is a specific fixed point (for example the least fixed point or greatest fixed point of a monotone function). In this talk we will discuss several types of fixed point computation problems, their complexity, and some of the common themes that have emerged: classes of problems for which there are efficient algorithms, and other classes for which there seem to be serious obstacles.

BibTeX - Entry

@InProceedings{yannakakis:LIPIcs:2019:10581,
  author =	{Mihalis Yannakakis},
  title =	{{Fixed Point Computation Problems and Facets of Complexity (Invited Talk)}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10581},
  URN =		{urn:nbn:de:0030-drops-105812},
  doi =		{10.4230/LIPIcs.ICALP.2019.5},
  annote =	{Keywords: Fixed Point, Polynomial Time Algorithm, Computational Complexity}
}

Keywords: Fixed Point, Polynomial Time Algorithm, Computational Complexity
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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