[39] Let L ⊂ {0, 1}2n be a language to be recognized by two parties P and Q with unlimited computation power. Party P knows the first n bits of the input and party Q knows the last n bits. P and Q exchange messages to recognize L according to some bounded-error two-way probabilistic protocol. An input is accepted if the probability of acceptance is at least 1 −  for some fixed , 0 ≤  < 1 2 ; an input is rejected if the probability of rejection is at least 1 − ; and every input must be either rejected or accepted. The probabilistic communication complexity of an input (x1,...,x2n) is the worst case, over all sequences of fair coin tosses, of the number of bits exchanged. The probabilistic communication complexity of the language is the maximum of this over all inputs. The set intersection language SETIN is defined to be the set of all sequences a1 ...anb1 ...bn over {0, 1} with n i=1 aibi ≥ 1. (P knows a1,...,an and Q knows b1,...,bn.) Prove that the probabilistic communication complexity of SETIN is Ω(n).

Comments. Source: [B. Kalyanasundaram and G. Schnitger, SIAM J.

Discrete Math., 5:4(1992), 545–557].