Campus Event Calendar

Event Entry

What and Who

Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?

Gunjan Kumar
National University of Singapore
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Thursday, 20 July 2023
30 Minutes
E1 4


Given a Boolean formula $\phi$ over $n$ variables, the problem of model counting is to compute the number of solutions of $\phi$. Model counting is a fundamental problem in computer science with wide-ranging applications in domains such as quantified information leakage, probabilistic reasoning, network reliability, neural network verification, and more. Owing to the #P-hardness of the problems, Stockmeyer initiated the study of the complexity of approximate counting and showed that $\log n$ calls to an NP oracle are necessary and sufficient to achieve tight guarantees.

It is well known that an NP oracle does not fully capture the behavior of SAT solvers, as SAT solvers are also designed to provide satisfying assignments when a formula is satisfiable, without additional overhead. Accordingly, the notion of SAT oracle has been proposed to capture the behavior of SAT solver wherein given a Boolean formula, an SAT oracle returns a satisfying assignment if the formula is satisfiable or returns unsatisfiable otherwise.

The primary contribution of this work is to study the relative power of the NP oracle and SAT oracle in the context of approximate model counting. We develop a new methodology to achieve the main result: a SAT oracle is no more powerful than an NP oracle in the context of approximate model counting.

(To appear in ICALP 2023 ( Joint work with Diptarka Chakraborty, Sourav Chakraborty, and Kuldeep S. Meel).


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 06/22/2023 12:46
Roohani Sharma, 06/21/2023 09:23 -- Created document.