Relaxed partition bound is quadratically tight for product distributions
Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan · arXiv (Cornell University) · 2015
where CCe p f q is the distributional communication complexity with error at most e under the distribution μ and rprt1{4p f q is the relaxed partition bound of the function f , as introduced by Kerenidis et al. [8]. A similar upper bound for communication complexity for product distributions in terms of information complexity was recently (and independently) obtained by Kol [9]. We show a similar result for query complexity under product distributions. Let g : t0, 1un N t0, 1u be a function. For every bit-wise product distribution μ on t0, 1un, we show that