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

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?

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)$$.
• 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? Feb 9, 2021 at 19:21