As we will discuss in the next post, for some application it suffices to get lower bounds on the one-way communication complexity -- that is, the case in which a single message is sent, either from Alice to Bob, or from Bob to Alice. The party receiving the message must immediately announce to answer, based on the message and their own input.
- EA[k] = 0.01 n. Indeed, for uniformly random A and i, the algorithm works with probability 0.99. So in expectation over A, the bad set of indices has size 0.01 n.
- By the Markov bound, PrA[k ≤ 0.02 n] ≥ 1/2.
- When k ≤ 0.02 n, lg(n choose k) ≤ n/2.
- When k ≥ 0.02 n, lg(n choose k) ≤ n.
- Therefore E[lg(n choose k)] ≤ 0.75 n.
Say Alice and Bob receive two set of n elements from the universe [n2]. Show that the one-way randomized communication complexity of set disjointness is Ω(n lg n) bits.This is the best result possible, since Alice can specify her entire set with O(n lg n) bits, after which Bob knows the answer with no error.