1 Search Results for "Salamon, András Z."

Document

DOI: 10.4230/LIPIcs.STACS.2022.55

Superlinear Lower Bounds Based on ETH

Authors: András Z. Salamon and Michael Wehar

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-linear time unless the exponential time hypothesis (ETH) is false and k-Clique is decidable in essentially-linear time in terms of the graph’s size for all fixed k. Such conditional lower bounds have previously only been demonstrated relative to the strong exponential time hypothesis (SETH). Our results therefore offer significant progress towards proving unconditional superlinear time complexity lower bounds for natural problems in polynomial time.

Cite as

András Z. Salamon and Michael Wehar. Superlinear Lower Bounds Based on ETH. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{salamon_et_al:LIPIcs.STACS.2022.55,
  author =	{Salamon, Andr\'{a}s Z. and Wehar, Michael},
  title =	{{Superlinear Lower Bounds Based on ETH}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.55},
  URN =		{urn:nbn:de:0030-drops-158652},
  doi =		{10.4230/LIPIcs.STACS.2022.55},
  annote =	{Keywords: Circuit Satisfiability, Conditional Lower Bounds, Exponential Time Hypothesis, Limited Nondeterminism}
}

Refine by Author
1 Salamon, András Z.
1 Wehar, Michael

Refine by Classification
1 Theory of computation → Complexity classes
1 Theory of computation → Models of computation

Refine by Keyword
1 Circuit Satisfiability
1 Conditional Lower Bounds
1 Exponential Time Hypothesis
1 Limited Nondeterminism

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Salamon, András Z."

Superlinear Lower Bounds Based on ETH

Abstract

Cite as

Thanks for your feedback!

Could not send message