Superlinear lower bounds based on ETH

András Z. Salamon; Michael Wehar

doi:10.4230/LIPIcs.STACS.2022.55

Superlinear lower bounds based on ETH

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Editors	Petra Berenbrink, Benjamin Monmege
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
Number of pages	15
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2022.55
Publication status	Published - 15 Mar 2022
Event	The 39th International Symposium on Theoretical Aspects of Computer Science: STACS 2022 - Virtual Duration: 15 Mar 2022 → 18 Mar 2022 Conference number: 39 https://stacs2022.sciencesconf.org/

Publication series

Name	Leibniz International Proceedings in Informatics
Publisher	Dagstuhl Publishing
ISSN (Electronic)	1868-8969

Conference

Conference	The 39th International Symposium on Theoretical Aspects of Computer Science
Abbreviated title	STACS 2022
Period	15/03/22 → 18/03/22
Internet address	https://stacs2022.sciencesconf.org/

Access to Document

10.4230/LIPIcs.STACS.2022.55Licence: CC BY

Salamon_2022_Superlinear-lower-bounds_AAM
Copyright © 2022 the Author(s). This work has been made available online in accordance with publisher policies or with permission. Permission for further reuse of this content should be sought from the publisher or the rights holder. This is the author created accepted manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.4230/LIPIcs.STACS.2022.14.
Accepted author manuscript, 454 KB

https://arxiv.org/abs/2008.06805v5

Cite this

@inproceedings{386b9262f2e34531bf7e3460acfca502,

title = "Superlinear lower bounds based on ETH",

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.",

author = "Salamon, {Andr{\'a}s Z.} and Michael Wehar",

note = "Andras Z. Salamon acknowledges support from EPSRC grants EP/P015638/1 and EP/V027182/1. ; The 39th International Symposium on Theoretical Aspects of Computer Science : STACS 2022, STACS 2022 ; Conference date: 15-03-2022 Through 18-03-2022",

year = "2022",

month = mar,

day = "15",

doi = "10.4230/LIPIcs.STACS.2022.55",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik GmbH",

editor = "Petra Berenbrink and Benjamin Monmege",

booktitle = "Symposium on Theoretical Aspects of Computer Science (STACS 2022)",

url = "https://stacs2022.sciencesconf.org/",

}

Salamon, AZ & Wehar, M 2022, Superlinear lower bounds based on ETH. in P Berenbrink & B Monmege (eds), Symposium on Theoretical Aspects of Computer Science (STACS 2022)., 14, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, The 39th International Symposium on Theoretical Aspects of Computer Science, 15/03/22. https://doi.org/10.4230/LIPIcs.STACS.2022.55

Superlinear lower bounds based on ETH. / Salamon, András Z.; Wehar, Michael.
Symposium on Theoretical Aspects of Computer Science (STACS 2022). ed. / Petra Berenbrink; Benjamin Monmege. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2022. 14 (Leibniz International Proceedings in Informatics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Superlinear lower bounds based on ETH

AU - Salamon, András Z.

AU - Wehar, Michael

N1 - Conference code: 39

PY - 2022/3/15

Y1 - 2022/3/15

N2 - 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.

AB - 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.

UR - https://drops.dagstuhl.de/opus/institut_lipics.php?fakultaet=04

U2 - 10.4230/LIPIcs.STACS.2022.55

DO - 10.4230/LIPIcs.STACS.2022.55

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics

BT - Symposium on Theoretical Aspects of Computer Science (STACS 2022)

A2 - Berenbrink, Petra

A2 - Monmege, Benjamin

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH

T2 - The 39th International Symposium on Theoretical Aspects of Computer Science

Y2 - 15 March 2022 through 18 March 2022

ER -

Superlinear lower bounds based on ETH

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Keep Learning: Keep Learning

Cite this

Superlinear lower bounds based on ETH

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Projects

Keep Learning: Keep Learning

Cite this