Information Technology Reference
In-Depth Information
Furst, Saxe, and Sipser [
107
] and, independently, Ajtai [13] obtained the first strong lower
bounds on the size of bounded-depth circuits. They demonstrated that every bounded-depth
circuit for the parity function
f
(
n
)
⊕
has superpolynomial size. Using a deeper analysis, Yao
[
368
] demonstrated that bounded-depth circuits for
f
(
n
)
have exponential size. Hastad [
124
]
strengthened the results and simplified the argument, giving a lower bound on circuit size of
2
Ω(
n
1
/d
/
10
)
for circuits of depth
d
.
Razborov [
272
] examined a more powerful class of bounded-depth circuits, namely, cir-
cuits that use unbounded fan-in
AND
,
OR
, and parity functions. He demonstrated that the
majority function
τ
(
n
)
⊕
n/
2
has exponential size over this larger basis. Smolensky [
313
] simplified
and strengthened Razborov's result, obtaining an exponential lower bound on the size of a
bounded-depth circuit for the MOD
p
function over the basis
AND
,
OR
,andMOD
q
when
p
and
q
are distinct powers of primes. We use a simplified version of his result in Section
9.7.5
.
Search WWH ::
Custom Search