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

Abstract

We present a linear program for a one-way version of the partition bound of Jain and Klauck, denoted ${\mathsf{prt}}_{\epsilon }^1(f)$, and show that it characterizes the one-way randomized communication complexity ${\mathsf{R}}_{\epsilon }^1(f)$ with shared randomness and worst-case error $\epsilon$ of any relation $f\subseteq \mathcal{X}\times \mathcal{Y}\times \mathcal{Z}$. More precisely, for all $\epsilon ,\delta \in (0,1/2)$, ${\mathsf{R}}_{\epsilon }^1(f)\ge \log {\mathsf{prt}}_{\epsilon }^1(f)$ and ${\mathsf{R}}_{\epsilon +\delta }^1(f)\le \lceil \log {\mathsf{prt}}_{\epsilon }^1(f)+\log \log (1/\delta )\rceil$. This improves upon the characterization of ${\mathsf{R}}_{\epsilon }^1(f)$ in terms of the rectangle bound due to Jain, Klauck, and Nayak [STOC'08], which is tight only up to an additive $O(\log (1/\delta ))$ term.

arXiv comment7 pages. v2: generalised the results to relations