|
2.00 pm, Seminar Hall Constrained Sampling and Counting: When Practice Drives Theory Kuldeep Meel Rice University, USA. 19-01-16 Abstract Constrained sampling, i.e. sampling satisfying assignments of a given set of constraints, and constrained counting, i.e. counting of satisfying assignments, are fundamental computational problems in computer science with numerous application, including probabilistic reasoning, machine learning, planning, statistical physics, inexact computing, and constrained-random verification. While the theory of these problems has been thoroughly investigated in the 1980s, approximation algorithms developed by theoreticians do not scale up to industrial-sized instances. Algorithms used by the industry offer better scalability, but give up certain correctness guarantees to achieve scalability. We describe a novel approach, based on universal hashing and Satisfiability Modulo Theory, that scales to formulas with hundreds of thousands of variables without giving up correctness guarantees. Joint work with Supratik Chakraborty and Moshe Y. Vardi.
|
