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

<p><span class="math-container">$$
\mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon
$$</span></p>

<p>you can conclude that there's a single <span class="math-container">$r_0$</span> for which</p>

<p><span class="math-container">$$
\mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r_0) \neq f(x,y)} \leq \varepsilon.
$$</span></p>

<p>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...</p>

CC BY-SA 4.0
2018-12-16T20:37:52.533Z
That's a good point... so it wasn't wrong, just proving something about a trivial concept. Thank you!
Clement C.
CC BY-SA 4.0
2018-12-16T19:58:55.267Z
2018-12-16T19:58:55.267Z
domotorp
<p><em>This may be obvious — sorry if it is.</em></p>

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

<p>Adapting the proof, this generalizes readily to <span class="math-container">$k$</span>-party protocols <span class="math-container">$f\colon (\{0,1\}^n)^k\to\{0,1\}$</span>, using <span class="math-container">$O(\log(kn/\delta^2))$</span> public random bits.</p>

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

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

<hr>

<p><em>Here is the proof I have in mind:</em></p>

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

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

CC BY-SA 4.0
2018-12-15T22:25:00.983Z
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 ;)
domotorp
CC BY-SA 4.0
2018-12-15T22:46:27.907Z
@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.)
Clement C.
CC BY-SA 4.0
2018-12-16T19:55:24.433Z
Oh I see, until now I was confused because I thought you go from private to public (which is another lemma).
domotorp
<randomness><communication-complexity>
Newman's lemma for distributional communication complexity
Clement C.
# Newman's lemma for distributional communication complexity

(Asked by: username_0 on 2018-12-15)

*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.

**Tags:** randomness, communication-complexity

> **Comments:**
> **username_1**: 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 ;)  
> **username_0**: @username_1 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.)  
> **username_1**: Oh I see, until now I was confused because I thought you go from private to public (which is another lemma).  

---

## 1 answers

### Answer by username_1 on 2018-12-16. Score: 4 | Accepted answer

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...

> **Comments:**
> **username_0**: That's a good point... so it wasn't wrong, just proving something about a trivial concept. Thank you!  

---

