  Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{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}^\mu_{0.49}(f) = O\left(\left(\log
\mathsf{prt}_{1/8}(f) \cdot \log \log \mathsf{prt}_{1/8}(f)\right)^2\right),$$
where $\mathsf{CC}^\mu_\varepsilon(f)$ is the distributional communication
complexity of $f$ with error at most $\varepsilon$ 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}^\mu_{0.49}(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 \rightarrow \{0,1\}$ be a function. For every bit-wise
product distribution $\mu$ on $\{0,1\}^n$, we show that
$$\mathsf{QC}^\mu_{0.49}(g) = O\left(\left( \log \mathsf{qprt}_{1/8}(g) \cdot
\log \log\mathsf{qprt}_{1/8}(g) \right)^2 \right),$$ where
$\mathsf{QC}^\mu_{\varepsilon}(g)$ is the distributional query complexity of
$f$ with error at most $\varepsilon$ 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.
