I am working on exercise 1.6 of the textbook Communication Complexity and Applications by Anup Rao and Amir Yehudayoff.

Alice and Bob get sets X and Y in {1,2,...,n} respectively and they want to compute median of X union Y. The exercise asks to show a lower bound of Omega( n / log n ).

For example, if the sets are X = {1,2,4}, Y = {2,3,4}, then X union Y = {1,2,3,4} and the median is (2+3)/2=2.5.

This problem is different from computing the median of two lists.

For example, if X = {1,2,4}, Y = {2,3,4} are viewed as lists, the X union Y = {1,2,3,3,4,4} and the median is (3+3)/2 = 3.

The median of union of lists has communication complexity O(log n) (See here).

There is a hint in the textbook:

compute the median of union of sets, as well as the median of the union of the lists.

All my methods failed, such as Krapchenko's method or finding a bad sets of inputs. Maybe I didn't use these methods correctly. Could someone help?

  • $\begingroup$ This may be considered to be an exercise, not a research-level question, and so not appropriate for cstheory.se. If so, maybe try cs.stackexchange.com? $\endgroup$
    – Neal Young
    Feb 21 at 20:12
  • 1
    $\begingroup$ Can you reduce set disjointness to it? See e.g. dx.doi.org/10.4086/toc.2007.v003a011 . Or use similar techniques to directly show a lower bound? $\endgroup$
    – Neal Young
    Feb 21 at 20:36


Browse other questions tagged .