<p>It is big open problem to prove lower bounds. This would imply lower bounds for BP.PP communication protocols (e.g., <a href="https://arxiv.org/abs/1205.0903" rel="nofollow noreferrer">Tarui's Theorem in communication complexity</a>), which would then imply lower bounds on matrix rigidity (over the real numbers).</p>
<p>For inner product, there is <span class="math-container">$O(1)$</span>-bit public coin protocol for <span class="math-container">$\epsilon=1/n^{O(1)}$</span>. Let me simplify by assuming that all <span class="math-container">$x_i$</span> and <span class="math-container">$y_i$</span> are IID and get value <span class="math-container">$1$</span> with probability <span class="math-container">$1/\sqrt{2}$</span> so that <span class="math-container">$x_i=y_i=1$</span> with probability <span class="math-container">$1/2$</span>. This simplifies the calculations (the uniform distribution is similar). Observe that <span class="math-container">$\langle x,y \rangle \in [0,n]$</span> is binomially distributed with mean <span class="math-container">$n/2$</span>. Note that for <span class="math-container">$c\ll\sqrt{n}$</span> we have <span class="math-container">$\langle x,y\rangle \in n/2\pm c$</span> with probability <span class="math-container">$\Theta(c/\sqrt{n})$</span>.</p>
<p>For warm up, consider the following protocol: Sample random <span class="math-container">$i\in[n]$</span> and accept if <span class="math-container">$x_i=y_i=1$</span>. Assuming <span class="math-container">$n$</span> is odd, <span class="math-container">$\lfloor n/2\rfloor$</span> is even and <span class="math-container">$\lceil n/2\rceil$</span> is odd, this protocol guesses <span class="math-container">$IP(x,y)$</span> right (with advantage <span class="math-container">$\approx 1/n$</span>) whenever <span class="math-container">$\langle x,y\rangle \in \{\lfloor n/2\rfloor,\lceil n/2\rceil\}$</span>, which occurs with probability <span class="math-container">$\Theta(1/\sqrt{n})$</span> over <span class="math-container">$(x,y)$</span>.</p>
<p>More generally, using the connection between small-advantage computations (class PP) and low-degree polynomials approximating Xor for inputs of Hamming weight <span class="math-container">$n/2\pm c$</span> (e.g, <a href="http://www.cs.yale.edu/homes/aspnes/papers/stoc91voting.pdf" rel="nofollow noreferrer">The expressive power of voting polynomials</a>) there are <span class="math-container">$O(c)$</span>-bit protocols that guess <span class="math-container">$IP(x,y)$</span> right (with advantage <span class="math-container">$1/n^{O(c)}$</span>) when <span class="math-container">$\langle x,y\rangle \in n/2 \pm c$</span>.</p>
<p>When <span class="math-container">$\langle x,y\rangle$</span> is outside middle interval, <span class="math-container">$\langle x,y\rangle \notin n/2 \pm c$</span>, we expect the protocol to err on roughly half the inputs <span class="math-container">$(x,y)$</span>. Choosing a large enough constant <span class="math-container">$c$</span>, the correctness in the middle interval starts dominating: protocol guesses right with probability <span class="math-container">$1/2+\Theta(c/\sqrt{n})$</span> over <span class="math-container">$(x,y)$</span>.</p>

CC BY-SA 4.0
2021-02-09T19:21:17.157Z
Thanks for your answer. The protocol for inner product doesn't seem correct to me though. E.g., consider $n=3$. With respect to the protocol's internal randomness, the success probability is $1$ when $\langle x, y \rangle \in \{0, 3\}$, and the success probability is $1/3$ when $\langle x, y \rangle \in \{1, 2\}$. Therefore, the probability of getting good inputs $(x, y)$ is $(3/4)^3 + (1/4)^3 < 1/2$, so the protocol doesn't work. Or am I misunderstanding?
William Hoza
CC BY-SA 4.0
2021-02-10T12:49:22.673Z
Sorry I was sloppy. I added details
Tetsuya Ishigami
CC BY-SA 4.0
2021-02-09T14:09:55.450Z
2021-02-10T12:48:27.140Z
2021-02-10T12:48:27.140Z
Tetsuya Ishigami
<p>Let <span class="math-container">$f\colon \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$</span>. I'm interested in randomized communication protocols <span class="math-container">$\pi$</span> that compute <span class="math-container">$f$</span> in the weak sense that
<span class="math-container">$$
\Pr_{x, y}\left[\Pr_r[\pi(x, y, r) = f(x, y)]\geq 1/2 + \varepsilon\right] \geq 1/2 + \varepsilon,
$$</span>
where <span class="math-container">$r$</span> is the internal randomness of <span class="math-container">$\pi$</span> and the inputs <span class="math-container">$x, y$</span> are sampled independently and uniformly at random from <span class="math-container">$\{0, 1\}^n$</span>. What upper/lower bounds are known in this setting? E.g., for the inner product mod 2 function <span class="math-container">$f(x, y) = \langle x, y\rangle$</span>, are <span class="math-container">$\Omega(n - \log(1/\varepsilon))$</span> bits of communication required?</p>

<lower-bounds><communication-complexity>
Average-case randomized communication complexity in the small-advantage regime
William Hoza
# Average-case randomized communication complexity in the small-advantage regime

(Asked by: username_0 on 2021-02-03)

Let $f\colon \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$. I'm interested in randomized communication protocols $\pi$ that compute $f$ in the weak sense that
$$
\Pr\_{x, y}\left[\Pr\_r[\pi(x, y, r) = f(x, y)]\geq 1/2 + \varepsilon\right] \geq 1/2 + \varepsilon,
$$
where $r$ is the internal randomness of $\pi$ and the inputs $x, y$ are sampled independently and uniformly at random from $\{0, 1\}^n$. What upper/lower bounds are known in this setting? E.g., for the inner product mod 2 function $f(x, y) = \langle x, y\rangle$, are $\Omega(n - \log(1/\varepsilon))$ bits of communication required?

**Tags:** lower-bounds, communication-complexity


---

## 1 answers

### Answer by username_1 on 2021-02-09. Score: 2

It is big open problem to prove lower bounds. This would imply lower bounds for BP.PP communication protocols (e.g., [Tarui's Theorem in communication complexity](https://arxiv.org/abs/1205.0903)), which would then imply lower bounds on matrix rigidity (over the real numbers).

For inner product, there is $O(1)$-bit public coin protocol for $\epsilon=1/n^{O(1)}$. Let me simplify by assuming that all $x\_i$ and $y\_i$ are IID and get value $1$ with probability $1/\sqrt{2}$ so that $x\_i=y\_i=1$ with probability $1/2$. This simplifies the calculations (the uniform distribution is similar). Observe that $\langle x,y \rangle \in [0,n]$ is binomially distributed with mean $n/2$. Note that for $c\ll\sqrt{n}$ we have $\langle x,y\rangle \in n/2\pm c$ with probability $\Theta(c/\sqrt{n})$.

For warm up, consider the following protocol: Sample random $i\in[n]$ and accept if $x\_i=y\_i=1$. Assuming $n$ is odd, $\lfloor n/2\rfloor$ is even and $\lceil n/2\rceil$ is odd, this protocol guesses $IP(x,y)$ right (with advantage $\approx 1/n$) whenever $\langle x,y\rangle \in \{\lfloor n/2\rfloor,\lceil n/2\rceil\}$, which occurs with probability $\Theta(1/\sqrt{n})$ over $(x,y)$.

More generally, using the connection between small-advantage computations (class PP) and low-degree polynomials approximating Xor for inputs of Hamming weight $n/2\pm c$ (e.g, [The expressive power of voting polynomials](http://www.cs.yale.edu/homes/aspnes/papers/stoc91voting.pdf)) there are $O(c)$-bit protocols that guess $IP(x,y)$ right (with advantage $1/n^{O(c)}$) when $\langle x,y\rangle \in n/2 \pm c$.

When $\langle x,y\rangle$ is outside middle interval, $\langle x,y\rangle \notin n/2 \pm c$, we expect the protocol to err on roughly half the inputs $(x,y)$. Choosing a large enough constant $c$, the correctness in the middle interval starts dominating: protocol guesses right with probability $1/2+\Theta(c/\sqrt{n})$ over $(x,y)$.

> **Comments:**
> **username_0**: Thanks for your answer. The protocol for inner product doesn't seem correct to me though. E.g., consider $n=3$. With respect to the protocol's internal randomness, the success probability is $1$ when $\langle x, y \rangle \in \{0, 3\}$, and the success probability is $1/3$ when $\langle x, y \rangle \in \{1, 2\}$. Therefore, the probability of getting good inputs $(x, y)$ is $(3/4)^3 + (1/4)^3 < 1/2$, so the protocol doesn't work. Or am I misunderstanding?  
> **username_1**: Sorry I was sloppy. I added details  

---

