This may be obvious — sorry if it is.

Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be converted to one that uses only $O(\log(n/\delta^2))$ public random bits, while preserving the communication complexity and at the price of an additional $\delta$ probability of error.

Adapting the proof, this generalizes readily to $k$-party protocols $f\colon (\{0,1\}^n)^k\to\{0,1\}$, using $O(\log(kn/\delta^2))$ public random bits.

What I couldn't find is the same result for distributional communication complexity (more precisely, for public-coin randomized distributional communication complexity, which may be a rather niche notion (?)). For the worst-case setting, the $n$ factor in the number of public random bits comes from a union bound over all possible $2^{2n}$ joint inputs. In the case of distributional communication complexity, where the input $x,y)$ (or even $(x^{(1)},\dots,x^{(k)})$ comes from a distribution $\mu$ over inputs, does that mean that one can avoid this union bound, and get the conclusion of Newman's lemma with only $O(1/\delta^2)$ public random bits?

(This seems a bit too good to be true — what am I missing?)

Here is the proof I have in mind:

Let $\mu$ a distribution over $\{0,1\}^n\times\{0,1\}^n$, and $f\colon \{0,1\}^n\times\{0,1\}^n \to \{0,1\}$ the function to compute. Let $\Pi$ be a public-coin protocol computing $f$ with probability at least $1-\varepsilon$ over $\mu$, i.e., $$ \mathbb{P}_{(x,y)\sim \mu, r}\{ \Pi(x,y; r) \neq f(x,y) \} \leq \varepsilon $$ where the probability is taken over the choice of input (drawn from $\mu$) and the public randomness $r$ of $\Pi$.

As in the proof of Newman's lemma, we can assume wlog that $\Pi$ is a uniform distribution over deterministic protocols $\Pi_1,\dots,\Pi_R$ for some $R\geq 0$. Thus, $$ \mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon $$ and, if we select uniformly and independently $t = O(1/\delta^2)$ indices $r_1,\dots, r_t\in[R]$, we have with probability at least $9/10$ that $$ \frac{1}{t}\sum_{i=1}^t \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r_i) \neq f(x,y)} \leq \varepsilon + \delta $$ so that in particular there exists a choice of $t$ indices $r^*_1,\dots, r^*_t\in[R]$ such that $$ \mathbb{P}_{(x,y)\sim \mu, i\sim[t]}\{ \Pi(x,y; r) \neq f(x,y) \} = \mathbb{E}_{i\sim [t]} \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r^\ast_i) \neq f(x,y)} \leq \varepsilon+\delta $$ which yields a public-coin protocol $\Pi^\ast$ with same communication complexity as $\Pi$, using only $O(\log t) = O(\log(1/\delta))$ random bits.

  • $\begingroup$ I don't think that the union bound can be avoided, but it's quite hard to spot the error in your argument if you don't write it down in more detail. (And if you do, probably you'll see it yourself ;) $\endgroup$
    – domotorp
    Dec 15, 2018 at 22:25
  • $\begingroup$ @domotorp I added the proof I had in mind. (Note that I am talking about "randomized distributional communication complexity," which I am not sure is that common a notion.) $\endgroup$
    – Clement C.
    Dec 15, 2018 at 22:46
  • $\begingroup$ Oh I see, until now I was confused because I thought you go from private to public (which is another lemma). $\endgroup$
    – domotorp
    Dec 16, 2018 at 19:55

1 Answer 1


There's nothing wrong in your proof, but you can do even better; by taking the average in

$$ \mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon $$

you can conclude that there's a single $r_0$ for which

$$ \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r_0) \neq f(x,y)} \leq \varepsilon. $$

So in particular, randomized distributional communication complexity is the same as deterministic distributional communication complexity, which explains why it didn't get much attention in the literature...

  • $\begingroup$ That's a good point... so it wasn't wrong, just proving something about a trivial concept. Thank you! $\endgroup$
    – Clement C.
    Dec 16, 2018 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.