Harsha, Prahladh ;
Jain, Rahul
A Strong Direct Product Theorem for the Tribes Function via the SmoothRectangle Bound
Abstract
The main result of this paper is an optimal strong direct
product result for the twoparty publiccoin randomized communication
complexity of the Tribes function. This is proved by providing an
alternate proof of the optimal lower bound of Omega(n) for the randomised communication complexity of the Tribes function using the socalled smoothrectangle bound, introduced by Jain and Klauck [CCC/2010]. The optimal Omega(n) lower bound for Tribes was originally proved by Jayram, Kumar and Sivakumar [STOC/2003], using a more powerful lower bound technique, namely the information complexity bound. The information complexity bound is known to be at least as strong a lower bound method as the smoothrectangle bound [Kerenidis et al, 2012]. On the other hand, we are not aware of any function or relation for which the smoothrectangle bound is (asymptotically) smaller than its publiccoin randomized communication complexity. The optimal direct product for Tribes is obtained by combining our smoothrectangle bound for tribes with the strong direct product result of Jain and Yao (2012) in terms of smoothrectangle bound.
BibTeX  Entry
@InProceedings{harsha_et_al:LIPIcs:2013:4367,
author = {Prahladh Harsha and Rahul Jain},
title = {{A Strong Direct Product Theorem for the Tribes Function via the SmoothRectangle Bound}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {141152},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897644},
ISSN = {18688969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4367},
URN = {urn:nbn:de:0030drops43670},
doi = {10.4230/LIPIcs.FSTTCS.2013.141},
annote = {Keywords: Rectangle bound, Tribes function, Strong direct product}
}
2013
Keywords: 

Rectangle bound, Tribes function, Strong direct product 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Issue date: 

2013 
Date of publication: 

2013 