Sampling Techniques for Constraint Satisfaction and Beyond

Date

September 5, 2014

Speaker

Kuldeep Meel

Affiliation

Rice University

Overview

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.

Speakers

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.