Information Technology Reference
In-Depth Information
P
1
is a
refinement
of
P
2
(denoted
P
1
∧
P
2
) because:
We can say, naturally, that
ↆ
P
2
there exist colors in
P
1
whose union is
exactly S
.
For every color (or part)
S
In this refinement situation [
AGKS13
] showed that, again, a suitable shift in the
⊤
circuit
D
(corresponding to
C
) achieves
n
log
k
ʲ
-concentration in time poly
(
)
.
Glimpse of a proof
We can assume
P
1
, otherwise this case is
no different from the last subsection. We assume that the first
k
1
product gates in
C
P
2
different from
⊤
i
ↆ[
k
]
=
T
i
respect
P
1
and the rest
k
2
respect
P
2
. The corresponding circuit
⊜
⊨
⊩
T
1
T
k
D
where we desire to achieve concentration is
D
=
over
R
=
H
k
(
F
)
.
But now the linear factors of
D
are not necessarily in disjoint variables. Example
⊞
x
1
x
2
x
1
+
⊠
x
1
+
⊞
0
1
⊠
x
2
⊞
0
1
⊠
⊞
1
0
⊠
x
2
over
H
2
(
F
)
.
To get some kind of a reduction to the set-multilinear case, we prove rank
concentration in parts. First, we consider those monomials (called
=
·
·
+
·
x
2
P
1
-
type
) that
could only be produced by the 'upper' part of
D
(i.e. the first
k
1
product gates
of
C
). Such a monomial, say indexed by
S
ₒ[
n
]
, is characterized by the presence
of
i
,
j
ↆ
S
that are in the same color of
P
2
. For a fixed such
i
,
j
we can “access”
2
D
all such monomials by the derivative
∂
/∂
x
i
∂
x
j
=:
∂
i
,
j
D
. Notice that this dif-
ferentiation kills the 'lower' part of
D
and only the
P
1
-part remains. So, we can
prove
(
2
+
log
k
1
)
-concentration in the monomials containing
i
,
j
as in Sect.
7.4.1
.
This proves
O
P
1
-type.
Next, we want to understand the remaining monomials (called
(
log
k
1
)
-concentration in the monomials of
P
2
-type); those
that could be produced by the 'lower' part of
D
(i.e. the last
k
2
product gates of
C
).
These, obviously, could also be produced by the upper part of
D
. Let us fix such a
monomial, say
x
1
···
. Assume that
S
1
,...,
S
ʲ
ↆ
P
2
are the colors that contain
x
ʲ
,...,ʲ
one of the indices 1
. Consider the subcircuit
D
ʲ
that in its
i
-th coordinate,
i
ↆ[
k
]
, simply drops those factors of
T
i
that are free of the variables
S
1
⃒···⃒
S
ʲ
.
The problem here is that
D
may be a 'high' degree circuit (
∃
n
instead of
ʲ
) and so
ʲ
we cannot use a proof like in Sect.
7.4.1
.
But, notice that all the degree-
(
ₔ
ʲ)
monomials in
D
are
P
1
-type; where we
ʲ
know how to achieve
ʲ
-concentration. So, we only have to care about degree-(
∧
ʲ
)
P
2
-type monomials in
D
-concentration can be shown using
Sect.
7.4.1
and the well-behaved transfer equations.
This sketch, handling two refined partitions, can be made to work for significantly
generalized models [
AGKS13
]. But, multilinear depth-3 PIT is still open (nothing
better than exponential time known).
. There, again,
(
log
k
)
ʲ
Remark 4.1
Using a different technique [
AGKS13
] also proves
constant
-
concentration, hence designs
poly
-time hitting-sets, for certain constant-width
ROABP. Thesemodels are arithmetic analogs of the
boolean
ones—width-2 read-once
branching programs [
AGHP92
,
NN93
] and constant-width read-once permutation
branching programs [
KNP11
].
