17 citations · 48 across the 19 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…
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…
On the Composition of Randomized Query Complexity and Approximate Degree
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +3
For any Boolean functions and , the question whether , is known as the composition question for the randomized query complexity. Similarly,…
Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar +1
Given a Boolean formula over variables, the problem of model counting is to compute the number of solutions of . Model counting is a fundamental problem in computer scie…
On simple expectations and observations of intelligent agents: A complexity study
Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh +1
Public observation logic (POL) reasons about agent expectations and agent observations in various real world situations. The expectations of agents take shape based on certain prot…
Regular Methods for Operator Precedence Languages
Thomas A. Henzinger, Pavol Kebis, Nicolas Mazzocchi +1
The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This inc…
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…
Certificate Games and Consequences for the Classical Adversary Bound
Sourav Chakraborty, Anna Gál, Mika Göös +3
We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function va…
Colorful two-piercing theorem for boxes
Sourav Chakraborty, Arijit Ghosh, Soumi Nandi
We prove a colorful extension of a Helly-type theorem by Danzer and Grünbaum (Combinatorica, 1982) concerning two-piercing families of axis-parallel boxes in . We als…
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…
On verifying expectations and observations of intelligent agents
Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh +1
Public observation logic (POL) is a variant of dynamic epistemic logic to reason about agent expectations and agent observations. Agents have certain expectations, regarding the si…
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…
The Role of Symmetry in Quantum Query-to-Communication Simulation
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer +3
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of…
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…
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh +2
The disjointness problem - where Alice and Bob are given two subsets of and they have to check if their sets intersect - is a central problem in the world of comm…
Two new results about quantum exact learning
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee +2
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a -Fourier-sparse -bit Boolean function from …
Improved bounds on Fourier entropy and Min-entropy
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký +2
Given a Boolean function , the Fourier distribution assigns probability to . The Fourier Entropy-Influence (FEI) conjec…
Property Testing of Joint Distributions using Conditional Samples
Rishiraj Bhattacharyya, Sourav Chakraborty
In this paper, we consider the problem of testing properties of joint distributions under the Conditional Sampling framework. In the standard sampling model, the sample complexity…
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…
Helly-Type Theorems in Property Testing
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy +1
Helly's theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If is a set of points in , we say tha…