Information Technology Reference
In-Depth Information
The coefficient of Neciporuk's lower-bound method [
230
]inTheorem
9.4.1
has been im-
proved upon by Paterson (unpublished) and Zwick [
373
]. Paul [244] has applied Neciporuk's
method to show that the indirect storage access function has formula size
Ω(
n
2
/
log
n
)
over
the basis
B
2
.Neciporuk's method has also been applied to many other problems, including the
determinant [
169
], the marriage problem [
126
], recognition of context-free languages [
241
],
and the clique function [304].
The proof of Krapchenko's lower bound [
174
] given in Theorem
9.4.2
is due to Pater-
son, as described by Bopanna and Sipser [
50
]. Koutsoupias [
172
] has obtained the results of
Problems
9.30
and
9.31
, improving upon the Krapchenko lower bounds for the
k
th thresh-
old function by a factor of at least 2. Andreev [
24
], building on the work of Subbotovskaya
[
320
], has improved upon Krapchenko's method and exhibits a lower bound of
Ω(
n
2
.
5
−
)
on
afunctionof
n
variables for every fixed
>
0when
n
is sufficiently large. Krichevskii [
176
]
has shown that over the standard basis,
τ
(
n
t
requires formula size
Ω(
n
log
n
)
,whichbeats
Krapchenko's lower bound for small and large values of
t
.
Symmetric functions are examined in Section
2.11
and upper bounds are given on the
circuit size of such functions over the basis
. Polynomial-size formulas for symmet-
ric functions are implicit in the work of Ofman [
234
] and Wallace [
356
], who also indepen-
dently demonstrated how to add two binary numbers in logarithmic depth. Krapchenko [
175
]
demonstrated that all symmetric Boolean functions have formula size
O
(
n
4
.
93
)
over the stan-
dard basis. Peterson [
247
], improving upon the results of Pippenger [
248
]andPaterson[
241
],
showed that all symmetric functions have formula size
O
(
n
3
.
27
)
over the basis
B
2
.Paterson,
Pippenger, and Zwick [
242
,
243
] have recently improved these results, showing that over
B
2
and
U
2
formulas exist of size
O
(
n
3
.
13
)
and
O
(
n
4
.
57
)
, respectively, for many symmetric Boolean
functions including the majority function, and of size
O
(
n
3
.
30
)
and
O
(
n
4
.
85
)
, respectively, for
all symmetric Boolean functions.
Markov demonstrated that the minimal number of negations needed to realize an arbitrary
binary function on
n
variables with an arbitrary number of output variables, maximized over
all such functions, is at most
{∧
,
∨
,
⊕}
log
2
(
n
+
1
)
. For Boolean functions (they have one output
log
2
(
n
+
1
)
variable) it is at most
.Fischer[
100
] has described a circuit whose size is at most
t
w
ice tha
t
of an optimal circuit plus the size of a circuit that computes
f
NEG
(
x
1
,
...
,
x
n
)=
(
x
1
,
...
,
x
n
)
and whose depth is at most that of the optimal circuit plus the depth of a circuit
for
f
NEG
. He exhibits a circuit for
f
NEG
of size
O
(
n
2
log
n
)
and depth
O
(log
n
)
.Thisis
the result given in Theorem
9.5.1
. Tanaka and Nishino [
323
] have improved the size bound
on
f
NEG
to
O
(
n
log
2
n
)
at the expense of increasing the depth bound to
O
(log
2
n
)
.Beals,
Nishino, and Tanaka [
32
] have further improved these results, deriving simultaneous size and
depth bounds of
O
(
n
log
n
)
and
O
(log
n
)
, respectively.
Using non-constructive methods, a series of upper bounds have been developed on the
monotone formula size of the threshold functions
τ
(
n
t
by Valiant [
346
] and Bopanna [
49
],
culminating in bounds by Khasin [
166
]andFriedman[
106
]of
O
(
t
4
.
3
n
log
n
)
over the mono-
tone basis. With constructive methods, Ajtai, Komlos, and Szemeredi [
14
] obtained polyno-
mial bounds on the formula size
τ
(
n
t
over the monotone basis. Using their construction, Fried-
man [
106
] has obtained a bound on formula size over the monotone basis of
O
(
t
c
n
log
n
)
for
c
a large constant.
Over the basis
B
2
, Fischer, Meyer, and Paterson [
101
] have shown that the majority func-
tion
τ
(
n
)
t
, and other symmetric functions require formula size
Ω(
n
log
n
)
.Pudlak
[
264
], building on the work of Hodes and Specker [
136
], has shown that all but 16 symmetric
,
t
=
n/
2
Search WWH ::
Custom Search