Kumar, Mrinal, 1990-.
Lower bounds for bounded depth arithmetic circuits.
Degree: PhD, Computer Science, 2017, Rutgers University
Proving 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…
Advisors/Committee Members: Saraf, Shubhangi (chair), Kopparty, Swastik (co-chair), Allender, Eric (internal member), Raz, Ran (outside member).
Subjects/Keywords: Computer arithmetic and logic units
to Zotero / EndNote / Reference
APA (6th Edition):
Kumar, Mrinal, 1. (2017). Lower bounds for bounded depth arithmetic circuits. (Doctoral Dissertation). Rutgers University. Retrieved from https://rucore.libraries.rutgers.edu/rutgers-lib/54175/
Chicago Manual of Style (16th Edition):
Kumar, Mrinal, 1990-. “Lower bounds for bounded depth arithmetic circuits.” 2017. Doctoral Dissertation, Rutgers University. Accessed September 20, 2020.
MLA Handbook (7th Edition):
Kumar, Mrinal, 1990-. “Lower bounds for bounded depth arithmetic circuits.” 2017. Web. 20 Sep 2020.
Kumar, Mrinal 1. Lower bounds for bounded depth arithmetic circuits. [Internet] [Doctoral dissertation]. Rutgers University; 2017. [cited 2020 Sep 20].
Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/54175/.
Council of Science Editors:
Kumar, Mrinal 1. Lower bounds for bounded depth arithmetic circuits. [Doctoral Dissertation]. Rutgers University; 2017. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/54175/