Information Technology Reference
In-Depth Information
6.2.3 From Tensor Rank Bounds to Formula Size Bounds
k
n
k
n
, we associate the following polynomial
With a tensor
t
=
(
t
i
1
,...,
i
d
)
∗
≤···≤
in the
nd
variables
X
i
,
j
,1
ↆ
i
ↆ
d
,1
ↆ
j
ↆ
n
:
n
n
f
t
=
1
···
t
i
1
,...,
i
d
X
1
,
i
1
···
X
n
,
i
n
.
i
1
=
i
d
=
1
Raz [
Raz10
] proved the following result:
Theorem 2
For any family of tensors t
n
of order d
(
n
)
such that
ʳ(
1
)
ↆ
d
(
n
)
ↆ
n
(
1
−
o
(
1
))
d
(
n
)
, the polynomials f
t
n
o
(
log
n
/
log log
n
)
and R
(
t
n
)
∧
have superpoly-
nomial formula size.
n
d
(
n
)
by the trivial decomposition. Therefore, the family
t
n
has “almost” highest rank possible. It is a major open problem to find a family of
polynomials with superpolynomial formula size. So finding high rank tensors might
be a way of doing so. The best lower bounds we have are due to Kalorkoti [
Kal85
]
and are quadratic.
Several decades earlier, Strassen [
St73
] proved the following result.
Note that
R
(
t
n
)
ↆ
Theorem 3
For any family of tensors t
n
of order
3
, the circuit complexity of the
trilinear forms f
t
n
are bounded by
ʲ(
R
(
t
n
))
.
This means that a family of tensors of superlinear rank yields a family of poly-
nomials with superlinear circuit complexity, something which we do not know for
general circuit models.
But there is a catch, as we will see in the next section. Finding some family
of tensors/polynomials with the desired properties is easy, a random choice does
the job. So what we really want is an
explicit
tensor. We call a family of tensors
t
n
=
(
t
n
;
i
1
,...,
i
d
can be computed
by an arithmetic circuit of size polynomial in
d
and log
n
. One can think also of other
notion of explicitness. For the purpose of this appetizer, any notion that prevents
random tensors is fine. If the entries of the tensors are rational, we could also require
that the mapping is computable in
P
t
n
;
i
1
,...,
i
d
)
explicit if the mapping
(
n
;
i
1
,...,
i
d
)
∩≥
poly
. Then, by using Valiant's criterion, we can
use high rank tensors to separate classes in Valiants model, in particular, we could
show that the permanent does not have polynomial size formulas, see [
Bür00
].
/
6.2.4 Random Tensors
Let
V
be a vector space of dimension
n
. Ageneric rank-one tensor in
V
≤
d
is described
by
dn
variables,
(
x
1
,
1
,...,
x
n
,
1
)
≤···≤
(
x
1
,
d
,...,
x
n
,
d
).
