@inproceedings{kayal2014an,
author = {Kayal, Neeraj and Limaye, Nutan and Saha, Chandan and Srinivasan, Srikanth},
title = {An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas},
booktitle = {Foundations of Computer Science (FOCS)},
year = {2014},
month = {October},
abstract = {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).},
publisher = {IEEE - Institute of Electrical and Electronics Engineers},
url = {http://approjects.co.za/?big=en-us/research/publication/an-exponential-lower-bound-for-homogeneous-depth-four-arithmetic-formulas/},
edition = {Foundations of Computer Science (FOCS)},
note = {Invited to Special Issue of SICOMP journal},
}