### New Strong Direct Product Results in Communication ComplexityNew Strong Direct Product Results in Communication Complexity

Access Restriction
Subscribed

 Author Jain, Rahul Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Communication complexity ♦ Information theory ♦ Strong direct product Abstract We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and ε > 0 be a constant. Let $R^{1,pub}_{ε}(f)$ represent the communication complexity of $\textit{f},$ with worst-case error ε in this model. We show that if for computing $f^{k}$ $(\textit{k}$ independent copies of $\textit{f})$ in this model, $\textit{o}(\textit{k}$ ċ R1, $pub}_{1/3}(f))$ communication is used, then the success is exponentially small in $\textit{k}.$ We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [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 nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct 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 proving that our new complexity measure gives a tight lower bound of $Ω(\textit{n})$ for the set-disjointness problem on $\textit{n}-bit$ inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 3 Page Count 27 Starting Page 1 Ending Page 27

#### Open content in new tab

Source: ACM Digital Library