Login
Talks & Seminars
Title: New Hashing-based Approaches to Approximate DNF Counting
Mr. Aditya Shrotri, Rice University, USA
Date & Time: January 5, 2017 15:45
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
Hashing based techniques have enjoyed tremendous success for approximately counting CNF formulas while providing scalability and theoretical guarantees on accuracy. It was shown recently that the same techniques can be used for counting DNF formulas with the same guarantees, and the resulting algorithm is a "Fully Polynomial Randomized Approximation Scheme" that is fundamentally different from the state of the art. However, in practice, the new approach does not scale as well. In this talk, I will discuss the techniques we developed to make hashing based DNF counting scalable. More importantly, I will demonstrate that these techniques are far more fundamental with much wider applicability than just DNF formulas. This is joint work with Kuldeep Meel and Moshe Vardi at Rice University.
Speaker Profile:
Aditya got his undergraduate degree from University of Pune and completed MTech from IITB in 2014. After that, he worked with Akshay S. for a year on applying Markov chain theory to the Skolem problem. Currently, he is working towards a PhD at Rice University, advised by Moshe Vardi in the area of model counting.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback