We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least α(n) on yes-inputs and at most β(n) on no-inputs, for some functions α(n) > β(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions α and β, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where α = 1/2+ (n) and β = 1/2− (n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a “restricted” class SBP (which lies between MA and AM) and an “unrestricted” class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least α(n) on yes-inputs and at most β(n) on no-inputs, for some functions α(n) > β(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions α and β, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where α = 1/2+ (n) and β = 1/2− (n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a “restricted” class SBP (which lies between MA and AM) and an “unrestricted” class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions alpha and beta, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where alpha=1/2+epsilon(n) and beta=1/2-epsilon(n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a "restricted" class SBP (which lies between MA and AM) and an "unrestricted" class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
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 f , with worst-case error ϵ in this model. We show that if for computing f k ( k independent copies of f ) in this model, o ( k ċ R 1, pub 1/3 ( f )) communication is used, then the success is exponentially small in 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 Ω( n ) for the set-disjointness problem on 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.
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 e > 0 be a constant. Let R1,pube(f) represent the communication complexity of f, with worst-case error e in this model. We show that if for computing fk (k independent copies of f) in this model, o(k c R1, pub1/3(f)) communication is used, then the success is exponentially small in 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 Ω(n) for the set-disjointness problem on 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.
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].
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.
In a multiparty message-passing model of communication, there are k players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in secure multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work [25], [29], [30], strong lower bounds of the form Ω(n·k) were obtained for several functions in the message-passing model; however, a lower bound on the classical set disjointness problem remained elusive. In this paper, we prove a tight lower bound of Ω(n · k) for the set disjointness problem in the message passing model. Our bound is obtained by developing information complexity tools for the message-passing model and proving an information complexity lower bound for set disjointness.