Information Technology Reference
In-Depth Information
Combining this and (
9.5
) (note that in step 6 we let
COL
t
=COL
∗
), we have the first
of the two desired conclusions, namely
μ
COL(
V
,
M
t
)
(COL
t
)
≥
2
m
t
−
2
t
. This implies that
m
t
≤
2
t
. Applying this to the inequality in Lemma
9.7.4
and using the condition
t
≤
n/
(
8
k
)
, we get the following inequality:
μ
CLQ(
V
,
P
t
,
M
t
−
1
)
(CLQ
t
)
/
2
μ
CLQ(
V
,
P
t
,
M
t
−
1
)
(CLQ
t
)
≥
Combining this with the lower bound given in (
9.6
), we have the second of the two desired
conclusions, namely,
μ
CLQ(
V
,
P
t
,
M
t
−
1
)
(CLQ
t
)
2
p
2
−
2
t
.
≥
We now state the principal conclusion of this section.
THEOREM
9.7.3
Let
2
≤ k ≤
(
n
/
2
)
2
/
3
. Then the monotone communication complexity of the
k
-clique function
f
(
n
)
clique
,
k
is
Ω(
√
k
)
.
Proof
Run the adversarial selection process for
T
=
√
k/
4 steps to produce sets
CLQ
T
,
COL
T
,
P
T
,and
M
T
. Below we show that
CLQ
T
and
COL
T
are not empty. Give the
clique player a
k
-clique
q
∈
and the color player a
(
k
−
1
)
-coloring
c
∈
COL
T
.To
show that the two players cannot agree in
T
orfewerroundsonanedgeinacliquein
CLQ
T
that is monochromatic in all
c
CLQ
T
q
be that edge.
If follows that both
u
and
v
are in
M
T
. But this cannot happen because, by construction,
q
∈
COL
T
, assume they can, and let
(
u
,
v
)
∈
∩
M
T
=
∅
.
To s h ow t h a t
CLQ
T
(
n/
2
)
2
/
3
and
t
and
COL
T
are not empty, observe that
k
≤
≤
√
k/
4 imply that
t
≤
n/
(
8
k
)
. Thus, Lemma
9.7.5
can be invoked, which implies that
≤
√
k/
2
p
t
,
m
t
≤
2
t
≤
k/
2
<n
. Invoking the definitions, the following inequalities also
hold.
2
p
t
−
2
t
CLQ(
V
,
P
t
,
M
t−
1
)
>
0
CLQ
t
≥
2
m
t
−
2
t
COL(
V
,
M
t
)
>
0
COL
t
≥
Since the right-hand sides are non-zero, we have the desired conclusion.
9.7.5 Bounded-Depth Circuits
As explained earlier, bounded-depth circuits are studied to help us understand the depth of
bounded fan-in circuits. Bounded-depth circuits for arbitrary Boolean functions require that
the fan-in of some gates be unbounded because otherwise only a bounded number of inputs
can influence the output(s).
In Section
2.3
we encountered the DNF, CNF, SOPE, POSE, and RSE normal forms.
Each of these corresponds to a circuit of bounded depth. The DNF and SOPE normal forms
represent Boolean functions as the
OR
of the
AND
of literals. The
OR
and each of the
AND
s
is a function of a potentially unbounded number of literals. The same statement applies to
the CNF and POSE normal forms when
AND
and
OR
are exchanged. The RSE normal form
represents Boolean functions as the
EXCLUSIVE OR
of the
AND
of variables, that is, without
the use of negation. Again, the fan-in of the two types of operation is potentially unbounded.
As stated in Problems
2.8
and
2.9
, the SOPE and POSE of the parity function
f
(
n
)
⊕
have
exponential size, as does the RSE of the
OR
function
f
(
n
)
. In Problem
2.10
it is stated that
∨
the function
f
(
n
)
mod
3
has exponential size in the DNF, CNF, and RSE normal forms.
Search WWH ::
Custom Search