Show simple item record

dc.contributor.advisorSaha, Chandan
dc.contributor.authorSharma, Abhijat
dc.date.accessioned2018-05-29T16:29:49Z
dc.date.accessioned2018-07-31T04:40:32Z
dc.date.available2018-05-29T16:29:49Z
dc.date.available2018-07-31T04:40:32Z
dc.date.issued2018-05-29
dc.date.submitted2017
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/3637
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/4507/G28453-Abs.pdfen_US
dc.description.abstractWe study the problem of proving lower bounds for depth four arithmetic circuits. Depth four circuits have been receiving much attraction when it comes to recent circuit lower bound results, as a result of the series of results culminating in the fact that strong enough lower bounds for depth four circuits will imply super-polynomial lower bounds for general arithmetic circuits, and hence solve one of the most central open problems in algebraic complexity i.e a separation between the VP and VNP classes. However despite several efforts, even for general arithmetic circuits, the best known lower bound is Omega(N log N) by Baur and Strassen (1983), where N is the number of input variables. In the case of arithmetic formulas, Kalorkoti (1985) proved a lower bound that is quadratic in the number of input variables, which has not seen any improvement since then. The situation for depth three arithmetic circuits was also similar for many years, until a recent result by Kayal et. al. (2016) achieved an almost cubic lower bound that improved over the previous best quadratic bound by Shpilka and Wigderson (1999). As the main contribution of this thesis, we prove an Omega(N^1.5) lower bound on the size of a depth four circuit, for an explicit multilinear N-variate polynomial in VNP with degree d = Theta(sqrt(N)). Our approach offers a potential route to proving a super-quadratic lower bound for depth four circuits. Taking cue from the numerous successful results recently, we use the technique of the shifted partial derivatives measure to achieve the said lower bound. Particularly, we use the Dimension of Projected Shifted Partials (DPSP) measure which has been previously used in recent depth four results. Coming to the choice of the hard polynomial, we again follow the status quo and use a variant of the Nisan-Wigderson (NW) polynomial family that has proved to be very helpful over the past few years in arithmetic circuit complexity. Finally, we do a careful analysis of Shoup-Smolensky (1997) and Raz (2010) and compare their techniques to ours. We conclude that our result can potentially be used as a starting point, and techniques similar to Kayal et. al. (2016) can likely be used to strengthen our lower bound to Omega(N^2.5), for general depth four arithmetic circuits. However, unlike depth three circuits, proving a super-quadratic lower bound for depth four circuits remains a prevalent open problem for many years. Previous work like Shoup-Smolensky and Raz implied super-linear lower bounds. To the best of our knowledge, the previous best known lower bound for general depth four circuits is Omega(N^1.33).en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG28453en_US
dc.subjectArithmetic Circuitsen_US
dc.subjectNisan-Wigdersonen_US
dc.subjectProjected Shifted Partialsen_US
dc.subjectNisan-Wigderson Polynomialsen_US
dc.subjectConstant Depth Circuitsen_US
dc.subjectDepth Four Circuitsen_US
dc.subjectDimension of Projected Shifted Partials (DPSP)en_US
dc.subjectDepth Arithmetic Circuitsen_US
dc.subject.classificationComputer Scienceen_US
dc.titleAn Improved Lower Bound for Depth four Arithmetic Circuitsen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record