Information Technology Reference
In-Depth Information
are first created. This will be useful later when discussing Boolean convolution and Boolean
matrix multiplication, since each of their prime implicants depends on two variables.
BOOLEAN CONVOLUTION
Convolution over commutative rings is defined in Section
6.7
.In
this section we introduce the Boolean version, which is defined by a monotone multiple-output
function, and derive a lower bound of
n
3
/
2
on its monotone circuit size. We also show that
over a complete basis Boolean convolution can be realized by a circuit of nearly linear size.
DEFINITION
9.6.3
The
Boolean convolution function
f
(
n
)
2
n
2
n−
conv
:
B
→B
1
maps Boolean
n
-tuples
a
=(
a
0
,
a
1
,
...
,
a
n−
1
)
and
b
=(
b
0
,
b
1
,
...
,
b
n−
1
)
onto a
(
2
n
−
1
)
-tuple
c
, denoted
c
=
a
⊗
b
,where
c
j
,
0
≤
j
≤
2
n
−
2
,isdefinedas
c
j
=
r
+
s
=
j
a
r
∧
b
s
Boolean convolution can be realized by a circuit over the standard basis
Ω
0
for multiplying
binary numbers (see Section
2.9
) as follows. Represent
a
and
b
by the following integers where
q
=
log
2
n
+
1:
n−
1
n−
1
a
i
2
qi
,
b
j
2
qj
a
=
b
=
i
=
0
j
=
0
That is, each bit in
a
and
b
is separated by
log
2
n
zeros. The formal product of
a
and
b
is
⎛
⎝
i
+
j
=
k
⎞
2
n−
2
⎠
2
qk
ab
=
a
i
b
j
k
=
0
Because no inner sum in the above expression is more than 2
n
1, at most
q
bits suffice to
represent it in binary notation. Consequently, there is no carry between any two inner sums.
It follows that an inner sum is non-zero if and only if
c
k
=
1. Thus, the value of
c
k
can be
obtained by forming the
OR
of the bits in positions
kq
,
kq
+
1,
...
,
kq
+
q
−
1oftheproduct.
Since two binary
m
tuples can be multiplied in the standard binary notation by a circuit of
size
O
(
m
(log
m
)(log log
m
))
(see Section
2.9.3
), the function
f
(
n
)
−
conv
can be computed by a
circuit of size
O
n
(log
2
n
)(log log
n
)
since
m
=
nq
=
O
(
n
log
n
)
.
THEOREM
9.6.3
The circuit size of
f
(
n
)
2
n
2
n−
1
over the standard basis satisfies
conv
:
B
→B
C
Ω
0
f
(
n
)
conv
=
O
n
(log
2
n
)(log log
n
)
Our goal is to use the function replacement method to show that every monotone circuit
for Boolean convolution has size
Ω(
n
3
/
2
)
. As explained above, the method is designed to
use induction to prove lower bounds on monotone circuit size. Each replacement step removes
prime implicants from the function
g
computed at some gate and changes the function
f
com-
puted by the circuit. If the new function
f
∗
is in the same family as
f
,thegate-replacement
process can continue and induction can be applied. Since the convolution function does not
necessarily change to another instance of itself on fewer variables, we place this function in the
class of semi-disjoint bilinear forms.
Search WWH ::
Custom Search