In this paper, we show a direct product theorm in the model of two-party bounded-round public-coin randomized communication complexity. For a relation f subset of X times Y times Z (X,Y,Z are finite sets), let R^{(t), pub}_e (f) denote the two-party t-message public-coin communication complexity of f with worst case error e. We show that for any relation f and positive integer k: R^{(t), pub}_{1 - 2^{-Omega(k/t^2)}}(f^k) = Omega(k/t (R^{(t), pub}_{1/3}(f) - O(t^2))) . In particular, it implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations f. Our result for example implies 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. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in [Jain 2011], where a strong direct product theorem for the two-party one-way public-coin communication complexity of all relations is shown (that is the special case of our result when t=1). One key tool used in our work and also in [Jain 2011] is a message compression technique due to [Braverman and Rao 2011], who used it to show a direct sum theorem for the two-party bounded-round public-coin randomized communication complexity of all relations. Another important tool that we use is a correlated sampling protocol, which for example, has been used in [Holenstein 2007] for proving a parallel repetition theorem for two-prover games.
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 [2011] 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~\cite{Jain:2011}. %, where a strong direct product theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when
t=1). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em 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~\cite{Holenstein2007} for proving a parallel repetition theorem for two-prover games.
We show a direct product result for two-way public coin communication complexity of all relations 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 08], thereby our result implying their direct product result in terms of the two-way product subdistribution bound. We show that our new complexity measure gives tight lower bound for the set-disjointness problem, as a result we reproduce strong direct product result for this problem, which was previously shown by [Klauck 00].