DNF Model Counting: The Search for Holier Grails
COM1 Level 3
MR1, COM1-03-19
Abstract:
The problem of propositional model counting is as hard as it is important. A wide variety of applications areas like Bayesian Learning, Probabilistic Databases, Reliability Testing to name a few, would benefit directly from any improvements to the apparently benign problem of counting solutions to Boolean formulas. Despite daunting complexity for the exact version, the approximate variant is surprisingly easy for some classes of formulas. One such example are boolean formulas in Disjunctive Normal Form. There are celebrated 30-year-old algorithms as well as a few recent ones, that provide highly accurate approximate counts for DNF formulas in polynomial time, which essentially is the holy grail in theory. However the practical side is still relatively unexplored and our experiments showed that the grails are not-so-holy in practice. In this talk I will describe our work on developing algorithms which provide strong guarantees on accuracy and running time for DNF Counting, and which also work well in practice. Our empirical evaluation of the various algorithms provides a nuanced picture which cautions against relying too much on worst case complexity. This is joint work with Prof. Kuldeep Meel from NUS and Prof. Moshe Vardi from Rice University.
Biodata:
Aditya Shrotri is a 4th year graduate student at Rice University, USA advised by Prof. Moshe Vardi. His work revolves around developing efficient algorithms for model counting with a focus on approximation algorithms that use hash functions.