Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-024 | 25th February 2011 11:08

New strong direct product results in communication complexity


Authors: Rahul Jain
Publication: 25th February 2011 13:07
Downloads: 3698


We show two new direct product results in two different models of communication complexity. Our first result is in the model of one-way public-coin model. Let $f \subseteq X \times Y \times Z $ be a relation and $\epsilon >0$ be a constant. Let $R^{1,pub}_{\epsilon}(f)$ represent the communication complexity of $f$, with worst case error $\epsilon$ in this model. We show that if for computing $f^k$ ($k$ independent copies of $f$) in this model, $o(k \cdot R^{1,pub}_{1/3}(f))$ communication is provided, then the success is exponentially small in $k$. To our knowledge this is the first time a strong direct product result holding for all relations has been shown in any model of communication complexity. We show a new tight characterization of communication complexity in this model which strengthens on the tight characterization shown in J., Klauck, Nayak, 2008. We use this new characterization to show our direct product result and this characterization may also be of independent interest.

Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to non-product distributions, of the two-way product subdistribution bound of J., Klauck and Nayak, 2008. Our direct product result therefore generalizes to non-product distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck, 2010. We show this by showing that our new complexity measure gives tight lower bound of $\Omega(n)$ for the set-disjointness problem on $n$-bit inputs. In addition we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.

ISSN 1433-8092 | Imprint