Information Technology Reference
In-Depth Information
=
H
w
(
F
)
For the following discussionwe fix a base commutative ring
R
called the
k
w
×
w
(
F
,
+
,)
Hadamard
algebra (instead of the
matrix algebra). This is basically
,
where
+
is the vector addition and
is the coordinate-wise vector product (called
the Hadamard product).
ʲ
-
concentration.
We say that a polynomial
f
ↆ
R
[
x
1
,...,
x
n
]
is
ʲ
-
concentrated
if
rk
F
{
coef
f
(
x
S
)
|
S
ₒ[
n
]
,
|
S
|
<ʲ
}=
rk
F
{
coef
f
(
x
S
)
|
S
ₒ[
n
]}
,
where coef
f
extracts a coefficient in
f
.
I.e. the coefficient-vectors of 'lower' monomials already span every possible
coefficient-vector in
f
. We are interested in studying whether circuits compute
an
ʲ
-concentrated polynomial for small
ʲ
(say, log
n
instead of
n
). By itself this
is not true, e.g. the trivial circuit
D
x
n
is not even
n
-concentrated. But,
maybe we can transform
f
a bit and then attain
=
x
1
···
(
log
n
)
-concentration? In this case,
D
:=
is suddenly 1-concentrated!
It was shown by [
ASS13
] that any
D
, above
R
, becomes
D
(
x
1
+
1
,...,
x
n
+
1
)
-concentrated after
applying a 'small' shift; the price of which is
n
log
k
time. Once we have this it directly
applies to the set-multilinear depth-3 model. Since, a depth-3
C
(
log
k
)
=
⊤
i
ↆ[
k
]
T
i
can be
⊜
⊨
⊩
T
1
T
k
=
,...,
·
=
rewritten as
C
[1
1]
D
, where
D
is of the promised sort over
R
=
H
k
(
F
)
(since
D
completely factorizes into disjoint-variate linear polynomials).
So,
-concentration in
D
implies an easy way to check
C
for zeroness—test the
coefficients of the monomials below
ʲ
-support in
C
.
Glimpse of a proof
We now show how to achieve
ʲ
ʲ
ʲ
=
(
)
-concentration,
O
log
k
,in
the following toy model:
D
=
(
1
+
z
i
x
i
),
where
z
i
ↆ
H
k
(
F
).
(7.2)
i
ↆ[
n
]
Because of the disjointness of the factors it can be seen, as a simple exercise, that:
D
is
ↆ
⊡
[
n
]
ʲ
⊣
.
:=
i
ↆ
S
(
ʲ
-concentrated iff
D
S
1
+
z
i
x
i
)
is
ʲ
-concentrated, for all
S
Thus, from now on we assume, wlog,
n
.
Shift
D
by formal variables
t
, and normalize, to get a new circuit:
=
ʲ
D
z
i
x
i
),
where
z
i
=
(
1
+
ↆ
H
k
(
F
(
t
)).
i
ↆ[
ʲ
]
We can express the new coefficients as:
z
i
=
z
i
/(
1
+
z
i
t
i
),
i
ↆ[
ʲ
]
.
Conversely, we write:
z
i
/(
z
i
t
i
),
=
−
ↆ[
ʲ
]
.
z
i
1
i
(7.3)
