Abstract
Let f: {0,1}^n*{0,1}^n > {0,1} be a 2party function. For every product distribution mu on {0,1}^n*{0,1}^n, we show that
CC^{mu}_{0.49}(f) = O(log(prt_{1/8}(f))*log(log(prt_{1/8}(f)))^2),
where CC^{mu}_{epsilon}(f) is the distributional communication complexity of f with error at most epsilon under the distribution mu and prt_{1/8}(f) is the partition bound of f, as defined by Jain and Klauck [Proc. 25th CCC, 2010]. We also prove a similar bound in terms of IC_{1/8}(f), the information complexity of f, namely,
CC^{mu}_{0.49}(f) = O((IC_{1/8}(f)*log(IC_{1/8}(f)))^2).
The latter bound was recently and independently established by Kol [Proc. 48th STOC, 2016] using a different technique.
We show a similar result for query complexity under product distributions. Let g: {0,1}^n > {0,1} be a function. For every bitwise product distribution mu on {0,1}^n, we show that
QC^{mu}_{0.49}(g) = O((log(qprt_{1/8}(g))*log(log(qprt_{1/8}(g))))^2),
where QC^{mu}_{epsilon}(g) is the distributional query complexity of f with error at most epsilon under the distribution mu and qprt_{1/8}(g) is the query partition bound of the function g.
Partition bounds were introduced (in both communication complexity and query complexity models) to provide LPbased lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for product distributions.
BibTeX  Entry
@InProceedings{harsha_et_al:LIPIcs:2016:6270,
author = {Prahladh Harsha and Rahul Jain and Jaikumar Radhakrishnan},
title = {{Partition Bound Is Quadratically Tight for Product Distributions}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {135:1135:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6270},
URN = {urn:nbn:de:0030drops62708},
doi = {10.4230/LIPIcs.ICALP.2016.135},
annote = {Keywords: partition bound, product distribution, communication complexity, query complexity}
}
Keywords: 

partition bound, product distribution, communication complexity, query complexity 
Collection: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

23.08.2016 