Newman's lemma for distributional communication complexity 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.
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...