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.IPEC.2015.17
URN: urn:nbn:de:0030-drops-55683
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5568/
Go to the corresponding LIPIcs Volume Portal

Vassilevska Williams, Virginia

Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)

pdf-format:
5.pdf (0.5 MB)

Abstract

Algorithmic research strives to develop fast algorithms for fundamental problems. Despite its many successes, however, many problems still do not have very efficient algorithms. For years researchers have explained the hardness for key problems by proving NP-hardness, utilizing polynomial time reductions to base the hardness of key problems on the famous conjecture P != NP. For problems that already have polynomial time algorithms, however, it does not seem that one can show any sort of hardness based on P != NP. Nevertheless, we would like to provide evidence that a problem $A$ with a running time O(n^k) that has not been improved in decades, also requires n^{k-o(1)} time, thus explaining the lack of progress on the problem. Such unconditional time lower bounds seem very difficult to obtain, unfortunately. Recent work has concentrated on an approach mimicking NP-hardness: (1) select a few key problems that are conjectured to require T(n) time to solve, (2) use special, fine-grained reductions to prove time lower bounds for many diverse problems in P based on the conjectured hardness of the key problems. In this abstract we outline the approach, give some examples of hardness results based on the Strong Exponential Time Hypothesis, and present an overview of some of the recent work on the topic.

BibTeX - Entry

@InProceedings{vassilevskawilliams:LIPIcs:2015:5568,
  author =	{Virginia Vassilevska Williams},
  title =	{{Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{17--29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5568},
  URN =		{urn:nbn:de:0030-drops-55683},
  doi =		{10.4230/LIPIcs.IPEC.2015.17},
  annote =	{Keywords: reductions, satisfiability, strong exponential time hypothesis, shortest paths, 3SUM, equivalences, fine-grained complexity}
}

Keywords: reductions, satisfiability, strong exponential time hypothesis, shortest paths, 3SUM, equivalences, fine-grained complexity
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

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