17 citations · 48 across the 19 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…