Tata Institute of Fundamental Research
Constrained Counting and Sampling: Bridging the Gap between Theory and Practice
STCS Seminar
Speaker:
Kuldeep S. Meel (Rice University
Department of Computer Science
DH 3060 Duncan Hall
6100 S. Main Street
Houston, TX 77005
United States of America)
Organiser:
Ashutosh Gupta
Date:
Wednesday, 11 Jan 2017, 11:00 to 12:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Constrained counting and sampling are two fundamental problems in Computer Science with numerous applications, including network reliability, decision making under certainty, 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 design verification, machine learning, probabilistic reasoning, and the like. I will demonstrate the utility of the above techniques on various real applications including probabilistic inference, hardware verification, and our ongoing collaboration in estimating the reliability of critical infrastructure networks during natural disasters.
Bio: Kuldeep Meel is a final year Ph.D. candidate at Rice University working with Prof. Moshe Vardi and Prof. Supratik Chakraborty (IITB). He obtained a B.Tech. from IIT Bombay and an M.S. from Rice in 2012 and 2014 respectively. His research broadly lies at the intersection of artificial intelligence and formal methods. He is the recipient of a 2016-17 IBM Ph.D. Fellowship, the 2016-17 Lodieska Stockbridge Vaughn Fellowship, and the 2013-14 Andrew Ladd Fellowship. His research won the best student paper award at the International Conference on Constraint Programming 2015. He co-won the 2014 Vienna Center of Logic and Algorithms International Outstanding Masters Thesis Award.
| Speaker: | Kuldeep S. Meel (Rice University Department of Computer Science DH 3060 Duncan Hall 6100 S. Main Street Houston, TX 77005 United States of America) |
| Organiser: | Ashutosh Gupta |
| Date: | Wednesday, 11 Jan 2017, 11:00 to 12:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Constrained counting and sampling are two fundamental problems in Computer Science with numerous applications, including network reliability, decision making under certainty, 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 design verification, machine learning, probabilistic reasoning, and the like. I will demonstrate the utility of the above techniques on various real applications including probabilistic inference, hardware verification, and our ongoing collaboration in estimating the reliability of critical infrastructure networks during natural disasters.
Bio: Kuldeep Meel is a final year Ph.D. candidate at Rice University working with Prof. Moshe Vardi and Prof. Supratik Chakraborty (IITB). He obtained a B.Tech. from IIT Bombay and an M.S. from Rice in 2012 and 2014 respectively. His research broadly lies at the intersection of artificial intelligence and formal methods. He is the recipient of a 2016-17 IBM Ph.D. Fellowship, the 2016-17 Lodieska Stockbridge Vaughn Fellowship, and the 2013-14 Andrew Ladd Fellowship. His research won the best student paper award at the International Conference on Constraint Programming 2015. He co-won the 2014 Vienna Center of Logic and Algorithms International Outstanding Masters Thesis Award.
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 design verification, machine learning, probabilistic reasoning, and the like. I will demonstrate the utility of the above techniques on various real applications including probabilistic inference, hardware verification, and our ongoing collaboration in estimating the reliability of critical infrastructure networks during natural disasters.
Bio: Kuldeep Meel is a final year Ph.D. candidate at Rice University working with Prof. Moshe Vardi and Prof. Supratik Chakraborty (IITB). He obtained a B.Tech. from IIT Bombay and an M.S. from Rice in 2012 and 2014 respectively. His research broadly lies at the intersection of artificial intelligence and formal methods. He is the recipient of a 2016-17 IBM Ph.D. Fellowship, the 2016-17 Lodieska Stockbridge Vaughn Fellowship, and the 2013-14 Andrew Ladd Fellowship. His research won the best student paper award at the International Conference on Constraint Programming 2015. He co-won the 2014 Vienna Center of Logic and Algorithms International Outstanding Masters Thesis Award.