17 citations · 48 across the 19 of their papers we have counts for
11 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…
Instance Dependent Testing of Samplers using Interval Conditioning
Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote +2
Sampling algorithms play a pivotal role in probabilistic AI. However, verifying if a sampler program indeed samples from the claimed distribution is a notoriously hard problem. Pro…
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…
Testing Self-Reducible Samplers
Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote +2
Samplers are the backbone of the implementations of any randomised algorithm. Unfortunately, obtaining an efficient algorithm to test the correctness of samplers is very hard to fi…
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…
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar
We study the equivalence testing problem where the goal is to determine if the given two unknown distributions on are equal or -far in the total variation distance in the…
Distinct Elements in Streams: An Algorithm for the (Text) Book
Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel
Given a data stream of elements where each , the Distinct Elements problem is to estimate the number of disti…
Testing of Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +2
The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Compute…
Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +2
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently…
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…
Counting Popular Matchings in House Allocation Problems
Rupam Acharyya, Sourav Chakraborty, Nitesh Jha
We study the problem of counting the number of popular matchings in a given instance. A popular matching instance consists of agents A and houses H, where each agent ranks a subset…