We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity $I$ and communication complexity $C$ can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed $O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication ... more >>>

For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,
Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ... more >>>

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof
showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

more >>>