All reports by Author Sourav Chakraborty:

__
TR22-143
| 7th November 2022
__

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny#### Certificate games

Revisions: 1

__
TR20-114
| 22nd July 2020
__

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar#### Disjointness through the Lens of Vapnikâ€“Chervonenkis Dimension: Sparsity and Beyond

__
TR19-136
| 23rd September 2019
__

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar#### Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead

__
TR18-167
| 25th September 2018
__

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf#### Improved bounds on Fourier entropy and Min-entropy

Revisions: 1

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny

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 values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower ... more >>>

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>>

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f : \{-1, 1\}^n \to \{-1, 1\}$ and $\bullet : \{-1, 1\}^2 \to \{-1, 1\}$ the two-party bounded-error quantum communication complexity of $(f \circ \bullet)$ is $O(Q(f) \log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. ... more >>>

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf

Given a Boolean function $f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of $[n]$, where each $S\subseteq [n]$ is sampled with probability $\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>