Please use this identifier to cite or link to this item:
|Title:||A direct product theorem for the two-party bounded-round public-coin communication complexity|
|Authors:||Jain, R. |
|Source:||Jain, R., Pereszlenyi, A., Yao, P. (2012). A direct product theorem for the two-party bounded-round public-coin communication complexity. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS : 167-176. ScholarBank@NUS Repository. https://doi.org/10.1109/FOCS.2012.42|
|Abstract:||A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols , , , , . Our result generalizes the result of Jain  which can be regarded as the special case when t = 1. Our result can be considered as an important progress towards settling the strong direct product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain. One key tool used in our work and also in Jain  is a message compression technique due to Braver man and Rao, who used it to show a direct sum theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein for proving a parallel repetition theorem for two-prover games. © 2012 IEEE.|
|Source Title:||Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 14, 2017
WEB OF SCIENCETM
checked on Nov 20, 2017
checked on Dec 17, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.