Information Technology Reference
In-Depth Information
the partitions (corresponding to each product gate) are 'close' to each other in the
sense of 'refinement'.
7.2 Shallow Circuits, Deep Interconnections
In this section, we exhibit the key ideas behind the universality of two shallowcircuits.
7.2.1 The Depth-
3
Chasm
In the study of circuits one feels that low-depth should already hold the key. This
feeling was confirmed in a series of work [
VSBR83
,
AV 0 8
,
Koi12
,
Tav13
]: Any
poly
(
n
)
-degree
n
-variat
e
polynomial computed by a poly
(
n
)
-sized circuit
C
can also
be computed by a
n
O
(
∈
n
)
-sized depth-4 circuit!
The idea for this is, in retrospect, simple—since the degree is only poly
(
n
)
, first,
squash the depth of
C
to
O
by only a polynomial blowup in the size. This is
done in a way so as to make the product gates quite
balanced
, i.e. their two inputs
are roughly of the same degree. Next, identify a
su
bcircuit
C
2
by picking those gates
(
log
n
)
whose output polynomial has degree at least
∈
n
, and call the remaining subcircuit
C
1
.Weview
C
2
as our circuit of interest that takes
ga
tes of
C
1
as input. It can be
shown that
C
2
computes a polynomial of degree
∃
∈
n
of its input variables (which
(
)
are
po
ly
n
many). Obviously, each gate of
C
1
also computes a polynomial of degree
∃
∈
n
of its inp
u
t variables (which are
x
1
,...,
x
n
). Thus,
C
2
finally computes a sum
∃
⊡
poly
(
n
)
+
∈
n
⊣
products, each product has
∈
n
factors, and each factor is itself a
of
∈
n
∈
n
⊣
degree-
∈
n
monomials. To put it simply (and ignoring the constant
factors),
C
can be expressed as a
⊤
∈
n
⊤
∈
n
circuit of size
n
O
(
∈
n
)
. The details
of this proof can be seen in [
Tav13
].
The strength of depth-4 is surprising. Recently, an even m
o
re surprising reduction
has been shown [
GKKS13
]—that to depth-3 (again,
n
O
(
∈
n
)
sized). We will now
sketch the proof. It ties together the known results in an unexpected way.
∃
⊡
n
+
∈
n
sum of
Esse
nt
ially, the idea is to modify a
⊤
a
⊤
a
circuit
C
of size
s
n
a
(where
:=
:=
∈
n
) by using two polynomial identities that are in a way “inverse” to each
other, and are to do with powers-of-linear-forms. First, replace the product gates
using Fischer's identity:
a
Lemma 2.1
[
Fis94
]
Any degree a monomial can be expressed as a linear combina-
tion of
2
a
−
1
ath powers of linear polynomials, as:
⊦
y
1
+
⊛
a
a
2
a
−
1
!
)
−
1
#
{
i
|
r
i
=−
1
}
.
y
1
···
y
a
=
(
·
a
·
r
i
y
i
·
(
−
1
)
r
2
,...,
r
a
ↆ{±
1
}
i
=
2
