2026-08-10T04:07:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22868 2025-10-02T13:35:56Z ddc:004 open_access

Local Enumeration: The Not-All-Equal Case Gurumukhani, Mohit Paturi, Ramamohan Saks, Michael Talebanfard, Navid Depth 3 circuits k-CNF satisfiability Circuit lower bounds Majority function Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number k and a parameter t, given an n-variate k-CNF with no satisfying assignment of Hamming weight less than t(n), enumerate all satisfying assignments of Hamming weight exactly t(n). Furthermore, they gave a randomized algorithm for Enum(k, t) and employed new ideas to analyze the first non-trivial case, namely k = 3. In particular, they solved Enum(3, n/2) in expected 1.598ⁿ time. A simple construction shows a lower bound of 6^{n/4} ≈ 1.565ⁿ. In this paper, we show that to break SSETH, it is sufficient to consider a simpler local enumeration problem NAE-Enum(k, t): for a natural number k and a parameter t, given an n-variate k-CNF with no satisfying assignment of Hamming weight less than t(n), enumerate all Not-All-Equal (NAE) solutions of Hamming weight exactly t(n), i.e., those that satisfy and falsify some literal in every clause. We refine the algorithm of Gurumukhani et al. and show that it optimally solves NAE-Enum(3, n/2), namely, in expected time poly(n) ⋅ 6^{n/4}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohit Gurumukhani and Ramamohan Paturi and Michael Saks and Navid Talebanfard 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.42 urn:nbn:de:0030-drops-228680 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.42 eng https://creativecommons.org/licenses/by/4.0/legalcode