Probabilistic inference via model counting has emerged as a scalable technique with strong formal guarantees, thanks to recent advances in hashing-based approximate counting. State-of-the-art hashing-based counting algorithms use an NP oracle, such that the number of oracle invocations grows linearly in the number of variables n in the input constraint. We present a new approach to hashing-based approximate model counting in which the number of oracle invocations grows logarithmically in $n$, while still providing strong theoretical guarantees. Our experiments show that the new approach outperforms state-of-the-art techniques for approximate counting by 1-2 orders of magnitude in running time.

(Joint work with Supratik Chakraborty and Moshe Y. Vardi)

Bio:

Kuldeep is a final year PhD student in Rice working with Prof. Moshe Vardi and Prof. Supratik Chakraborty (IITB). He obtained B.Tech. from IIT Bombay and M.S. from Rice in 2012 and 2014 respectively. His research broadly falls into the intersection of artificial intelligence and formal methods. He is the recipient of 2016-17 IBM PhD Fellowship and Lodieska Stockbridge Vaughn Fellowship. His research won best student paper award at International Conference on Constraint Programming 2015 and 2014 Vienna Center of Logic and Algorithms Outstanding Masters thesis award.