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

Expand Messages

GASARCH

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

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 x_{1}...x_{m}
where each x_{i} is length L.
Bob views y as y_{1}...y_{m}
where each y_{i} is length L.

Alice sends to Bob a string A of length L that is NOT any of
x_{1},...,x_{m}.
Bob sends Alice a string B of length L that is NOT any of
y_{1},...,y_{m}.
Note: we will need 2^{L} > n/L.

So long as it looks like the strings are identical
They alternate sending the next block:
Alice sends x_{1}, Bob sends y_{2}
Alice sends x_{3}, Bob sents y_{4}
(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 x_{i} > y_{i} 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 x_{i} < y_{i} 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 2^{L} > 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.