Communication and Information Complexity

This document discusses topics related to communication and information complexity. It includes a proof of the fooling set lower bound, the relationship between prime numbers and natural numbers, rank comparison, lower bound for disjointness, and deterministic and randomized protocols.

1
COMMUNICATION AND INFORMATION COMPLEXITY-HOMEWORK I
Student’s Name:
University Affiliation:
Course:

2
Question 1.
The communication protocol is such that the output function wholly depends
on the leaf protocol reached i.e. the players’ production output correspond to
the transcript as well as the input.
Level of production is a factor of two individuals i.e. Alice (outv A(x) and Bob
(out vB(y) on arriving at the leaf v.
You are asked to prove that the fooling set lower bound still holds i.e.
D’(f)≥log(t), Given that D’(f) is the shortest potential that weakly solves f.
Proof;
It is true that for every (x, y)£Protocol ∏ will get fixed to a rectangle of a
different kind within the matrix of the function. Therefore, we can conclude
that is fixed to a different leaf.
Similarly, we understand that there is a binary tree of depth d whose leaf is
of at most two dimensions. Hence, you are to conclude a trivial lower bound
of the depth of the tree, which is [log(Protocol ∏).
But at least a rectangle is required for the other output. Thus, a tight bound
is necessary i.e.
D’(f)=[log(t+1)]
Contrasting and comparing an equality problem;
{(x,x)|x£(0,1)n} ͢ D’(Equality)≥{log(2t+1)}=t+1
In addition;
[(x,ẋ)|x £ (0,1)n is a disjoint problem that can be included as a fooling set i.e
Alice combination equals Bob’s combination (A С B)

3
When Alice combination intersect Bob’s combination, it is impossible to get
the parameter ∏
There is a probability of getting parameter ∏ when the two combination
intersect.
The linear production problem;
Given advanced tools, you can implement the technical techniques to prove
a tight bound. However, it is impossible to prove a tight bound on the inner
product problem.
Question 2:
Prime numbers are numbers which can be divided only by one and itself.
Natural numbers are counting positive whole numbers with zero included.
By Euclid’s proof, a finite list of prime numbers is incomplete.
Therefore, he recommended the multiplication of prime numbers in a list
with addition of one to get a natural number.
For instance,
Suppose p1,p2,……………..pn is a list of prime numbers, then,
N=1+p1 + p2,……………….pn
On prime factorization;
N=p11.p21………pn.
You will realize that N has a remainder of 1 when divided by any prime
number in the list i.e. there is an infinite number of prime numbers.
Hence, you can conclude that prime numbers are elements of natural
numbers.

4
Rank Fp(M)≤RankR(M)
(┌Qual ,┌Forb) are the structures of n participants. Assume that there is a
collection s of nxk Boolean matrices of R and F.
There exist a value α(m). If there is a set {X<tx}x £ ┌Qual satisfying;
You can contrast the condition:
X={i1,i2,i3,,,,,in] £ ┌Qual
And the row vector satisfies;
(i) w(V0)≤tX−α(m)⋅m,
and
(ii) w(V1)≥tX.
recorded.
tX = min(w(V1)) is the threshold
Security condition: A (forbidden) subset X = {i1, i2, …, iv} ∈ ΓForb is
where all participants are locked from the ideal information.
b)
Let f and 1-f ╥ be a protocol for f with leaves u1,u2.u3,……un and V0
be the set of all leaves with output 0.
V1 is the set of leaves with output 1.
Hence,
v £ V1
But fRv(x,y)={10 otherwise if (x,y) ≥Rv is the pdf.

5
Also note that;
(1-f)Rv(x,y)=0
Hence v £ V0
This implies,
FRv(x.y)=0
But if (1-f)Rv(x,y)={0 otherwise1 if (x,y) £ Rv is the pdf,
Then,
F=∑v £ V1fRv,1-f=∑v£V0(1-f)Rv
This means that {rank (1-f) ≤|v0|rank(f)≤|v1|
Remember that the rank (1-f)≥rank(f)-1
Similarly,
Rank (f)+Rank(1-f)≤|V0ŬV1|=# leaves ≤ 2|╥|
Thus |╥|≥log (rank(f)-1
c)
IP(x,y)=(x,y)mod 2
You are to consider a function IP’ to help prove the lower bound of IP.
Thus IP’(x,y)=(-1)(x,y)mod 2
We can confirm by induction that;
IP’n+1 =IP1’ * IPn’
And ;

6
Rank(IP’n+1)=rank(IP’n)*2
But
Rank (IP’n)=2n
Rank(IPn)≥2n-1
Which gives;
D(IPn)≥[log(2n-1)]=n.
Question 4.
Disj(x,y)={10 ,xny≠ ɸ ,xny=ɸ
You understand that there exist a ῼ(n) lower bound for communication
complexity of disjointness.
YAou are expected to reduce exact distinct elements problems to
disjointness problem.
For instance,
You are given a set of X and Y.
You are to run the streaming algorithm in such a way that, the elements of X
follow those of Y.
You will finally establish a stream whose distinct elements is |XŬY|
You are to investigate the stream.
When XņY=ɸ then |XŬY|=|X|+|Y|
Similarly, when XņY≠ɸ then |XŬY|<|X|+|Y|

7
When |XŬY|=|X| +|Y|, your output is 1, otherwise, your output is 0.
Question 5:
a)
Consider a fact that when the streaming algorithm is deterministic, the
protocol is deterministic as well.
Similarly, if randomized, the protocol must be randomized to maintain the
state.
However, the protocol has got a communication complexity of s+logn +1
when the streaming algorithm requires s bits of space.
When there is a lower bound of ῼ(n) for disjoint problem, s=ῼ(n) is a
deterministic distinct element.
Hence, one-sided protocol reduction and a single output of distinct elements
i.e x £ {0,1} or j £ (n) gives;
Index(x,j)=(x(j)
Thus,
D(Index)=ῼ(logn)
b)
Consider Alice input as x £ {0,1}
But,
Only Bob is expected to receive and output the answer.

8
You will notice that the problem encounters a trivial bound of n bits.
In addition, a simple two-sided protocol with log n communication complexity
exist.
Thus,
D͢ (INDEX)=ῼ(n)