The 2-party communication setting consists of two players, Alice and Bob, who are given two input strings, \(x,y\in \left\lbrace 0,1\right\rbrace ^K\)  respectively,
and need to evaluate some given function \(f:\left\lbrace 0,1\right\rbrace ^K\times \left\lbrace 0,1\right\rbrace ^K\rightarrow \left\lbrace \mathrm {true},\mathrm {false}\right\rbrace \)  on their inputs.
The maximal number of bits, over all inputs, exchanged in a protocol \(\pi \)  that computes
\(f\)  is the communication complexity of \(\pi \) and is denoted \(CC(\pi )\) . The communication complexity of the function \(f\) is the minimum of \(CC(\pi )\)  over all deterministic protocols \(\pi \)  that compute \(f\)  and is denoted \(CC(f)\) . In a similar manner, for randomized protocols, the randomized communication complexity of \(f\)  is denoted \(CC^R(f)\) .
In the set disjointness problem, the problem is to compute a boolean function
\(DISJ_K\)  defined as \(DISJ_K(x, y) = \mathrm {false}\)  if and only if there is an index \(0\le i\le K-1\)  such that \(x_i=y_i=1\) . It is well known that that \(CC(DISJ_K), CC^R(DISJ_K)\)  are both \(\Theta (K)\)  (see, e.g., [1]}).
