Information Technology Reference
In-Depth Information
k
d
C
=
L
i
,
j
,
i
=
1
j
=
1
where
L
i
,
j
are linear polynomials in
. Significant research has been
done with this model, but both subexponential PIT and exponential lower bounds
are open here. Recently, a remarkable universality result was shown for depth-3
[
GKKS13
]: If an
n
-variate poly
F[
x
1
,...,
x
n
]
-degree polynomial can be nontrivially computed
by a circuit, then it can be nontrivially computed in depth-3. This 'squashing' of
depth means that it suffices to focus on depth-3 for PIT purposes.
If we consider a depth-2 circuit (top
(
n
)
gate), over a
ring R
, then again we get
some remarkable connections. Fix
R
to be the 2
×
×
2 matrix algebra
M
2
(
F
)
, and
consider the circuit
d
D
=
L
i
,
i
=
1
where
L
i
are linear polynomials in
R
. Traditionally,
D
is called a
width-
2 algebraic branching program
(ABP). It was shown by [
SSS09
] that depth-3 PIT
efficiently reduces to width-2 ABP PIT.
[
x
1
,...,
x
n
]
Faithful morphisms
It was observed in the last fewyears that in all the known hitting-
sets, the key idea in the proof is to work with a
homomorphism
ϕ
and an algebraic
property
that the image of
ϕ
should preserve. [
SS12
] used a (Vandermonde-based)
map
ϕ
: F[
x
1
,...,
x
n
]≤F[
y
1
,...,
y
k
]
that preserves the 'linear' rank of any
k
linear polynomials. This gave the first blackbox PIT for bounded top fanin depth-3,
over any field.
Beecken et al. [
BMS13
] and Agrawal et al. [
ASSS12
] used a (Vandermonde and
Kronecker-based)
map
ϕ
:
F[
x
1
,...,
x
n
]≤F[
that preserves the 'algebraic' rank (formally,
transcendence
degree
) of certain
k
polynomials. This gave the first blackbox PIT (and lower bounds)
for several well-studied classes of constant-depth circuits. One drawback of the tech-
nique is that it requires zero/large characteristic fields.
y
1
,...,
y
k
]
Rank concentration
Inspired from the tensors, a restricted circuit model called
multilinear read-once ABP (ROABP) has been intensively studied. Let
R
be the
w
×
w
matrix algebra
M
w
(
F
)
and let
{
S
i
}
be a partition of
[
n
]
. Consider the circuit
i
=
1
L
i
,
(i.e. the linear factors
have disjoint variables). For
D
[
FSS13
] gave a hitting-set in time poly
D
=
where
L
i
are linear polynomials in
R
[
x
S
i
]
log
n
,
i.e. quasi-poly-time. The proof is based on the idea, following [
ASS13
], that after
applying a small (Kronecker-based) 'shift',
D
gets the following property: The rank
of its coefficients (viewed as
log
w
·
(w
n
)
-vectors) is concentrated in the 'low' support mono-
mials. Thus, checking the zeroness of these low monomials is enough!
We conjecture that rank concentration, after a 'small' shift, should be attainable
in any ABP
D
. But currently the proof techniques are not that strong. Recently,
[
AGKS13
] have achieved rank concentration in multilinear depth-3 circuits where
F
