Sampling Techniques for Constraint Satisfaction and Beyond


September 5, 2014


Kuldeep Meel


Rice University


Constraint problems have played a key role in diverse areas spanning testing, formal verification, planning, inferencing and the like. Apart from the classical problem of checking satisfiability, the problems of generating satisfying assignments randomly and of counting the total number of satisfying assignments have also attracted significant theoretical and practical interest over the years. Prior work offered heuristic approaches with no guarantee of solution distribution, and approaches with proven guarantees, but poor performance in practice. In this talk, I will describe a novel approach based on limited independent hashing and present two practical algorithms, UniGen and WeightMC, for solving these two fundamental problems. Unlike prior work, our algorithms provide strong theoretical guarantees and also scale to large problem sizes.


Kuldeep Meel

Kuldeep Meel is a PhD student in Rice working with Prof. Moshe Vardi and Prof. Supratik Chakraborty. His research broadly falls into the intersection of program synthesis, computer-aided verification and formal methods. He is the recipient of 2013-14 Andrew Ladd fellowship. He received his M.S. from Rice in 2014 and B.Tech. from IIT Bombay in 2012.