Alice has x, an n-bit integer. Bob has y, an n-bit integer. They want to both know, max(x,y). This can be done with a deterministic n + \sqrt{2n} + O(1) bits. Can they do better?Anon Comment 5 on that post, and possibly a paper that was pointed to, lead to a Deterministic Protocols that took n+O(log(n)) bits. I am presenting it carefully in this post, hoping that someone will NOW prove the lower bound OR get an even better upper bound.
When I had the upper bound of n +\sqrt{2n} + O(1) I thought it was optimal. Now that I have the upper bound of n+O(log n) + O(1) I'm not so sure. This is a good example of why lower bounds are so interesting- someone clever may come along with a better algorithm-- How to you prove that they can't?
- Alice has x, Bob has y. L is a paramter to be determined later. We will assume L divides n. Let m=L/n. Alice views x as x1...xm where each xi is length L. Bob views y as y1...ym where each yi is length L.
- Alice sends to Bob a string A of length L that is NOT any of x1,...,xm. Bob sends Alice a string B of length L that is NOT any of y1,...,ym. Note: we will need 2L > n/L.
- So long as it looks like the strings are identical They alternate sending the next block: Alice sends x1, Bob sends y2 Alice sends x3, Bob sents y4 (NOTE- nobody has to send a bit saying `we are tied'.) They keep doing this until one of them notices that the strings are NOT equal. If they they never discover this then they spend n+Lb bits and discover x=y. They both know max since its x=y.
- If Bob notices that xi > yi then he will send B0. Alice knows that B can't be one of Bob's segments, so she knows why Bob send this. She will then send the rest of her string that she has not already send. They both know max(x,y). This took n+3L bits.
- If Bob notices that xi < yi then he will send B1. Alice knows that B can't be one of Bob's segments, so she knows why Bob send this. Bob will then send the rest of his string. They both know max(x,y). This took n+4L bits.
A few typos: you use A and B as terminating strings at the beginning, B0 and B1 later. The condition on L is mistyped as 2^L > L/n at the end. Also, L = lg(n) - lg(lg(n)) appears not to work, e.g. n = 256, L = 8 - 3, 2^L is too small.
ReplyDeleteI might be a bit daft - but what is stage #2 for? Can't it be skipped?
ReplyDeleteI think L = lg(n) - lg(lg(n) - lg(lg(n))) works as a slightly better version of L = lg(n).
ReplyDeleteTo anonymous above - the parties need some way to signal to each other that received a block not identical to their own, and therefore they should stop the exchange and the larger party should transmit the rest. You need some way to make this signal stand out from a regular block of L bits in step 3. If you use even one additional 'control bit' in every transmission, you're already wasting too many bits. Stage #2 is a neat trick to avoid that.
Why are you interested in this gap between n and n+O(lg n), for a rather uninteresting problem?
ReplyDeleteIf you had looked at the analysis in the paper, you would have seen that they get n + 2 log n + O(1).
ReplyDelete-Anon 5 from the previous post
Proving lower bound: Has anybody tried to count number of possible m-bit communications and compare it to the number of possibilities of input?
ReplyDeleteAnon #6: if you want to try a counting argument, you're going to have to explain why the same argument doesn't also apply to the variation of the problem in which the two players don't care to know what value the max has, they only want to know which one of them has it. That problem can be solved easily in n+1 bits: the first player sends her number to the second, and the second one sends back one bit saying who has the max.
ReplyDeleteL must be at least L => W(N ln2)/ln2
ReplyDeleteWhere W(x) is the Lambert W function, which is the inverse of f(x) = xe^x.
W is also the solution of W(x) = ln(x)-ln(W(x)) so L = lg(n) - lg(lg(n) - lg(lg(n))) is pretty close.
I am always wondering, why theoretical computer science is never taking physical time into account. At least with quantum computers, a direct connection to physical time does exist and synchronization of imperfect clocks of classical computers (see Lynch's book) is no longer an issue. So, lets extend our model by assuming Alice and Bob both having access to the ticks of physical time. Alice proceeds by sending the most significant bit first in, say, a clock tick and then waits for a maximum timeout of anohter tick for Bob's response. If there is no response, Alice proceeds with sending her next significant bit and so forth. Bob will only respond to Alice's transmission if he detects a mismatch with the respective bits of his own bit string. If he detects a mismatch, Bob will take over control and transmit all further bits of his string. In any case, both parties will know the maximum of both bit strings at the end of the protocol by combining the two half strings in the obvious way. The number of bits transmitted is exactly n+1 (the extra bit was the first and most significantly mismatching bit). The new resource to bound in this example is physical time spent by the protocol. In the worst case it will take Alice 2n time ticks to transmit n bits: one for transmitting, one for listening. If Alice and Bob shared a full-duplex channel (a pair of opposite unidirectional channels), Alice could transmit on bit per tick and listen on the other channel for Bob's response. In such a model, exactly n+1 bits and n+1 time ticks are consumed. Acknowledgements: The idea of using time to communicate by not sending something is not new and due to a 1984 paper of Leslie Lamport, as far as I am aware of.
ReplyDeletePerhaps I'm missing something, but this result only seems to hold if we know that n has a prime factor of O(log n).
ReplyDeleteWhat if n is prime?
TheKro, for the last chunk, which is (n mod L) bits long, just budget a couple of bits from the O(1) term to signal more efficiently than sending a length L chunk.
ReplyDeleteAnon #8 gives no proof, and hardly an explanation, but his solution sounds very close to the truth, perhaps exactly the truth. Using the special markers A and B is similar to the need to send an end-of-file marker or an escape symbol when compressing.
ReplyDeleteIf I had to guess, then #8 is either a compression person, or Mihai Patrascu. The arrogant style fits Mihai just fine, as well.
Not a Romanian, Anon 8's bound comes from a simple manipulation of the algebra; We require that 2^L > ceil(N/L), so
ReplyDeletee^(L lg2) > N/L
(L lg2) e^(L lg2) > N lg2
L lg2 > W(N lg2)
L > W(N lg2)/lg2
The Kro, we don't need L to divide evenly into N; as long as the choice of L is deterministic (the ceiling of the logarithm, for example), we can just pad N with leading zeros to divide things evenly.
This comment didn't go through before (probably I forgot to click the last button), so I'm trying again. If you can show that the guy with the largest number knows roughly (say within log n bits) which is the first bit that differs, then information theory gives the correct lower bound. I don't see how to prove this, but my intuition says that in any good protocol, he will know this.
ReplyDeleteA small optimization: suppose we relax the requirement that the special block of L bits occurs nowhere in the number. Instead, disambiguate it. Every time it is sent, it's followed by 0 if it's actually a normal block occurring in the number, by 10 if it's special and A > B, and by 11 if it's special and A < B.
ReplyDeleteLet's choose the least frequent among all the L-bit blocks, then in the worst case it occurs n/(L*2^L) times. The total number of bits is n + 4L + n/(L*2^L) + O(1). The trade-off between the second and third summands is a little more favorable than the previous condition on L. In particular, L = lg(n) - lg(lg(n)) really works here. Probably some better functions do, too, although not as good as lg(lg(n)).