12 citations · 34 across the 22 of their papers we have counts for
8 papers · 1 filter
Estimating Size of the Union of Sets in Streaming Model
Kuldeep S. Meel, N. V. Vinodchandran, Sourav Chakraborty
We study estimating the size of the union of sets , where each is presented implicitly and arrives in a stream. We introduce Delphic sets, a class of…
Towards practical FPRAS for #NFA: Exploiting the Power of Dependence
Kuldeep S. Meel, Alexis de Colnet
#NFA refers to the problem of counting the words of length accepted by a non-deterministic finite automaton. #NFA is #P-hard, and although fully-polynomial-time randomized appr…
Algorithms and Hardness for Estimating Statistical Similarity
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We introduce and study the computational problem of determining statistical similarity between probability distributions. For distributions and over a finite sample space,…
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…
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…
A faster FPRAS for #NFA
Kuldeep S. Meel, Sourav Chakraborty, Umang Mathur
Given a non-deterministic finite automaton (NFA) A with m states, and a natural number n (presented in unary), the #NFA problem asks to determine the size of the set L(A_n) of word…
Total Variation Distance Meets Probabilistic Inference
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-prese…
Testing Probabilistic Circuits
Yash Pote, Kuldeep S. Meel
Probabilistic circuits (PCs) are a powerful modeling framework for representing tractable probability distributions over combinatorial spaces. In machine learning and probabilistic…