TY - GEN
T1 - Local Enumeration
T2 - 42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025
AU - Gurumukhani, Mohit
AU - Paturi, Ramamohan
AU - Saks, Michael
AU - Talebanfard, Navid
N1 - Publisher Copyright:
© Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, and Navid Talebanfard.
PY - 2025/2/24
Y1 - 2025/2/24
N2 - 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, n2 ) in expected 1.598n time. A simple construction shows a lower bound of 6 n4 ≈ 1.565n. 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.
AB - 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, n2 ) in expected 1.598n time. A simple construction shows a lower bound of 6 n4 ≈ 1.565n. 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.
KW - Circuit lower bounds
KW - Depth 3 circuits
KW - k-CNF satisfiability
KW - Majority function
UR - http://www.scopus.com/inward/record.url?scp=85219529522&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85219529522&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2025.42
DO - 10.4230/LIPIcs.STACS.2025.42
M3 - Conference contribution
AN - SCOPUS:85219529522
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025
A2 - Beyersdorff, Olaf
A2 - Pilipczuk, Michal
A2 - Pimentel, Elaine
A2 - Thang, Nguyen Kim
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 4 March 2025 through 7 March 2025
ER -