CNFs and DNFs with exactly k solutions

Title of the Talk: CNFs and DNFs with exactly k solutions
Host Faculty: Dr. Rogers Mathew
Speaker: Prof. L. Sunil Chandran
Date: 01 Jun 2026
Time: 12:00 pm

Abstract
Model counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weighted sum of satisfying assignments, has extensive applications in probabilistic reasoning, network reliability, statistical physics, and formal verification. A common approach for solving weighted model counting is to reduce it to unweighted model counting, which raises an important question: What is the minimum number of terms (or clauses) required to construct a DNF (or CNF) formula with exactly $k$ satisfying assignments?

In this talk, we establish both upper and lower bounds on this question. We prove that for any natural number $k$, one can construct a monotone DNF formula with exactly $k$ satisfying assignments using at most $O(\sqrt{\log k}\log\log k)$ terms. This construction represents the first $o(\log k)$ upper bound for this problem. We complement this result by showing that there exist infinitely many values of $k$ for which any DNF or CNF representation requires at least \Omega(\log\log k)$ terms or clauses. These results have significant implications for the efficiency of model counting algorithms based on formula transformations.

Bio
Dr. L. Sunil Chandran is a professor in the Department of Computer Science and Automation in Indian Institute of Science, Bangalore. His area of research is graph theory, combinatorics, and graph algorithms. He is a fellow of Indian National Science Academy (INSA) and Indian National Academy of Engineering (INAE).