Transcript Communication complexity

‫‪Communication Complexity‬‬
‫מגישים‪:‬‬
‫מיכאל זמור‪317735678 :‬‬
‫‪01762926/2‬‬
‫אבי מינץ‪:‬‬
‫ערן מנצור‪ :‬ת‪.‬ז‪02801532/9 .‬‬
‫‪1‬‬
Communication Complexity
The Model
• 2 Computers : A,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
2
Communication Complexity
The Model
14, 29,53,28,284,348
(98) 00100110
39, 67,98,22,35,253
(48) 01110110
B
A
Communication Complexity
3
Example
•
Input
A has array of n numbers
B has array of n numbers
• Output
median of all 2n numbers
• Heuristic
numbers are O(log n) bits long
4
Naïve Algorithm
1. A sends all of his numbers to B
2. 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
5
Communication Complexity
Naive algorithm
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
6
Communication Complexity
Naive algorithm
14, 29,53,28,284,348
14, 29,53,28,284,348 39, 67,98,22,35,253
B calculate the
median
B
A
Communication Complexity
7
Better algorithm
1. A sorts his array and sends his median ( M A )
to B
2. B sorts his array and sends his median ( M B )
to A.
3. Exercise :
define : r = real median
b = MAX{ MA , MB }
s = MIN { M , M }
A
B
prove : s  r  b
8
Communication Complexity
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
9
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
10
M A = M B then return M A ( = M B )
5. If M A > M B then A throws top (n/2) elements
4. If
B throws low (n/2) elements
6. And vice versa
• We reduces the size of the problem by half
7. Back to step 1, until size of arrays = 1
11
Communication Complexity
53<67
Better algorithm
Then A throws
the small half of
his array
67>53
Then B throws
the big half of
his array
,53,284,348,500
22, 35,39,67
B
A
Communication Complexity
12
Communication Complexity
Better algorithm
Since equal amount of members
were thrown from two sides of
the median
,53,284,348,500
22, 35,39,67
So, new median not changed.
B
A
Communication Complexity
13
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 O (Log^2(n)) bits
B
A
Communication Complexity
14
Calculation of cost
• Each number is O(log n) bits
• Each step 2 numbers are sent
• log(n) steps
• Total cost is O (Log^2(n)) bits
15
another improvement
- A calculates his median
- B calculates his median
13 18 20 25 32
17 22
27 31 45
B
A
Communication Complexity
16
Two assumptions
1) The requested median is between the A’s median and
B’s median.
13 18 20 25 32
A’s median
The requested median
between A’s and
B’s median
13 17 18 20 22
17 22 27 31 45
B’s median
25 27 31 32 45
17
* (we have an even amount of numbers, so we choose the the 6 th place of the 10 numbers)
Two assumptions
2) In binary representation we divide the medians to
common segment and different segment.
Note: Sometimes there is no common segment, but if
there is common for A’s and B’s medians then its
common to the request median.
Decimal
binary representation
27
-
11011
25
-
11001
20
-
10100
Common Different
segment
segment
18
Communication Complexity
After those assumptions we continue….
Every side send each bit of his median (start from MSB bit)
20 = 10100 b
27 = 1 1 0 1 1 b
1b
13 18 20 25 32
1b
17 22
27 31 45
B
A
Communication Complexity
19
Communication Complexity
Every side compares the bit he gets with the bit of his median.
If equal, those bits are in the “common segment” (see slide 17) and
this common to the request median then every side continue send
the next bit of his median.
20 = 10100 b
27 = 1 1 0 1 1 b
1b
1b
B
A
Communication Complexity
20
Communication Complexity
If not equal then A sees that his median is bigger, so he throws
the bigger half of his array,
B sees that his median is smaller then A’s median, so he throws
the smaller half of his array
20 = 10100 b
27 = 1 1 0 1 1 b
1b
0b
B
A
Communication Complexity
21
Communication Complexity
•After throwing half of his array, every side calculates his new
median.
•Every side send bits of the new median, starting from the bit
that there was different in the previous iteration ( and not from
the MSB bit).
•Every side continues the algorithm.
20 25 32
17 22 27
B
A
Communication Complexity
22
Communication Complexity
•The algorithm stops when one of two events occur.
1) the arrays of A and B contain one element (each).
2) all bits of the medians were sent.
20 25 32
17 22 27
B
A
Communication Complexity
23
Communication Complexity
•If arrays contain one element so this element is the median.
•If all bits were sent so the medians are equal and this is the
request median.
20 25 32
17 22 27
B
A
Communication Complexity
24
Complexity of algorithm
Every iteration one of this events occur
Bit is send to the other sides.
(log n bits can be sent from every side)
The array become shorter by half.
(the array can reduce by half , log n times)
So, sum of bits can be sent limited by O(log
n).
25
Communication complexity
The previous subject talked about problem of finding
median of array that was divided to two parts.
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
26
Communication complexity
Naïve algorithm
A send X to B.
B compares X to Y and return yes/no
X is logX bits long so cost is logX
B
A
Communication Complexity
27
Communication complexity
New random algorithm - GLOBAL CC
In this algorithm we have a random number R, that can
be changed and known for both sides.
?
X=Y
B
A
Communication Complexity
28
Communication complexity
GLOBAL CC
Lets define inner product of A and B:
A[0…..n-1], B[0…..n-1]
n 1
A * B   Ai * Bi
i 0
B
A
Communication Complexity
29
Communication complexity
GLOBAL CC
A: calculates
B: calculates
(X*R)mod 2
(Y*R)mod 2
B
A
Communication Complexity
30
Communication complexity
GLOBAL CC
bX=(X*R)mod 2
If X=Y then always bX= bY
If x ≠ Y then Prob(bX= bY)=1/2
bY=(Y*R)mod 2
B
A
Communication Complexity
31
Communication complexity
GLOBAL CC
Every side sends his result (b) and compares the results.
If the results are not equal so the numbers are not equal.
bX=(X*R)mod 2
bY
bY=(Y*R)mod 2
bX
B
A
Communication Complexity
32
Communication complexity
GLOBAL CC
bY=(Y*Rnew)mod 2
bX=(X*Rnew)mod 2
We choose a new R and
repeat the algorithm.
We do so C times.
B
A
Communication Complexity
33
Communication complexity
GLOBAL CC
If X=Y then all C times bX = bY.
If X≠Y the probability that all C times bX = bY is 2-c.
B
A
Communication Complexity
34
Communication complexity
Complexity of global CC
Each time every side transfers bX/Y by length of 1 bit.
There are C times so every side transfers C bits.
Complexity = O ( C )
B
A
Communication Complexity
35
Communication complexity
Another random algorithm
In this algorithm every side constructs a polynom from
his number according to these steps:
Every number consist of n bits.
X[an-1, an-2,…..,a1,a0]
Y[an-1, an-2,…..,a1,a0]
B
A
Communication Complexity
36
Communication complexity
Step 1:
Polynom of side A will be:
PolyA(T)= an-1*Tn-1+ an-2*Tn-2+…..+ a0*T0
X[an-1, an-2,…..,a1,a0]
Y[bn-1, bn-2,…..,b1,b0]
B
A
Communication Complexity
37
Communication complexity
Step 1:
Like side A polynom B will be:
Polyb(T)= bn-1*Tn-1+ bn-2*Tn-2+…..+ b0*T0
X[an-1, an-2,…..,a1,a0]
Y[bn-1, bn-2,…..,b1,b0]
B
A
Communication Complexity
38
Communication complexity
Step 2:
A chooses random prime p : n2 <p < n3
A sends p to B
X[an-1, an-2,…..,a1,a0]
Y[bn-1, bn-2,…..,b1,b0]
B
A
Communication Complexity
39
Communication complexity
Step 3:
B chooses
1≤R ≤ p-1 and calculates (polyb(R) mod p)
Remind: Polyb(R)= bn-1*Rn-1+ bn-2*Rn-2+…..+ b0*R0
B sends (R, (polyb(R) mod p) ) to A.
B
A
Communication Complexity
40
Communication complexity
Step 4:
A calculates polya(R) mod p
A compares (polya(R) mod p) with (polyb(R) mod p)
B
A
Communication Complexity
41
Communication complexity
Analysis of algorithm
If polya(R)  polyb(R)
Then X  Y
B
A
Communication Complexity
42
Communication complexity
Analysis of algorithm
But if polya(R) = polyb(R) there is some probability that X  Y.
We will calculate F:
F=prob(X  Y and polya(R) = polyb(R))
B
A
Communication Complexity
43
Communication complexity
Analysis of algorithm
polya(R) = polyb)R)
polya(R) - polyb)R)=0
F=prob[X  Y and polya(R) = polyb)R(]= prob[X  Y and polya(R)-polyb)R(=0].
polya(R)-polyb)R(=0 is a polynom of degree n
it has n-1 roots.
B
A
Communication Complexity
44
Communication complexity
Analysis of algorithm
Because there are n-1 R’s s.t. polya(R)-polyb)R(=0.
And 1<=R<=p-1.
So the probability to choose one of those R’s is: (n-1)/p.
B
A
Communication Complexity
45
Communication complexity
Analysis of algorithm
We saw that n2 <p < n3
So: n-1/p>(n-1)/ n21/n
F=prob(X  Y and polya(R) = polyb(R))<1/n
The probability of mistake is:1/n
B
A
Communication Complexity
46
Communication complexity
Analysis of algorithm
Communication complexity:
The sides transferred p and R only:
n2 <p < n3
|p|=O(log n) And R<p
So the total complexity is : O(log n)
B
A
Communication Complexity
47
Communication complexity
CC and Global CC
What is the complexity relation between CC and GCC
Note: CC is the last alogorithm we had seen.
B
A
Communication Complexity
48
Communication complexity
solution
A and B have a deterministic Turing machine which
generates (deterministically) K random r’s.
2
(while K= )
n
B
A
Communication Complexity
49
Communication complexity
solution
Define R to be the chain of K’s random r’s
R  ri *n
2
r1
r2
ri
rn

2
R
B
A
Communication Complexity
50
Communication complexity
Now, instead of A sending r to B, A only has to send
ri ' s index in R.
2
The index can be sent with O(log( n ) bits
=O(log n)
B
A
Communication Complexity
51
Communication complexity
Claim:
For each subset of R there is ri in the subset that is never
wrong for each (x,y).
B
A
Communication Complexity
52
Communication complexity
Proof:
subset 
k
2
L  {x, y | x  y}
prob (( x, y )  {0,1}n * {0,1}n  L |
R
subset  R | ri  subset | A, B  r ( x, y )  1
i

22 n
 prob(subset  R ir  subset | A, B  ( x, y )  1)
r
i 1
( x , y )L
A
22 n
 k 


k 
 2
i 1
t 1
B
   prob(r  subset | A, B  r ( x, y )  1)
Communication
Complexity
 k 


53
subset  R | ri  subset | A, B  r ( x, y )  1
i

Communication
complexity
 prob(subset  R ir  subset | A, B  ( x, y )  1)
22 n
r
i 1
( x , y )L
Proof:
22 n
 k 


k 
 2
i 1
t 1
   prob(r  subset | A, B  r ( x, y )  1)
 k 


k 
 2
k
   prob( A, B  r ( x, y )  1)
i 1 t 1 2
22 n
 k 


k 
 2
 k 


k 
 2
2k
2k
k 1
1
1
1
   *         2 2 n *    1
i 1 t 1 2
k i 1 t 1 2 i 1  2 
 2

22 n
22 n
22 n

B
A
Communication Complexity
54
Communication complexity
So:
prob(r that is never wrong)
 1 - prob(r there is no r that is wrong)
 1-  0
B
A
Communication Complexity
55
Communication complexity
Conclusion:
CC  (O(log n)  GCC
)



 running
sending
index
GCC
B
A
Communication Complexity
56