Rahul Jain, Centre for Quantum Technologies/National University of Singapore (CQT/NUS)
Abstract
Abstract: 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 subset of X times Y times Z be a relation and eps be a constant. Let R^{1,pub}_eps(f) represent the communication complexity of f, with worst case error eps in this model. We show that if for computing f^k (k independent copies of f) in this model, o(k R^{1,pub}_eps(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.
Talk based on http://www.eccc.uni-trier.de/report/2011/024/