Information Technology Reference
In-Depth Information
We write
z
S
for
i
ↆ
S
z
i
. Now the goal is to 'lift' an
F
-dependence of
z
S
's to the
z
S
; which ultimately shows the condition on the shift that shall yield concentration.
Consider the 2
ʲ
vectors
{
|
ₒ[
ʲ
]}
ʲ>
z
S
S
.If
log
k
then there is a nontrivial
linear dependence amongst these vectors, say,
α
S
z
S
=
0
,
where
α
S
ↆ F
.
S
ₒ[
ʲ
]
Rewriting this in terms of
z
S
we get:
z
i
/(
z
i
t
i
)
=
α
S
·
1
−
0
.
S
ₒ[
ʲ
]
i
ↆ
S
Or,
S
z
S
·
z
i
t
i
)
=
α
S
·
S
(
1
−
0
.
(7.4)
ₒ[
ʲ
]
i
ↆ[
ʲ
]\
Let us collect the 'coefficient' of
z
[
ʲ
]
in the above expression. It comes out to,
)
|[
ʲ
]\
S
|
·
α
S
·
(
−
1
t
[
ʲ
]\
S
.
(7.5)
S
ₒ[
ʲ
]
If we can ensure this expression to be nonzero then Eq. (
7.4
) tells us that
z
[
ʲ
]
is in the
-span of the 'lower'
z
S
. But, ensuring the nonzeroness of Eq. (
7.5
)is
easy—use
t
i
's such that all the (
F
(
t
)
)-support monomials
t
S
are
distinct
. We can use
standard sparse PIT tricks [
BHLV09
] for this, in time poly
∧
ʲ
n
ʲ
)
.
What we have shown is that, after applying a Kronecker-based shift, the circuit
D
becomes
(
-concentrated; all this in time
n
O
(
log
k
)
. This 'recipe' of studying the
generic shift, via some combinatorial properties of the 'transfer' equations (
7.3
), is
generalized in [
ASS13
] to other
D
; and further improved in [
FSS13
] to multilinear
ROABP. The latter use a 'primal' interpretation of the 'transfer' matrix and show
that the linear transformation- corresponding to a Kronecker shift together-with the
truncation of the high-support monomials -behaves like a
rank-extractor
.
It is not known how to design such hitting-sets, even for the toy case, in
poly
-time.
ʲ
7.4.2 Towards Multilinear Depth-
3
It is tantalizing to achieve
-concentration in multilinear depth-3 (before embarking
on the general depth-3!). A partial result in that direction was obtained in [
AGKS13
].
We will sketch their ideas in a toy model.
Consider a multilinear depth-3 circuit
C
with only
two
partitions being induced
by the product gates—
ʲ
P
2
. Say, the
number of the corresponding product gates is
k
1
respectively
k
2
(summing to
k
).
P
1
= {{
1
}
,
···
,
{
n
}}
and an arbitrary partition
