82 citations · 369 across the 63 of their papers we have counts for
12 papers · 1 filter
Engineering an Efficient Approximate DNF-Counter
Mate Soos, Uddalok Sarkar, Divesh Aggarwal +3
Model counting is a fundamental problem in many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In thi…
#CFG and #DNNF admit FPRAS
Kuldeep S. Meel, Alexis de Colnet
We provide the first fully polynomial-time randomized approximation scheme for the following two counting problems: 1. Given a Context Free Grammar over alphabet , count the…
An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs
Kuldeep S. Meel, Alexis de Colnet
Non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD), are a fundamental data structure in computer science for repr…
Distance Estimation for High-Dimensional Discrete Distributions
Gunjan Kumar, Kuldeep S. Meel, Yash Pote
Given two distributions and over a high-dimensional domain , and a parameter , the goal of distance estimation is to determine t…
On Scalable Testing of Samplers
Yash Pote, Kuldeep S. Meel
In this paper we study the problem of testing of constrained samplers over high-dimensional distributions with guarantees. Samplers are increasingly used in a w…
Support Size Estimation: The Power of Conditioning
Diptarka Chakraborty, Gunjan Kumar, Kuldeep S. Meel
We consider the problem of estimating the support size of a distribution . Our investigations are pursued through the lens of distribution testing and seek to understand the pow…
On Approximating Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV d…
Model Counting meets F0 Estimation
A. Pavan, N. V. Vinodchandran, Arnab Bhattacharyya +1
Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science…
On Testing of Samplers
Kuldeep S. Meel, Yash Pote, Sourav Chakraborty
Given a set of items and a weight function , the problem of sampling seeks to sample an item proportional to its weight. Sampl…
Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice
Kuldeep S. Meel, S. Akshay
Given a CNF formula F on n variables, the problem of model counting or #SAT is to compute the number of satisfying assignments of F . Model counting is a fundamental but hard probl…
Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +1
We design efficient distance approximation algorithms for several classes of structured high-dimensional distributions. Specifically, we show algorithms for the following problems:…
Principled Network Reliability Approximation: A Counting-Based Approach
R. Paredes, L. Duenas-Osorio, K. S. Meel +1
As engineered systems expand, become more interdependent, and operate in real-time, reliability assessment is indispensable to support investment and decision making. However, netw…