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

Bringmann, Karl

Fine-Grained Complexity Theory (Tutorial)

pdf-format:
LIPIcs-STACS-2019-4.pdf (0.4 MB)

Abstract

Suppose the fastest algorithm that we can design for some problem runs in time O(n^2). However, we want to solve the problem on big data inputs, for which quadratic time is impractically slow. We can keep searching for a faster algorithm, but maybe none exists. Is there any reasoning that provides evidence against significantly faster algorithms, and thus allows us to stop searching? In other words, is there an analogue of NP-hardness for polynomial-time problems?
In this tutorial, we will give an introduction to fine-grained complexity theory, which allows to rule out faster algorithms by proving conditional lower bounds via fine-grained reductions from certain key conjectures. We will define these terms and show exemplary lower bounds.

BibTeX - Entry

@InProceedings{bringmann:LIPIcs:2019:10243,
  author =	{Karl Bringmann},
  title =	{{Fine-Grained Complexity Theory (Tutorial)}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{4:1--4:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10243},
  doi =		{10.4230/LIPIcs.STACS.2019.4},
  annote =	{Keywords: Hardness in P, conditional lower bound, fine-grained reduction}
}

Keywords: Hardness in P, conditional lower bound, fine-grained reduction
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

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