Information Technology Reference
In-Depth Information
x
2
x
2
+ 2
x
1
x
4
+
x
2
x
4
+4
x
2
−
x
1
x
4
+
x
2
+
x
1
x
4
+
x
2
−2
x
1
x
1
x
1
x
3
+10
x
1
x
3
−
x
1
x
3
+3
x
1
T
1
T
2
T
3
Fig. 7.1
Nodes and paths in
C
=
T
1
+
T
2
+
T
3
+···
Theorem 3.2 (
Certificate for a non-identity)
Let I be an ideal generated by some
multiplication terms. Let C
=
⊤
i
ↆ[
k
]
T
i
be a depth-
3
circuit that is nonzero modulo
3
I . Then
∗
i
ↆ{
0
,...,
k
−
1
}
such that C
mod I has a path
p
satisfying: C
∅
[
i
]
for some
α
ↆ F
⃐
.
α
·
T
i
+
1
≥∅
0
(
mod
I
+∩
p
)
The proof of this theorem involves an extension of Chinese remaindering to ideals
that are generated by multiplication terms. Once we have this structural result about
depth-3, observe that we would be done if we could somehow ensure
T
i
+
1
(in
our application
I
is zero). How do we preserve this ideal non-membership under a
cheap map?
Notice that the rank of the set
S
0
of linear polynomials that divide the nodes in
the path
p
is
/
ↆ∩
p
k
(since path length is below
k
). Moreover,
T
i
+
1
factors into at most
d
linear polynomials, denote the set by
S
1
. So if we apply a map that preserves the rank
of each of the
d
sets
S
0
⃒{
ʲ
}
,ʲ
ↆ
<
S
1
, then, intuitively, the ideal non-membership
(
S
0
⃒{
ʲ
}
)
∧
should be preserved. As rk
k
we can employ the previously discussed
dnk
2
). This idea could be easily turned into a
map
β
(over a field satisfying
|F|
>
proof; details are in [
SS12
].
Finally, what we have achieved is the construction of amap
,
that reduces the variables of
C
from
n
to
k
and preserves nonzeroness. Once this is
done, the poly
β
, in time poly
(
dnk
)
nd
k
(
)
blackbox PIT follows from the brute-force hitting-set.
7.3.2 Depth
≥
3
Results
Looking at the success of bounded fanin depth-3 one wonders about the analogous
depth-4 model:
=
f
i
,
j
,
C
where
f
i
,
j
are sparse polynomials.
(7.1)
i
ↆ[
k
]
j
ↆ[
d
]
3
We mean
C
[
i
]
:=
⊤
j
ↆ[
i
]
T
j
.
