Partition Bound is Quadratically Tight for Product Distributions

In a sequence of remarkable results, Ganor, Kol and Raz, over the last couple of years, show that there exist non-product distributions which exhibit exponential separation between internal information complexity and distributional communication complexity. However, it is still open if internal information complexity (or a polynomial of it) upper bounds the public-coin randomized communication complexity (up to logarithmic multiplicative factors in the input size). In this result, we show that when the inputs to the two parties are drawn from a product distribution, this is indeed the case. Informally, we show that for product distributions, the two-party public-coin randomized communication complexity CC(f) is at most quadratically larger than either the partition bound prt(f) or the information complexity IC(f) (i.e., CC(f) = O( (prt(f) \log prt(f))^2 ) and CC(f) = O( (IC(f) \log IC(f))^2 )). Similar results for CC(f) vs IC(f) were independently obtained by Kol recently.