An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas - Kayal, Neeraj; Limaye, Nutan; Saha, Chandan; Srinivasan, Srikanth (Foundations of Computer Science (FOCS), 2014)
We show here a Nsqrt(d) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d3 in our case) with 0,1-coefficients such that any homogeneous depth four arithmetic formula computing such an f must have size at least Nsqrt(d).
Invited to Special Issue of SICOMP journal