Information Technology Reference
In-Depth Information
complementary value for all
v
V
), let
f
=
x
i
inthefirstcaseand
f
=
x
i
in the second.
Thus, in the first case (the second case is treated similarly)
U
∈
⊆
f
−
1
(
0
)
,
V
⊆
f
−
1
(
1
)
and
D
Ω
0
(
f
)=
0. This establishes the base case.
For the induction step, without loss of generality, let Player I send the first bit. (The
other case is treated similarly.) For some partition of
U
=
U
0
∪
U
1
,
U
0
∩
U
1
=
∅
,PlayerI
sends a 0 if
u
∈
U
0
and a 1 if
u
∈
U
1
, after which the players play with the best protocol
for each subcase. It follows that
C
(
U
,
V
)=
1
+max
j
=
1,2
(
C
(
U
j
,
V
))
Since
C
(
U
j
,
V
)
<C
(
U
,
V
)
for
j
=
1, 2, by induction there exist Boolean functions
f
1
and
f
2
such that
U
j
⊆
f
−
1
j
f
−
1
j
(
0
)
and
V
⊆
(
1
)
and
D
Ω
0
(
f
j
)
≤
C
(
U
j
,
V
)
for
j
=
1, 2.
Since the output vertex is assumed to be
AND
,
f
=
f
1
∧
f
2
,
f
has value 1 only when both
f
1
and
f
2
have value 1 and has value 0 when either
f
1
or
f
2
have value 0. Thus, we have
f
−
1
(
1
)
f
−
2
(
1
)=
f
−
1
(
1
)
V
⊆
∩
f
−
1
(
0
)
f
−
2
(
0
)=
f
−
1
(
0
)
U
=
U
1
∪
U
2
⊆
∪
from which we conclude that
D
Ω
0
(
f
)
≤
1
+max(
D
Ω
0
(
f
1
)
,
D
Ω
0
(
f
2
))
≤
1
+max
j
=
1,2
(
C
(
U
j
,
V
)) =
C
(
U
,
V
)
which is the desired result.
This establishes the connection between the depth of a Boolean function
f
over the stan-
dard basis
Ω
0
and the communication complexity associated with the sets
f
−
1
(
0
)
and
f
−
1
(
1
)
.
We now draw some conclusions from Theorem
9.7.1
. From the observation made above
that
C
(
U
,
V
)
n
+log
2
n
for an arbitrary communication problem
(
U
,
V
)
when
U
,
V
≤
∈
n
,wehavethat
D
Ω
0
(
f
)
n
+log
2
n
for all
f
:
n
B
≤
B
→B
. Abetterupperboundof
D
Ω
0
(
f
)
≤
n
+
1 is given in Theorem
2.13.1
. The best upper bound of
n
−
log
2
log
2
n
+
O
(
1
)
has been derived by Gaskov [
110
], matching the lower bound of
n
−
Θ(log log
n
)
derived in
Theorem
2.12.2
.
The parity communication problem described above is defined in terms of the two sets
that are the inverse images of the parity function
f
(
n
)
n
:
B
→B
. As stated in Problem
9.28
,
⊕
this function has a formula size of at least
n
2
.Since
D
Ω
(
f
)
≥
log
2
L
Ω
0
(
f
)
(Theorem
9.2.2
),
it follows that
D
Ω
(
f
(
n
)
2
log
2
n
, which matches the upper bound on the communication
complexity of the parity communication problem. Thus the protocol given earlier for this
problem is optimal.
We now introduce the monotone communication game and develop a relationship be-
tween its complexity and the depth of monotone functions over a monotone basis.
)
≥
⊕
9.7.3 Monotone Depth and Communication Complexity
We specialize Theorem
9.7.1
to monotone functions by using the fact that if
f
:
n
is
monotone and there are two
n
-tuples
u
and
v
such that
f
(
u
)=
0and
f
(
v
)=
1, then there
exists an index
i
,1
B
→B
n
,suchthat
u
i
<v
i
,thatis,
u
i
=
0and
v
i
=
1.
The binary
n
-tuple
x
can be defined by the set
≤
i
≤
{
i
|
x
i
=
1
}
of indices on which variables
.Let2
[
n
]
be the power set of
[
n
]
,that
have value 1. This is a subset of
[
n
]=
{
1, 2,
...
,
n
}
Search WWH ::
Custom Search