Information Technology Reference
In-Depth Information
The number of summands
s
is called the top fan-in of the circuit.
Further, a
[
a
]
[
b
]
circuit is a depth-4 circuit computing a polynomial of the
form
f
=
Q
11
...
Q
1
a
+ ··· +
Q
s
1
...
Q
sa
where deg
Q
ij
≥
b
for all
i
,
j
.
5.9.1 Significance of the Model
In a surprising series of results on depth reduction, Agrawal and Vinay [
AV 0 8
]
and subsequent strengthenings of Koiran [
Koi12
] and Tavenas [
Tav13
] showed that
depth-4 circuits more or less capture the complexity of general circuits.
Theorem 41
[
AV 0 8
,
Koi12
,
Tav13
]
If f is an n variate degree-d polynomial
compute
d
by a
si
ze s arithmetic circuit,
th
en
f
can also be computed by a
[
O
(
∀
d
)
]
[
∀
d
]
circuit of size
exp
O
.
(
∀
d
log
s
)
[
O
(
∀
d
)
]
[
∀
d
]
cir-
Conversely, if an n-
va
riate degree-d polynomial requires
cuits of size
exp
, then it requires arbitrary depth arithmetic circuits
of size n
ˇ(
log
s
/
log
n
)
to compute it.
ˇ(
∀
d
log
s
)
Thus proving strong enough lower bounds for this special case of depth-4 circuits
imply lower bounds for general circuits. Themain results of the section is some recent
lower bound [
GKKS13
,
KSS13
,
FLMS13
] that comes very close to the required
threshold.
5.9.2 Building the Complexity Measure
As a simpler task, let us first attempt to prove lower bounds for expressions of the
form
Q
1
+ ··· +
Q
s
f
=
where each of the
Q
i
's are quadratics. This is exactly the problem studied by
Kayal [
Kay12
], which led to the complexity measure for proving depth-4 lower
bounds.
The goal is to construct a measure
is small whenever
f
is a
power of a quadratic. As a first attempt, let us look at the space of
k
-th order partial
derivatives of
Q
d
(for a suitable choice of
k
). Unlike the case of
such that
(
f
)
⃐
-circuits where
d
had dimension 1, the space of partial
derivatives of
Q
d
could be as large as it can be expected. Nevertheless, the following
simple observation would provide the key intuition.
the space of
k
-th order partial derivatives of
