Description
TitleLower bounds for bounded depth arithmetic circuits
Date Created2017
Other Date2017-05 (degree)
Extent1 online resource (viii, 201 p. : ill.)
DescriptionProving lower bounds for arithmetic circuits is a problem of fundamental importance in
theoretical computer science. In recent years, an approach to this problem has emerged
via the depth reduction results of Agrawal and Vinay [AV08], which show that strong
enough lower bounds for extremely structured bounded depth circuits (even homogeneous
depth-4 circuits) suffice for general arithmetic circuits lower bounds. In this dissertation,
we study homogeneous depth-4 and homogeneous depth-5 arithmetic circuits
with a view towards proving strong lower bounds, and understanding the optimality of
the depth reduction results. Some of our main results are as follows.
• We show a hierarchy theorem for bottom fan-in for homogeneous depth-4 circuits
with bounded bottom fan-in. More formally, we show that there for a wide range
of choice of parameter t, there is a homogeneous polynomial in n variables of
degree d = nΘ(1) which can be computed by a homogeneous depth-4 circuit of
bottom fan-in t, but any homogeneous depth-4 circuit of bottom fan-in at most
t/20 must have top fan-in nΩ(d/t)
• We show that there is an explicit polynomial family such that any homogeneous
depth-4 arithmetic circuit computing it must have super-polynomial size. These
were the first superpolynomial lower bounds for homogeneous depth-4 circuits
with no restriction on top or bottom fan-in. Simultaneously and independently,
a similar lower bound was also proved by Kayal et al [KLSS14b].
• We show that any homogeneous depth-4 circuit computing the iterated matrix
multiplication polynomial in n variables and degree d = n
Θ(1) must have size at
least nΩ(√d). This shows that the upper bounds of depth reduction from general
arithmetic circuits to homogeneous depth-4 circuits are almost optimal, up to a
constant in the exponent. Moreover, these were the first nΩ(√d) lower bounds
for homogeneous depth-4 circuits over all fields. Prior to our work, Kayal et
al. [KLSS14a] had shown such a lower bound over the fields of characteristic zero.
• We show that there is a family of polynomials in n variables and degree d =
O(log2 n) which can be computed by linear size homogeneous depth-5 circuits
and polynomial size non-homogeneous depth-3 circuits but require homogeneous
depth-4 circuits of size nΩ(√d). In addition to indicating the power of increased
depth, and non-homogeneity, these results also show that for the range of parameters
considered here, the upper bounds for the depth reduction results [AV08,
Koi12, Tav15] are close to optimal in a very strong sense : a general depth reduction
to homogeneous depth-4 circuits of size nΩ(√d) is not possible even for
homogeneous depth-5 circuits of linear size.
• We show an exponential lower bound for homogeneous depth-5 circuits computing
an explicit polynomial over all finite fields of constant size. For any non-binary
field, these were the first such super-polynomial lower bounds, and prior to our
work, even cubic lower bounds were not known for homogeneous depth-5 circuits.
On the way to our proofs, we study the complexity of some natural polynomial families
(for instance, homogeneous depth-4, depth-5 circuits, iterated matrix multiplication)
with respect to many existing partial derivative based complexity measures, and also
define and analyze some new variants of these measures [KS14, KS15b].
NotePh.D.
NoteIncludes bibliographical references
Noteby Mrinal Kumar
Genretheses, ETD doctoral
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.