A note on the partition bound for one-way classical communication complexity

Abstract

We present a linear program for the one-way version of the partition bound (denoted ${\mathsf{prt}}_{\epsilon }^1(f)$). We show that it characterizes one-way randomized communication complexity ${\mathsf{R}}_{\epsilon }^1(f)$ with shared randomness of every partial function $f:\mathcal{X}\times \mathcal{Y}\to \mathcal{Z}$, i.e., for $\delta ,\epsilon \in (0,1/2)$, ${\mathsf{R}}_{\epsilon }^1(f)\ge \log {\mathsf{prt}}_{\epsilon }^1(f)$ and ${\mathsf{R}}_{\epsilon +\delta }^1(f)\le \log {\mathsf{prt}}_{\epsilon }^1(f)+\log \log (1/\delta )$. This improves upon the characterization of ${\mathsf{R}}_{\epsilon }^1(f)$ in terms of the rectangle bound (due to Jain and Klauck, 2010) by reducing the additive $O(\log (1/\delta ))$-term to $\log \log (1/\delta )$.

6 pages