Please use this identifier to cite or link to this item: https://doi.org/10.1109/FOCS.2012.42
Title: A direct product theorem for the two-party bounded-round public-coin communication complexity
Authors: Jain, R. 
Pereszlenyi, A.
Yao, P.
Keywords: bounded rounds
Communication complexity
direct product
information theory
Issue Date: 2012
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 [27], [18], [29], [20], [14]. Our result generalizes the result of Jain [11] 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[11]. One key tool used in our work and also in Jain [11] is a message compression technique due to Braver man and Rao[5], 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[9] for proving a parallel repetition theorem for two-prover games. © 2012 IEEE.
Source Title: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
URI: http://scholarbank.nus.edu.sg/handle/10635/40762
ISSN: 02725428
DOI: 10.1109/FOCS.2012.42
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

17
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

7
checked on Nov 20, 2017

Page view(s)

181
checked on Dec 17, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.