2026-07-22T17:01:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15865 2024-03-06T10:56:23Z ddc:004 open_access

Superlinear Lower Bounds Based on ETH Salamon, András Z. Wehar, Michael Circuit Satisfiability Conditional Lower Bounds Exponential Time Hypothesis Limited Nondeterminism 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik András Z. Salamon and Michael Wehar 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.55 urn:nbn:de:0030-drops-158652 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.55 eng https://creativecommons.org/licenses/by/4.0/legalcode