Average-case randomized communication complexity in the small-advantage regime

Question

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?

Answer 1

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), 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) 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)$.