Information Technology Reference
In-Depth Information
5.9.3.3 Shifted Partials of the Iterated-Matrix-Multiplication Polynomial
Fourier, Limaye, Malod and Srinivasan [
FLMS13
] showed the same lower bound
as [
KSS13
]butforthe
iterated matrix multiplication
polynomial which is known to
have polynomial sized circuits computing it.
Definition 58
(
Iterated matrix multiplication polynomial
)Let
M
1
,...,
M
d
be n
×
n
x
(
k
)
ij
matrices with distinct variables as entries, i.e.,
M
k
=
for
k
=
1
,...,
d
.
i
,
j
≥
n
n
2
d
The polynomial IMM
n
,
d
is a
(
)
-variate degree-
d
polynomial defined as the
(
1
,
1
)
-th entry of the matrix product
M
1
...
M
d
:
IMM
n
,
d
(
x
)
=
(
M
1
...
M
d
)
1
,
1
.
A more useful perspective is to interpret this as a
canonical algebraic branching
program
.
Definition 59
(
Algebraic branching program
) An algebraic branching program
(ABP) comprises a layered directed graph
G
with
(
+
)
layers of vertices, where the
first and last layer consists of a single node (called source and sink respectively), all
other layers consist of
n
vertices, and edges are only between successive layers and
have linear polynomials as edge-weights. The ABP is set to compute the polynomial
f
defined as
d
1
⊨
f
(
x
)
=
weight
(ˀ)
source-sink pat h
ˀ
where the weight of any path is just the product of the edge weights on the path.
The canonical ABP comprises a graph where the
i
-th vertex of layer
(
−
1
)
is
with edge-weight
x
()
ij
connected to the
j
-th vertex of layer
for every choice of
i
,
j
and
. It is easy to see that the polynomial computed by the canonical ABP is in fact
IMM
n
,
d
.
To lower bound the dimension of shifted partial derivatives of IMM
n
,
d
, first note
that a derivative with respect to any variable (or edge) simply results in the sum of all
source-sink paths that
pass
through this edge. [
FLMS13
] uses the following simple
but crucial observation to assist in bounding the dimension of shifted partials.
Observation 60
Assume that d is even. Let e
1
,
e
3
,...,
e
d
−
1
be an arbitrary set of
edges such that e
i
is between layer i and i
1
. Then, there is a unique path from
source to sink that passes through all these edges.
+
Proof
Since these are edges in alternate layers, their starting and ending points
uniquely determine the edges that are picked up from the even-numbered layers to
complete the source-sink path.
≈
∂
∀
d
,[
FLMS13
] consider
the following restriction by removing some edges from the underlying graph:
Since we are interested in
k
-th order derivatives for
k
