Information Technology Reference
In-Depth Information
7.3.1 Bounded Fanin Depth-3 Blackbox PIT
=
⊤
i
ↆ[
k
]
Let
C
T
i
be a depth-3 circuit. When
k
is constant,
C
is naturally called
bounded fanin
depth-3. This case of PIT has, by now, a rich history [
DS07
,
KS07
,
KS11
,
SS11
,
KS09
,
SS13
,
SS12
]. Several new techniques have sprung up from this
model— a locally decodable code structure, a rank-preserving map via extractors,
Sylvester-Gallai configurations (higher dimensions and all fields) and rank bounds.
We will sketch here the main idea behind the poly-time blackbox PIT of bounded
fanin depth-3. The details are quite technical and could be seen in [
SS13
,
SS12
].
Vandermonde map
We define a homomorphism
β
,fora
β
ↆ F
,as:
k
ij
y
j
,
i
ↆ[
n
]
,
β
:
x
i
≤
1
β
j
=
and
β
(α)
=
α
for all
α
ↆ F
. This (naturally) defines the action of
β
,on
all
the elements of
, that preserves the ring operations. We have the following nice
property, as a consequence of [
GR08
, Lemma 6.1]:
R
Lemma 3.1
[
β
preserves
k
-rank]
Let S be a subset of linear forms in
R
with
nk
2
. Then
rk
(
S
)
∧
k, and
|F|
>
∗
β
ↆ F
,
rk
(ψ
β
(
S
))
=
rk
(
S
)
.
.
The proof of this lemma is by studying the coefficient-matrix of the linear polynomi-
als in
S
, and its change under
Intuitively,
β
is
faithful
to any algebraic object involving the elements in span
(
S
)
β
. This map has a role to play in bounded fanin depth-3
owing to a certain structural theorem from [
SS13
]—
certificate for a non-identity
.
To discuss this certificate we need a definition, that of 'paths' of 'nodes' in
C
(assumed to be nonzero). A
path
p
with respect to an ideal
I
is a sequence of
terms
(these are products of linear forms) with the following prop-
erty. Each
p
i
divides
T
i
, and each
p
i
is a 'node' of
T
i
with respect to the ideal
∩
{
p
1
,
p
2
,...,
p
b
}
.
2
So
p
1
is a node of
T
1
wrt
I
,
p
2
is a node of
T
2
wrt
,
p
1
,
p
2
,...,
p
i
−
1
∩
,
p
1
I
I
,
etc.
Let us see an example of a path
in Fig.
7.1
. The oval bubbles
represent the list of forms in a product gate, and the rectangles enclose forms in a
node. The arrows show a path. Starting with the zero ideal, nodes
p
1
:=
(
∩
0
,
p
1
,
p
2
,
p
3
)
x
1
,
p
2
:=
x
2
(
x
2
+
2
x
1
)
, and
p
3
:=
(
x
4
+
x
2
)(
x
4
+
4
x
2
−
x
1
)(
x
4
+
x
2
+
x
1
)(
x
4
+
x
2
−
2
x
1
)
form a path. Initially, the path is just the zero ideal, so
x
1
is a node. Note how
p
2
is
a power of
x
2
modulo radsp
.
The non-identity certificate theorem [
SS13
, Theorem 25] states that for any non-
identity
C
, there exists a path
p
such that modulo
∩
p
1
, and
p
3
is a power of
x
4
modulo radsp
∩
p
1
,
p
2
∩
p
,
C
reduces to a single nonzero
multiplication term.
2
By a
node p
i
we mean that some nonzero constant multiple of
p
i
is identical to a power-of-a-
linear-form modulo radsp
∩
I
,
p
1
,
p
2
,...,
p
i
−
1
, where radsp is the ideal generated by the set of all
the linear polynomials that divide
p
j
,
j
ↆ[
i
−
1
]
and the generators of
I
.
