1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – William Hoza Feb 9 at 19:21
  • $\begingroup$ Sorry I was sloppy. I added details $\endgroup$ – Tetsuya Ishigami Feb 10 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.