Access Restriction

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

   Open content in new tab
Source: ACM Digital Library