Information Technology Reference
In-Depth Information
to extend the standard communication complexity measure to the following VLSI communi-
cation complexity measure for functions
f
:
X
n
→B
.
DEFINITION
12.7.2
The
VLSI communication complexity
of a predicate
f
:
X
n
→B
,
CC
vlsi
(
f
)
, is the minimum of the communication complexity
C
(
U
,
V
)
over all partitions
(
U
,
V
)
of the variables of
f
into two sets of size at most
2
n/
3
.
The following theorem, which is left as an exercise (see Problem
12.17
), summarizes the
result of applying the VLSI communication complexity measure
CC
vlsi
(
f
)
together with the
planar separator theorem to derive a lower bound on the semellective planar circuit size of
predicates.
THEOREM
12.7.4
Let
f
:
X
n
have VLSI communication complexity
CC
vlsi
(
f
)
.Then,
the following bounds hold for the computation of
f
by a semellective VLSI chip with area
A
in
T
steps.
→B
(
CC
vlsi
(
f
))
2
=
O
(
AT
2
)
,
O
(
A
2
T
)
Note that in a planar circuit all the information passed from each side of the separator
to the other is sent simultaneously, whereas in the communication game players alternate in
sending values drawn from the set
X
. Because more freedom is granted to players in the com-
munication game (each player can choose data to send based on responses previously received
from the other player), a lower bound on communication complexity is a lower bound on the
amount of information that must be exchange in a planar circuit.
A number of techniques have been developed to derive lower bounds on the planar circuit
size of predicates. One of these uses the pigeonhole principle (also known as a
crossing-
sequence argument
) to derive lower bounds for predicates that are
w
(
u
,
v
)
-separated. This
new property is similar to the
w
(
u
,
v
)
-flow property of multi-output functions. It is defined
below.
DEFINITION
12.7.3
Afunction
f
:
X
n
is
w
(
u
,
v
)
-separated if its variables can be per-
muted and partitioned into three sets
U
,
V
,and
Z
,
→B
|
U
|≥
u
and
|
V
|≥
v
, such that there is some
value
z
for variables in
Z
and values
u
i
and
v
i
,
1
≤
i
≤|
X
|
w
(
u
,
v
)
,forvariablesin
U
and
V
,
respectively, such that the following holds:
f
(
u
i
,
v
j
,
z
)=
1
if
i
=
j
0
otherwise
This definition can be applied to predicates that are associated with multi-output functions.
These functions are defined below.
DEFINITION
12.7.4
The characteristic predicate
p
f
:
X
(
n
+
m
)
of
f
:
X
(
n
)
X
(
m
)
→B
→
is
defined below.
p
f
(
x
,
y
)=
1
if
y
=
f
(
x
)
0
otherwise
It is straightforward to show that the characteristic predicate of a function that has a
w
(
u
,
v
)
-flow is
w
(
u
,
v
)
-separated. (See Problem
12.18
.) As a consequence, quadratic lower
Search WWH ::
Custom Search