Superlinear lower bounds based on ETH

András Z. Salamon, Michael Wehar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Downloads (Pure)

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 s uperlinear time complexity lower bounds for natural problems in polynomial time.
Original languageEnglish
Title of host publicationSymposium on Theoretical Aspects of Computer Science (STACS 2022)
EditorsPetra Berenbrink, Benjamin Monmege
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
Number of pages15
DOIs
Publication statusPublished - 15 Mar 2022
EventThe 39th International Symposium on Theoretical Aspects of Computer Science: STACS 2022 - Virtual
Duration: 15 Mar 202218 Mar 2022
Conference number: 39
https://stacs2022.sciencesconf.org/

Publication series

NameLeibniz International Proceedings in Informatics
PublisherDagstuhl Publishing
ISSN (Electronic)1868-8969

Conference

ConferenceThe 39th International Symposium on Theoretical Aspects of Computer Science
Abbreviated titleSTACS 2022
Period15/03/2218/03/22
Internet address

Fingerprint

Dive into the research topics of 'Superlinear lower bounds based on ETH'. Together they form a unique fingerprint.

Cite this