Monday, September 22, 2008

The Communication Complexity of MAX: Open problem

Alice has x, an n-bit integer. Bob yas y, an n-bit integer. They want to both know, max(x,y). This can be done with n + \sqrt{2n} + O(1) bits of communication.
  1. Alice sends the first \sqrt{2n} bits of x.
  2. If Bob can deduce that x LESS THAN y then he sends 11y and they are DONE. If Bob can deduce that x GREATER THAN y then he sends 10, Alice sends the rest of x, and they are done. If the first \sqrt{2n} bits of x and y are the same then Bob sends 0.
  3. (This step is reached only if x and y agree on the first \sqrt{2n} bits.) Alice sends the next \sqrt{2n}-1 bits of x. If Bob can deduce that x LESS THAN y then he sends 11 followed by all BUT the first \sqrt{2n} bits of y (which Alice already knows since they are the same as hers) and they are DONE. If Bob can deduce that x GREATER THAN y then he sends 10, Alice sends the rest of x, and they are done. If the first \sqrt{2n} bits of x and y are the same then Bob sends 0.
  4. (sketch) In the ith round, if there is one, Alice sends \sqrt{2n} - i bits.
We leave the analysis that this takes n+\sqrt{2n}+O(1) bits to the reader.

It is easy to show that the max(x,y) problem requires n bits of communication (also left to the reader). So we have
  1. Upper bound of n+\sqrt{2n} +O(1).
  2. Lower bound of n.
Open Problems
  1. Close this gap! Or at least get a larger lower bound or a smaller upper bound.
  2. The protocol above is similar to the following problem: Assume there is a building is n stories high and there is some floor f such that, dropping an egg off of floor f it will break, but off of floor f-1 it will not. If you have 2 eggs, how many egg-dropping do you need to determine f? (NOTE- if an egg breaks you cannot reuse it.) For 2 egges you can do this with \sqrt{2n}+O(1) egg-droppings (and this is tight). For e eggs you can do this with (e!)1/en1/e+O(1) droppings (and this is tight). See this paper for writeups of these results. (NOTE: I am sure this problem is ``well known'' but have not been able to find references. If you know any please comment or email so I can insert them into the writeup.) Is there some communication complexity problem for which the e-egg problem supplies the key to the answer.

15 comments:

  1. Does e eggs mean 2.718281828... eggs? Making those not broken is problematic, unless they have already been mapped into an omelette.

    ReplyDelete
  2. Alas, the problems with working with both
    discrete and continous math.
    e is an integer.
    e is not 2.718...

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. The Greater-Than problem is the following: Alice receives x, an n-bit number; Bob receives y, an n-bit number; they want to determine whether x>y.

    Your problem's bit complexity is n + complexity of GT.

    The Greater Than problem can be solved with polylog(n) bits of communication, by a randomized protocol (binary search for the longest common prefix).

    So there's your improvement, unless your really wanted deterministic protocols. If you want deterministic, you can't go via this routa (GT requires linear complexity, like equality).

    ReplyDelete
  5. Here's a protocol that requires only n + O(log n) bits.

    Alice finds two (log n)-bit strings a_small and a_large that do not
    appear in x and sends them to Bob. Bob finds two (log n)-bit strings
    b_small and b_large that do not appear in y and sends them to Alice.
    Alice and Bob take turns exchanging log n bit chunks of x and y.
    If either one discovers that their number is larger or smaller,
    they substitute the appropriate codeword, and the party with the
    larger number sends the rest.

    ReplyDelete
  6. An n+O(log(n)) upper bound was recently given by Babaioff, Blumrosen, M. Naor and Schapira in EC'08 (Thm 3.2).

    It was given in the context of the communication overhead for computing payments in auctions. This problem is equivalent to solving a two player second-price auction (the price paid is the minimal value of the two).

    ReplyDelete
  7. n + 2 bits.

    Alice sends x to Bob. Bob sends 11 if greater, 00 if less, 01 if equal.

    ReplyDelete
  8. sep332, you missed the "both" part: "They want to both know max(x,y)"

    ReplyDelete
  9. sep332, if Bob's number is greater, Alice still doesn't know what the greater number is.

    And to the anonymous before liad, it seems like the number of passes required by this algorithm will not be O(1); I believe that an n+O(logn) bound might exist (viz. liad's post), but it is not clear that this algorithm reaches it (indeed, you haven't supplied a mechanism for Alice or Bob to use this data to determine which number is greater at all...).

    ReplyDelete
  10. This protocol only need n+2 bits. Is there anything wrong?

    1.Alice sends first two bits of x.
    2.Bob sends 1) 0, if x is bigger.
    2)y, if y is bigger.
    3)next two bits of y, if the first two bits is the same.
    3.Alice makes the similar choice like Bob (swap x and y), except in the second condition Alice sends all but first two bits of x. And the following steps are all like this.
    4.Make some special rules of the last one or two bits.

    ReplyDelete
  11. The egg problem is mentioned in Peter Winkler's Mathematical mind-benders . He refers to Konhauser, Velleman and Wagon, Which way did the bicycle go? .

    ReplyDelete
  12. pkughost wrote: This protocol only need n+2 bits. Is there anything wrong?

    A requirement of communication protocols is that after each bit is sent, the player to communicate the next bit is determined by the communication so far. Your protocol does not have the required property.

    ReplyDelete
  13. I was interested to see the e-egg problem described as it is also the basis of many of the modern improvements in computational pattern matching. For example, pattern matching under the Hamming, L_1 norm etc. (typically the complexity you get is something like O(n sqrt{m log m}). The basic technique is normally attributed, in that field at least, to both Abrahamson's "Generalized string matching", SIAM journal on Computing, 16:(6) pages 1039--1051, 1987 and an unpublished manuscript called "Efficient string matching" by S. R. Kosaraju in the same year.

    However, it is worth mentioning that these techniques were not widely understood until a series of talks and papers by Amihood Amir emerged.

    ReplyDelete
  14. Hm, I guess reading comprehension would be useful *before* I post!

    ReplyDelete
  15. The Greater Than problem can be solved with polylog(n) bits of communication, by a randomized protocol (binary search for the longest common prefix).
    蒸馏塔
    种子罐

    ReplyDelete