Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for +publisher:"Rutgers University" +contributor:("Raz, Ran"). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Rutgers University

1. 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

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

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. https://rucore.libraries.rutgers.edu/rutgers-lib/54175/.

MLA Handbook (7th Edition):

Kumar, Mrinal, 1990-. “Lower bounds for bounded depth arithmetic circuits.” 2017. Web. 20 Sep 2020.

Vancouver:

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/

.