Information Technology Reference
In-Depth Information
We denote this type of a circuit by the notation
⊤⊝
a
⊤
, where the wedge
signifies the powering by
a
. The above identity transforms the
⊤
a
⊤
a
circuit
C
to a
⊤⊝
a
⊤⊝
a
⊤
circuit, of size poly
. We reuse
s
for this size estimate.
Next, the two power gates are 'opened' up using an identity introduced by the
author:
(
s
)
,
Lemma 2.2
[
Sax08
]
For any a
m, there exist degree-a univariate polynomials f
i
,
j
such that
ma
+
1
m
a
(
y
1
+···+
y
m
)
=
f
i
,
j
(
y
j
).
i
=
1
j
=
1
Let us carefully see the jugglery on
C
.The
⊤⊝
a
⊤⊝
a
⊤
circuit
C
has the
expression
C
=
⊤
i
(
⊤
s
j
=
1
ʲ
e
i
,
j
i
,
j
)
a
with linear
T
i
, where each
T
i
has the form
ʲ
i
,
j
's.
We want to open up the top power gate of
C
. By Lemma 2.2 we get
sa
+
1
s
e
i
,
j
i
T
i
=
f
u
,
j
(ʲ
j
).
,
u
=
1
j
=
1
Since
f
u
,
j
is a univariate, it splits into linear polynomials when the base field
F
is
ʲ
i
,
j
is already a linear polynomial, we deduce that
T
i
, and
algebraically closed
.As
hence
C
,isa
⊤⊤
circuit of size poly
(
)
.
Finally, note that for the above arguments to work, we require
s
F
to be algebraically
closed and char
a
. Lemma 2.2 has been generalized to all characteristics by
[
FS13b
], so it is likely that this depth-3 reduction can be extended to
all
algebraically
closed fields.
The optimality of
n
∈
n
-size, in this reduction, is open. However, [
KSS13
]showed
that any decent reduction in this size bound would imply
VNP
(
F
)>
≥=
VP
.
7.2.2 The Width-
2
Chasm
Here we look at
⊤
circuits over a matrix algebra. Though the model
D
=
i
L
i
,
with linear
L
i
, seems innocuous at first sight, a closer look proves
the opposite! It can be shown fairly easily that a polynomial computed by a constant-
depth circuit (over a field) can as well be computed by a
D
over a 3
ↆ
R
[
x
1
,...,
x
n
]
×
3matrix
algebra [
BC88
]. On the other extreme, by taking
R
=
M
n
(
F
)
we can compute the
n
[
MV97
], hence, arithmetic
formulas
(not general
circuits!) can be simulated in this model [
Va l 7 9
].
Perhaps surprisingly, [
SSS09
] showed that: A polynomial
C
computed by a depth-
3 circuit (over a field) can be “almost”
1
computed by a
D
over a 2
n
×
determinant
of a matrix in
F
×
2 matrix algebra.
1
We are able to compute only a
multiple
of
C
. However, the extra factor is simply a product of
poly-many linear polynomials. So, it suffices for PIT purposes.
