Partition bound is quadratically tight for product distributions

Abstract

Let $f:\{0,1{\}}^n\times \{0,1{\}}^n\to \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1{\}}^n\times \{0,1{\}}^n$, we show that $${\mathsf{CC}}_{0.49}^{\mu }(f)=O\left({\left(\log {\mathsf{prt}}_{1/8}(f)\cdot \log \log {\mathsf{prt}}_{1/8}(f)\right)}^2\right),$$ where ${\mathsf{CC}}_{\epsilon }^{\mu }(f)$ is the distributional communication complexity of $f$ with error at most $\epsilon$ under the distribution $\mu$ and ${\mathsf{prt}}_{1/8}(f)$ is the {\em partition bound} of $f$, as defined by Jain and Klauck [{\em Proc. 25th CCC}, 2010]. We also prove a similar bound in terms of ${\mathsf{IC}}_{1/8}(f)$, the {\em information complexity} of $f$, namely, $${\mathsf{CC}}_{0.49}^{\mu }(f)=O\left({\left({\mathsf{IC}}_{1/8}(f)\cdot \log {\mathsf{IC}}_{1/8}(f)\right)}^2\right).$$ The latter bound was recently and independently established by Kol [{\em Proc. 48th STOC}, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let $g:\{0,1{\}}^n\to \{0,1\}$ be a function. For every bit-wise product distribution $\mu$ on $\{0,1{\}}^n$, we show that $${\mathsf{QC}}_{0.49}^{\mu }(g)=O\left({\left(\log {\mathsf{qprt}}_{1/8}(g)\cdot \log \log {\mathsf{qprt}}_{1/8}(g)\right)}^2\right),$$ where ${\mathsf{QC}}_{\epsilon }^{\mu }(g)$ is the distributional query complexity of $f$ with error at most $\epsilon$ under the distribution $\mu$ and ${\mathsf{qprt}}_{1/8}(g))$ is the {\em query partition bound} of the function $g$. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for {\em product} distributions.

arXiv commentThe previous version of the paper erroneously stated the main result in terms of relaxed partition number instead of partition number