### Constrained Counting and Sampling: Bridging the Gap between Theory and Practice

Kuldeep Meel

Rice University

SWS Colloquium

07 Mar 2017, 10:00 am - 12:30 pm

Saarbrücken building E1 5, room 029

simultaneous videocast to Kaiserslautern building G26, room 111

simultaneous videocast to Kaiserslautern building G26, room 111

Constrained counting and sampling are two fundamental problems in Computer
Science with numerous applications
including network reliability
privacy
probabilistic reasoning
and constrained-random verification. In constrained
counting
the task is to compute the total weight
subject to a given weighting
function
of the set of solutions of the given constraints. In constrained
sampling
the task is to sample randomly
subject to a given weighting
function
from the set of solutions to a set of given constraints.
In this talk
I will introduce a novel algorithmic framework for constrained
sampling and counting that combines the classical algorithmic technique of
universal hashing with the dramatic progress made in Boolean reasoning over the
past two decades. This has allowed us to obtain breakthrough results in
constrained sampling and counting
providing a new algorithmic toolbox in
machine learning
probabilistic reasoning
privacy
and design verification. I
will demonstrate the utility of the above techniques on various real
applications including probabilistic inference
design verification and our
ongoing collaboration in estimating the reliability of critical infrastructure
networks during natural disasters.