Information Technology Reference
In-Depth Information
the standard communication game than are exchanged with the monotone communication
game when the sets
U
and
V
are the inverse images of a monotone Boolean function.
In the next section we use the above result to derive a large lower bound on the monotone
depth of the clique function.
9.7.4 The Monotone Depth of the Clique Function
In this section we illustrat
e
the use of the monotone communication game by showing that
in this game at least
Ω(
√
k
)
bits must be exchanged between two players to compute the
clique function
f
(
n
)
clique
,
k
n
(
n−
1
)
/
2
(
n/
2
)
2
/
3
.The
:
B
→B
defined in Section
9.6
when
k
≤
inputs to
f
(
n
)
clique
,
k
are variables associated with the edges of a graph on
n
vertices. If an edge
variable
e
i
,
j
=
1, the edge between vert
ic
es
i
and
j
is present. Otherwise, it is absent. By
Theorem
9.7.2
, a lower bound of
Ω(
√
k
)
on the number of bits that must be
e
xchanged
between the two players to compute
f
(
n
)
clique
,
k
clique
,
k
has depth
Ω(
√
k
)
.
implies that
f
(
n
)
THE RULES OF THE GAME
Fix
n
and
k
. The players in this communication game are each
given sets of edges of graphs on
n
vertices. Player I is given a set of edges that contains a
k
-
clique (an input on which
f
(
n
)
clique
,
k
has value 1, a
positive instance
) whereas Player II is given
a set of edges that does not contain a
k
-clique (an input on which it has value 0, a
negative
instance
). The goal of the game is to exchange the minimum number of bits for the worst-case
instances to permit the players to identify an edge variable that is 1 on a positive instance and
0 on a negative one. This number of bits is the communication complexity of the game.
To derive the lower bound on communication complexity, we restrict the graphs under
consideration by choosing them so that every protocol must exchange a lot of data (this cannot
make the worst cases any worse). In particular, we give Player I only
k
-cliques, the set of
graphs, CLQ, whose only edges are those between an arbitrary set of
k
vertices. We call Player
Ithe
clique player
.Also,wegivePlayerIIa
(
k
−
1
)
-coloring drawn from the set COL of all
possible assignments of
k
−
1 colors to the
n
vertices of a graph
G
. The interpretation of a
(
k
1
)
-coloring is that two vertices can have the same color only if there is no edge between
them. Thus, any graph that has a
(
k
−
1
)
-coloring cannot contain a
k
-clique because the
k
vertices in such a subgraph must have different colors. We call Player II the
color player
.The
goal now becomes for the two players to find a monochromatic edge (both endpoints have the
same color) owned by the clique player.
In the standard communication game players alternate exchanging binary messages. We
simplify our discussion by assuming that each player transmits one bit simultaneously on each
round. We then find a lower bound on the number of rounds and use this as a lower bound
on the number of bits exchanged between the two players.
−
AN ADVERSARIAL STRATEGY
We describe an adversarial strategy for the selection of cliques and
colorings that insures that many rounds are needed for the two players to arrive at a decision.
To present the strategy, we need some notation.
Let CLQ
0
denote the set of graphs
G
=(
V
,
E
)
on
n
vertices that contain only those edges
in a
k
-clique. It follows that CLQ
0
contains
k
graphs. Let COL
0
denote the set of
(
k
−
1
)
-
colorings of graphs on
n
vertices, that is, COL
0
=
{
c
|
c
:
V
→
[
k
−
1
]
}
,where
[
k
−
1
]
1
)
n
(
k
denotes the set
{
1, 2,
...
,
k
−
1
}
. It follows that COL
0
contains
(
k
−
−
1
)
-colorings.
Search WWH ::
Custom Search