Transcript The Model

Communication
Complexity
Guy Feigenblat
Based on lecture by Dr. Ely Porat
Some slides where adapted from various sources
Complexity course
Computer science department , Bar-Ilan university
January 2008
The Model
•
2 Computers : Alice (A) ,Bob (B)
All calculations for A are free
All calculations for B are free
Algorithm costs are measured by cost of
communications.
Cost is measured per bits
•
Motivation – Distributed models
•
•
•
•
The Model
14, 29,53,28,284,348
(98)
00100110
39, 67,98,22,35,253
(48)
01110110
B
A
Communication Complexity
Our goal
Minimize the communication between A,B while
calculating functions on their inputs
First Problem



Input
A has array of n numbers
B has array of n numbers
Output
median of all 2n numbers
Numbers are O(log n) bits long
Naive Solution
1.
2.

A sends all of his numbers to B
B calculates median of all 2n numbers
Cost

Each number is O(log n) bits

n numbers are sent

Total cost is O(n*log n) bits
Naive Solution
14, 29,53,28,284,348
(14)
001110
(53)
101011
(29) 10111
(348) 001110101
39, 67,98,22,35,253
(284) 00011111
B
A
Communication Complexity
Total cost is O(n*log n) bits
Better algorithm
1.
2.
A sorts his array and sends his median (
to B
B sorts his array and sends his median (
to A.
Exercise :
define :
prove :
M A)
MB )
r = real median
b = MAX{ MA , MB }
s = MIN { M , M }
srb
A
B
8
Better algorithm
A sort his array
and find his
median
B sort his array
and find his
median
14, 28,29,53,284,348,500
22, 35,39,67,98,253,300
B
A
Communication Complexity
Better algorithm
B send his
median to A
A send his
median to B
67
14, 28,29,53,284,348,500
22, 35,39,67,98,253,300
53
B
A
Communication Complexity
Better algorithm
4. If
M A = M B then return M A( = M B )
5. If M A > M B then A throws top (n/2)
elements B throws low (n/2) elements
6. Otherwise, vice versa
We reduces the size of the problem by half
7. Back to step 1, until size of arrays = 1
Better algorithm
53<67
67>53
Then A throws
the small half
of his array
Then B throws
the big half of
his array
,53,284,348,500
22, 35,39,67
B
A
Communication Complexity
Better algorithm
,53,284,348,500
We will repeat this algorithm until
the size of the array will be 1,
while every loop the array is cut in
half, and log n bits transferred
22, 35,39,67
Total cost is
CCmid = O (log2n) bits
B
A
Communication Complexity
Even Better algorithm
Exercise:
Try reducing the communication complexity to
O(log n) bits
EQ
The previous subject talked about problem of finding
median of a divided array.
Now we consider a new problem : Each side has a
number and we want to know if the numbers are equal.
?
X=Y
B
A
Communication Complexity
Deterministic Algorithm
Send all the data
We can’t avoid it !!
Think why ?
Probabilistic Algorithm
Analysis
CC 1 ( EQ)  O (log n)
n2
Like Co-RP
How can we lower the failure
probability ?

Run the experience few times

Use larger “q” (i.e. q = n10 )
G – Communication Complexity



Till now we had to send the Random number.
Consider a model in which A,B use a third party in
order to synchronize random numbers.
A,B use exactly the same random
“Alise on the moon, Bob on earth, both take random from the
sun”
Hard to “understand” – Remember this is just a model!!
Protocol
Analysis

Completeness – Perfect Completeness
If A=B then all i times

(a,r) = (b,r)
Soundness –
If A≠B
the probability that all i times (a,r) = (b,r) is 2-i

Communication Complexity
GCC 1 ( EQ)  O(i )  O(1)
2i
Exercise
Define LE to be :
LE(x,y) =
1 x≤y
0 otherwise
Show that
CC 1 ( LE )  O (log 2 n)
n
Theorem:
CC1 ( L)  O(GCC1 ( L)  log n)
2
2
We prove that we can give up synchronized random
with an overhead of O(logn) communication bits.
We will choose the same random
numbers (n2) using deterministic
machine for both A,B
R  r1, r2, ...rn 2
i ri {0,1}n
Protocol
A choose i R [n 2 ] and send it to B
If algorithm GCC1 ( L) exists for L, we will run it 3
times and use it.
2
CC 1 ( L)  O(GCC1 ( L)  log n)
2
8
GCC1 ( L)  g (n)
2
GCC1 ( L)  3g (n)
8
As for the proof…
We have perfect completeness in GCC (L)
But, we need to prove soundness
For the
chosen i
It is equivalent to argue:
By union bound:
We have proved that there exist a group of
R  r1, r2, ...rn 2
i ri {0,1}n
There is a deterministic algorithm that can find
them.
Remember, both A and B have unlimited
computational power.