THE MULITPARTY COMMUNICATION COMPLEXITY OF EXACT-T
Talk by Bill Gasarch
Work by Beigel, Gasarch, Glenn
Assume that Alice, Bob, and Carol all have
numbers on their foreheads, which we denote a,b,c.
Note that
Alice sees only b,c .
Bob sees only a,c.
Carol seens only a,c.
The numbers a,b,c are all n-bits long
so the numbers themselves are less than or equal to 2n.
They want to know if a+b+c=2n.
Alice COULD just say
``HEY, BOB, b is 100011001'',
which would take n bits.
CAN THEY DO BETTER THAN THIS?
1) It was shown in 1983 that
-
They can deterine if a+b+c = 2n with O(n1/2) bits,
-
The problem CANNOT be done with a constant number of bits.
2) WE show the following:
-
If there are k players and they all have numbers on foreheads
then it can be done with O(n1/(k-1)) bits
-
In the 3 player case it requiers Ω(log log n)
-
We have some empirical studies as well in the 3-player case.