Sorry, an error occurred while loading the content.

## [Computational Complexity] Thanks for better upper bound. Still want better l...

Expand Messages
• I posted on the max problem a while back. 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
Message 1 of 1 , Oct 13 8:48 AM
I posted on the max problem a while back.
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?
1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
What can L be? we needed 2L > L/n. L=lg n works. So this works in n+4lg n. You can do slightly better by taking L=lg n - lglg n.

--
Posted By GASARCH to Computational Complexity at 10/13/2008 10:47:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.