12 citations · 34 across the 22 of their papers we have counts for
5 papers · 1 filter
Computational Explorations of Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm…
Model Counting in the Wild
Arijit Shaw, Kuldeep S. Meel
Model counting is a fundamental problem in automated reasoning with applications in probabilistic inference, network reliability, neural network verification, and more. Although mo…
Formally Certified Approximate Model Counting
Yong Kiam Tan, Jiong Yang, Mate Soos +2
Approximate model counting is the task of approximating the number of solutions to an input Boolean formula. The state-of-the-art approximate model counter for formulas in conjunct…
Total Variation Distance for Product Distributions is -Complete
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We show that computing the total variation distance between two product distributions is -complete. This is in stark contrast with other distance measures such as Kul…
Equivalence Testing: The Power of Bounded Adaptivity
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar +1
Equivalence testing, a fundamental problem in the field of distribution testing, seeks to infer if two unknown distributions on are the same or far apart in the total variati…