- Alice sends the first \sqrt{2n} bits of x.
- 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.
- (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.
- (sketch) In the ith round, if there is one, Alice sends \sqrt{2n} - i bits.
It is easy to show that the max(x,y) problem requires n bits of communication (also left to the reader). So we have
- Upper bound of n+\sqrt{2n} +O(1).
- Lower bound of n.
- Close this gap! Or at least get a larger lower bound or a smaller upper bound.
- 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.
Does e eggs mean 2.718281828... eggs? Making those not broken is problematic, unless they have already been mapped into an omelette.
ReplyDeleteAlas, the problems with working with both
ReplyDeletediscrete and continous math.
e is an integer.
e is not 2.718...
This comment has been removed by the author.
ReplyDeleteThe 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.
ReplyDeleteYour 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).
Here's a protocol that requires only n + O(log n) bits.
ReplyDeleteAlice 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.
An n+O(log(n)) upper bound was recently given by Babaioff, Blumrosen, M. Naor and Schapira in EC'08 (Thm 3.2).
ReplyDeleteIt 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).
n + 2 bits.
ReplyDeleteAlice sends x to Bob. Bob sends 11 if greater, 00 if less, 01 if equal.
sep332, you missed the "both" part: "They want to both know max(x,y)"
ReplyDeletesep332, if Bob's number is greater, Alice still doesn't know what the greater number is.
ReplyDeleteAnd 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...).
This protocol only need n+2 bits. Is there anything wrong?
ReplyDelete1.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.
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? .
ReplyDeletepkughost wrote: This protocol only need n+2 bits. Is there anything wrong?
ReplyDeleteA 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.
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.
ReplyDeleteHowever, it is worth mentioning that these techniques were not widely understood until a series of talks and papers by Amihood Amir emerged.
Hm, I guess reading comprehension would be useful *before* I post!
ReplyDeleteThe Greater Than problem can be solved with polylog(n) bits of communication, by a randomized protocol (binary search for the longest common prefix).
ReplyDelete蒸馏塔
种子罐