Information Technology Reference
In-Depth Information
This, togetherwith the previous subsection, makes the
⊤
circuits over
M
2
(
F
)
quite
strong.
Say, we want to express the depth-3 circuit
C
=
⊤
i
=
1
T
i
in a 2
×
2 matrix product.
=
j
=
1
ʲ
i
,
j
as:
First, we express a product
T
i
⊞
ʲ
i
,
1
0
01
⊠
⊞
ʲ
i
,
d
−
1
0
01
⊠
⊞
1
⊠
⊞
T
i
T
i
01
⊠
ʲ
i
,
d
01
where
T
i
···
·
=
,
:=
T
i
/ʲ
i
,
d
.
th place, we
would like to sum the
T
i
's in a 'doubling' fashion (instead of one-by-one).
We describe one step of the iteration. Let
Once we have such
k
2
×
2 matrices, each containing
T
i
in the
(
1
,
2
)
⊠
be
encapsulating two intermediate summands
f
and
g
. With the goal of getting (a
multiple of)
f
⊞
L
1
⊠
and
⊞
M
1
L
2
f
M
2
g
0
L
3
0
M
3
+
g
we consider the following, carefully designed, product:
⊞
L
1
⊠
⊞
L
2
M
3
⊠
⊞
M
1
⊠
L
2
f
0
M
2
g
·
·
0
L
3
0
L
1
M
2
0
M
3
⊞
L
1
M
1
L
2
M
3
⊠
L
2
M
3
L
1
M
2
(
f
+
g
)
=
0
L
3
M
3
L
1
M
2
After log
k
such iterations, we get a
multiple
of
C
in the
(
1
,
2
)
-th entry of the final
2
2 matrix product. Note that the middle matrix, introduced in the LHS above,
potentially doubles (in the degree of the entry polynomials) in each iteration. Thus,
finally,
D
is a product of poly
×
d
2
log
k
(
)
linear polynomials over
M
2
(
F
)
. Thus, the size
blowup is only polynomial in going from depth-3 to width-2.
7.3 Faithful Morphisms, Hitting-Sets
In algebraic complexity the study of certainmaps has been fruitful—homomorphisms
ϕ
:
R
:= F[
y
k
]=:
R
such that the algebraic 'relation-
x
1
,...,
x
n
]≤F[
y
1
,...,
ship' of certain polynomials
does not change in the image of
ϕ
. When
f
i
's are linear this boils down to a linear algebra question and we can easily design
ϕ
in time poly
{
f
1
,...,
f
k
}
(hint: employ Vandermonde matrix). This business becomes compli-
cated when
f
i
's are nonlinear. Then we have to ask how are
f
i
's represented. If they
are given via monomials then we invoke the Jacobian criterion to design
ϕ
,butthe
time complexity becomes exponential in
k
. Several variants of such faithful maps are
discussed in the Ph.D thesis [
Mit13
]. We sketch the ideas behind two basic maps here.
(
n
)
