Paper Info
Title
Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits.
Abstract
In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree n in n(2) variables such that any homogeneous depth 4 arithmetic circuit computing it must have size n(Omega(log log n)). Our results extend the works of Nisan-Wigderson [13] (which showed superpolynomial lower bounds for homogeneous depth 3 circuits), Gupta-Kamath-Kayal-Saptharishi and Kayal-Saha-Saptharishi [4, 7] (which showed superpolynomial lower bounds for homogeneous depth 4 circuits with bounded bottom fan-in), Kumar-Saraf [9] (which showed superpolynomial lower bounds for homogeneous depth 4 circuits with bounded top fan-in) and Raz-Yehudayoff and Fournier-Limaye-Malod-Srinivasan [3,14] (which showed superpolynomial lower bounds for multilinear depth 4 circuits). Several of these results in fact showed exponential lower bounds. The main ingredient in our proof is a new complexity measure of bounded support shifted partial derivatives. This measure allows us to prove exponential lower bounds for homogeneous depth 4 circuits where all the monomials computed at the bottom layer have bounded support (but possibly unbounded degree/fan-in), strengthening the results of Gupta et al and Kayal et al [4, 7]. This new lower bound combined with a careful "random restriction" procedure (that transforms general depth 4 homogeneous circuits to depth 4 circuits with bounded support) gives us our final result.
Year
Venue
Field
2014
Lecture Notes in Computer Science
Discrete mathematics,Arithmetic circuits,Combinatorics,Polynomial,Homogeneous,Partial derivative,Information complexity,Mathematics
DocType
Volume
ISSN
Conference
8572
0302-9743
Citations 
PageRank 
References 
10
0.55
8
Authors
2
Name
Order
Citations
PageRank
Mrinal Kumar 00011649.94
Shubhangi Saraf226324.55