Information Technology Reference
In-Depth Information
In this section we first show that the depth of a function
f
is equal to the
communication
complexity
of a related problem in a two-player game. Communication complexity is a measure
of the amount of information that must be exchanged between two players to perform a com-
putation. We establish such a connection for all Boolean functions over the standard basis
Ω
0
and monotone functions over the monotone basis
Ω
mon
. These connections are used to derive
lower bounds on circuit depth for monotone and non-monotone functions. After establishing
these results we examine bounded-depth circuits and demonstrate that some problems require
exponential size when realized by such circuits.
9.7.1 Communication Complexity
We define a
communication game
between two players who have unlimited computing power
and communicate via an error-free channel. This game has sufficient generality to derive
interesting lower bounds on circuit depth.
DEFINITION
9.7.1
A
communication game
(
U
,
V
)
is defined by sets
U
,
V ⊆ B
n
,where
U ∩
V
=
V.
u
is assigned to Player I and
v
is assigned to Player II. Players alternate sending binary messages to each other. We assume that
the binary messages form a prefix code (no message is a prefix for another) so that one player can
determine when the other has finished transmitting a message.
Although each player has unlimited computing power, each message it sends is a function of just
its own
n
-tuple and the messages it has received previously from the other player. The two functions
used by the players to determine the contents of their messages constitute the
protocol
Π
under
which the communication game is played. The protocol also determines the first player to send a
message and termination of the game. The
goal
ofthegameistofindanindex
i
,
1
∅
. An instance of the game is defined by
u
∈
U
and
v
∈
≤
i
≤
n
,such
that
u
i
=
v
i
.
Let
Π(
u
,
v
)
denote the number of bits exchanged under
Π
on the instance
(
u
,
v
)
of the game
(
U
,
V
)
.The
communication complexity
C
(
U
,
V
)
of the communication game
(
U
,
V
)
is the
minimum over all protocols
Π
of the maximum number of bits exchanged under
Π
on any instance
of
(
U
,
V
)
;thatis,
C
(
U
,
V
)=mi
Π
max
u
∈U
,
v
∈V
Π(
u
,
v
)
Note that there is always a position
i
,1
≤
i
≤
n
,suchthat
u
i
=
v
i
since
U
∩
V
=
∅
.
The communication game models a search problem; given disjoint sets of
n
-tuples,
U
and
V
, the two players search for an input variable on which the two
n
-tuples differ. A related
communication game measures the exchange of information to obtain the value of a function
f
:
X
Z
on two variables in which one player has a value in
X
and the other has
a value in
Y
. The players must acquire enough information about each other's variable to
compute the function.
Every communication problem
(
U
,
V
)
,where
U
,
V
×
Y
→
B
n
, can be solved with communi-
⊆
cation complexity
C
(
U
,
V
)
≤
n
+
log
2
n
by the following protocol:
•
Player I sends
u
to Player II.
•
Player II determines a position in which
u
=
v
and sends it to Player I using
log
2
n
bits.
Search WWH ::
Custom Search