Information Technology Reference
In-Depth Information
6. An
extreme
depth reduction result is given by the highly influential paper of
Agrawal and Vinay [
AV 0 8
]. To first see the context, note that any polynomial
in
n
varia
b
les with degree
d
has an unbounded fan-in depth-2 circuit of size
2
O
(
d
+
d
log
d
)
. (If
d
, then 2
O
(
d
)
suffices, otherwise the second term in the
exponent makes up.) This is because we can just explicitly compute all monomials
of degree at most
d
, and add up the required ones with suitable wei
g
hts. Now, can
we find circuits substantially better than this, say even 2
o
(
d
+
d
log
d
)
, if we allow
depth to be increased a bit? Agrawal andVinay showed that indeed this is possible,
even with depth 4, provided there is some circuit (not necessarily depth-reduced)
of that size to beginwith. The idea is extremely simple. Peform the depth reduction
from [
VSBR83
]or[
AJMV98b
], and ensure with some additional care that degree
provably drops at
∃
ˇ(
n
)
gatemayhavefanin
upto 6, instead of 2.) Now, choose a horizontal cut in the depth-reduced circuit so
that for the sub-circuit above it, and for the sub-circuits below it rooted at gates
on the cut, the “brute-force” construction described above is small. Obviously
there is a trade-off: if the cut is too high up, the lower sub-circuits can have large
explicit forms, but if it is too low down, the upper sub-circuit can have large
explicit forms. Cut in the right place, and everything works out!
Subsequently the extreme depth-reductions have been pushed further; see
[
Koi12
,
Tav13
,
GKKS13b
]. The lower bound results of [
GKKS13a
,
FLMS13
]
show that the depth reduction upper bound from [
Tav13
] is tight and cannot be
pushed any further.
This has significant implications for the quest for derandomizing algorithms
for the well-studied problemACIT (arithmetic circuit identity testing)—checking
if a given circuit computes the identically zero polynomial. But that is not directly
connected with this survey. One question it raises here is: what kind of extreme
depth reduction can we achieve for VQP? Can we stay within quasi-polynomial
size?
×
gates. (The price for this is small: a
×
4.4 The Syntactic Multilinear World
Much of the study concerningVP andVNP involves the families
.
The polynomials in both families are
multilinear
. In principle, to compute a multilin-
ear polynomial via a circuit, we need never compute intermediate polynomials that
are not multilinear. Let us call such circuits, where the polynomial computed at each
node is multilinear,
multilinear circuits
. However, often it is the case that allowing
non-multilinear terms at intermediate stages, and eventually cancelling them out,
allows more efficient computation (smaller circuits). This leads to the following
quest: what kind of multilinear
p
-families have efficient multilinear formulas, or
even multilinear circuits, where each intermediate polynomial is required to be mul-
tilinear? Even for the
(
Det
n
)
amd
(
Perm
n
)
family, which we know is multilinear and in VP, we do
not know of polynomial size multilinear circuits. That being the case, can we prove
lower bounds?
(
Det
n
)
