Room 327

Partition bound is quadratically tight for product distributions

Prahladh Harsha

TIFR

Over the last few decades, several lower bound techniques (eg., LP-based approaches such as partition bound, the information theoretic approaches such as information complexity) have been developed to bound the two-party public-coin randomized communication complexity. 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.