All reports by Author Sagnik Mukhopadhyay:

__
TR18-175
| 23rd October 2018
__

Bruno Loff, Sagnik Mukhopadhyay#### Lifting Theorems for Equality

Revisions: 2

__
TR17-170
| 6th November 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Simulation Beats Richness: New Data-Structure Lower Bounds

__
TR17-014
| 23rd January 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Composition and Simulation Theorems via Pseudo-random Properties

__
TR16-165
| 30th October 2016
__

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Lower Bounds for Elimination via Weak Regularity

__
TR16-027
| 10th February 2016
__

Sagnik Mukhopadhyay#### Tribes Is Hard in the Message Passing Model

Revisions: 1

__
TR15-107
| 21st June 2015
__

Sagnik Mukhopadhyay, Swagato Sanyal#### Towards Better Separation between Deterministic and Randomized Query Complexity

Bruno Loff, Sagnik Mukhopadhyay

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ EQ_n$ ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a $p \times n$ ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f:\{0,1\}^n \to \{0,1\}$ be any boolean function. Alice and Bob get $k$ inputs ... more >>>

Sagnik Mukhopadhyay

We consider the point-to-point message passing model of communication in which there are $k$ processors

with individual private inputs, each $n$-bit long. Each processor is located at the node of an underlying

undirected graph and has access to private random coins. An edge of the graph is a private channel ...
more >>>

Sagnik Mukhopadhyay, Swagato Sanyal

We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$

and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by

Saks and Wigderson that for any Boolean ...
more >>>