KTH Exchange 20

Comm Cplx 終於到了最後一份功課, 其中一題 refer 到 lecture 1, 由於那一堂是剛好飛到 Stockholm 所以沒有上, 翻看 notes 才發現一個很有趣的問題:

假設 Alice 和 Bob 各自有 set A 和 B ⊆ {1,2, ..., N}
Define median(S) = S 中 element 的 median
Alice 和 Bob 目標是找 multiset A U B 的 median
這個問題的 deterministic communication upper bound 是 O(log N)

其中一個做法是 binary search median = k
Alice 告訴 Bob 在 A 中有少個 element > k, = k 和 < k
然後就可以把 median range 砍掉一半
一共是 O(log²N) bit
要降至 O(log N) bit, 用了一個很巧妙的 trick, 亦是這次功課的其中一條題目 (雖然 notes 給了大概的 idea)