Information Technology Reference
In-Depth Information
CIRCUIT DEPTH
9.39 Show that the communication complexity of a problem
(
U
,
V
)
,
U
,
V
⊆
B
n
, satisfies
n
+log
2
n
,where
log
2
n
is the number of times that
C
(
U
,
V
)
≤
log
2
must be taken
to reduce
n
to zero.
Hint:
Complete the definition of a protocol in which Player I sends Player II
n
−
bits on the first round and Player II responds with a message specifying
whether or not its
n
-tuple agrees with that of Player I and if not, where they differ.
9.40 Consider the communication problem defined by the following sets:
log
2
n
U
=
{
u
|
3 divides the number of 1s in
u
}
V
=
{
v
|
3 does not divide the number of 1s in
u
}
Show that a protocol exists that solves this problem with communication complexity
3
log
2
n
.
9.41 Show that Theorem
9.7.4
continues to hold when the MOD
3
function is added to the
basis where MOD
3
is the Boolean function that has value 1 when the number of 1s
among its inputs is not divisible by 3.
Chapter Notes
The dependence of circuit size on fan-out stated in Theorem
9.2.1
is due to Johnson et al.
[
150
]. The depth bound implied by this result is proportional to the product of the depth and
the logarithm of the size of the original circuit. Hoover et al. [
138
] have improved the depth
bound so that it is proportional to
(log
r
s
)
D
Ω
(
f
)
without sacrificing the size bound of [
150
].
The relationship between formula size and depth in Theorem
9.2.2
is due to Spira [
314
],
whose depth bound has a coefficient of proportionality of 2
.
465 over the basis of all Boolean
functions on two variables. Over the basis of all Boolean functions except for parity and its
complement, Preparata and Muller [
259
] obtain a coefficient of 1.81. Brent, in a paper on the
parallelization of arithmetic formulas [
58
], has effectively extended the relationship between
depth and formula size to monotone functions. (See also [
359
].)
An interesting relationship between complexity measures that is omitted from Section
9.2
,
due to Paterson and Valiant [
240
], shows that circuit size and depth satisfy the inequality
1
4
C
Ω
(
f
)log
C
Ω
(
f
)
D
Ω
(
f
)
≥
−
O
(
C
Ω
(
f
))
The lower bounds of Theorem
9.3.2
on functions in
Q
(
n
)
2,3
are due to Schnorr [
300
],
whereas that of Theorem
9.3.3
on the multiplexer function is due to Paul [
244
]. Blum [
48
],
building on the work of Schnorr [
302
], has obtained a lower bound of 3
(
n
1
)
for a particular
function of
n
variables over the basis
B
2
. This is the best circuit-size lower bound for this
basis. Zwick [
374
] has obtained a lower bound of 4
n
for certain symmetric functions over the
basis
U
2
.Red'kin[
274
] has obtained lower bounds with coefficients as high as 7 for certain
functions over the bases
−
. (See Problem
9.23
.) Red'kin [
276
]hasusedthe
gate-elimination method to show that the size of the ripple-adder circuit of Section
2.7
cannot
be improved.
{∧
,
¬}
and
{∨
,
¬}
Search WWH ::
Custom Search