Information Technology Reference
In-Depth Information
n
+log
2
n
,where
log
2
n
is the number of
This bound can be improved to
C
(
U
,
V
)
≤
must be taken to reduce
n
to zero. (See Problem
9.39
.) The
log-star
function
log
2
n
grows very slowly. For example,
log
2
10
10
10
log
2
times that
is 8; by contrast,
log
2
10
10
10
=
33,219,280,949.
These concepts are illustrated by the
parity communication problem
(
U
,
V
)
,defined
below, where
n
=
2
k
:
U
=
{
u
|
u
has an even number of 1s
}
V
=
{
v
|
v
has an odd number of 1s
}
The following protocol achieves a communication complexity bound of
C
(
U
,
V
)
≤
2
log
2
n
for this problem. Later we show it is best possible.
1. If
n
=
1, the players know where their tuples differ and no communication is necessary.
2. If
n>
1, go to the next step.
3. Player I sends the parity of the first
n/
2bitsof
u
to Player II.
4. Since
u
=
v
, with one bit Player II tells Player I of half of the variables on which
u
and
v
are known to differ. Play is resumed at the first step with the half of the variables on which
they are known to differ.
Let
κ
(
n
)
denote the number of bits exchanged with this protocol. Then
κ
(
1
)=
0and
κ
(
n
)
≤
κ
(
n/
2
)+
2, whose solution is
κ
(
n
)=
2
log
2
n
.Thus,
C
(
U
,
V
)=
κ
(
n
)
≤
2
log
2
n
.
9.7.2 General Depth and Communication Complexity
We now establish a relationship between the depth
D
Ω
0
(
f
)
of a Boolean function
f
:
n
→B
over the standard basis
Ω
0
and the communication complexity of a communication game in
which
U
=
f
−
1
(
0
)
and
V
=
f
−
1
(
1
)
,where
f
−
1
(
a
)
is the set of
n
-tuples for which
f
has
value
a
.Theorem
9.7.1
asserts that
D
Ω
0
(
f
)
and
C
(
f
−
1
(
0
)
,
f
−
1
(
1
))
have exactly the same
value. Later we establish a similar result for monotone functions realized over the monotone
basis. We divide this result into two lemmas that are proved separately.
B
THEOREM
9.7.1
For every Boolean function
f
:
B
n
→B
,
D
Ω
0
(
f
)=
C
(
f
−
1
(
0
)
,
f
−
1
(
1
))
The communication game allows the two players to have unlimited computing power at
their disposal. Thus, the protocol they employ can be an arbitrarily complex function. This
power reflects the non-uniformity in the circuit model.
LEMMA
9.7.1
For all Boolean functions
f
:
B
n
n
→B
and all
U
,
V
⊆B
such that
U
⊆
f
−
1
(
0
)
and
V
f
−
1
(
1
)
, the following bound holds:
⊆
D
Ω
0
(
f
)
Proof
In this lemma we demonstrate that a protocol for the communication game
(
f
−
1
(
0
)
,
f
−
1
(
1
))
can be constructed from a circuit of minimal depth for the Boolean function
f
.We
C
(
U
,
V
)
≤
Search WWH ::
Custom Search