12 citations · 34 across the 22 of their papers we have counts for
24 papers
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…
CSB: A Counting and Sampling tool for Bit-vectors
Arijit Shaw, Kuldeep S. Meel
Satisfiability modulo theory (SMT) solvers have significantly advanced automated reasoning due to their effectiveness in solving problems across various fields. With the advancemen…
Counting and Sampling Traces in Regular Languages
Alexis de Colnet, Kuldeep S. Meel, Umang Mathur
In this work, we study the problems of counting and sampling Mazurkiewicz traces that a regular language touches. Fix an alphabet and an independence relation $\mathbb{I} \subs…
Efficient Volume Computation for SMT Formulas
Arijit Shaw, Uddalok Sarkar, Kuldeep S. Meel
Satisfiability Modulo Theory (SMT) has recently emerged as a powerful tool for solving various automated reasoning problems across diverse domains. Unlike traditional satisfiabilit…
Solution-aware vs global ReLU selection: partial MILP strikes back for DNN verification
Yuke Liao, Blaise Genest, Kuldeep Meel +1
To handle complex instances, we revisit a divide-and-conquer approach to break down the complexity: instead of few complex BaB calls, we rely on many small {\em partial} MILP calls…
Approximate SMT Counting Beyond Discrete Domains
Arijit Shaw, Kuldeep S. Meel
Satisfiability Modulo Theory (SMT) solvers have advanced automated reasoning, solving complex formulas across discrete and continuous domains. Recent progress in propositional mode…
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…
Assessing the Quality of Binomial Samplers: A Statistical Distance Framework
Uddalok Sarkar, Sourav Chakraborty, Kuldeep S. Meel
Randomized algorithms depend on accurate sampling from probability distributions, as their correctness and performance hinge on the quality of the generated samples. However, even…
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…
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…
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…
Explaining SAT Solving Using Causal Reasoning
Jiong Yang, Arijit Shaw, Teodora Baluta +2
The past three decades have witnessed notable success in designing efficient SAT solvers, with modern solvers capable of solving industrial benchmarks containing millions of variab…
How Biased are Your Features?: Computing Fairness Influence Functions with Global Sensitivity Analysis
Bishwamittra Ghosh, Debabrota Basu, Kuldeep S. Meel
Fairness in machine learning has attained significant focus due to the widespread application in high-stake decision-making tasks. Unregulated machine learning classifiers can exhi…
Efficient Learning of Interpretable Classification Rules
Bishwamittra Ghosh, Dmitry Malioutov, Kuldeep S. Meel
Machine learning has become omnipresent with applications in various safety-critical domains such as medical, law, and transportation. In these domains, high-stake decisions provid…
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…
Projected Model Counting: Beyond Independent Support
Jiong Yang, Supratik Chakraborty, Kuldeep S. Meel
The past decade has witnessed a surge of interest in practical techniques for projected model counting. Despite significant advancements, however, performance scaling remains the A…
Arjun: An Efficient Independent Support Computation Technique and its Applications to Counting and Sampling
Mate Soos, Kuldeep S. Meel
Given a Boolean formula over the set of variables and a projection set , a subset of variables is independent support of $\mathcal{P}…
Algorithmic Fairness Verification with Graphical Models
Bishwamittra Ghosh, Debabrota Basu, Kuldeep S. Meel
In recent years, machine learning (ML) algorithms have been deployed in safety-critical and high-stake decision-making, where the fairness of algorithms is of paramount importance.…
Distributed Phasers
Sri Raj Paul, Karthik Murthy, Kuldeep S. Meel +1
A phaser is an expressive synchronization construct that unifies collective and point-to-point coordination with dynamic task parallelism. Each task can participate in a phaser as…