@inproceedings{kayal2014a,
author = {Kayal, Neeraj and Saha, Chandan and Saptharishi, Ramprasad},
title = {A super-polynomial lower bound for regular arithmetic formulas.},
booktitle = {Symposium on Theory of Computing (STOC)},
year = {2014},
month = {June},
abstract = {We consider arithmetic formulas consisting of alternating layers of addition and multiplication gates such that the fanin of all the gates in any fixed layer is the same. Such a formula  which additionally has the property that its formal/syntactic degree is at most twice the (total) degree of its output polynomial, we refer to as a regular formula. As usual, we allow arbitrary constants from the underlying field F on the incoming edges to a + gate so that a + gate can in fact compute an arbitrary F-linear combination of its inputs. We show that there is an (n2 + 1)-variate polynomial of degree 2n in VNP such that any regular formula computing it must be of size at least n (log n).},
publisher = {ACM - Association for Computing Machinery},
url = {http://approjects.co.za/?big=en-us/research/publication/a-super-polynomial-lower-bound-for-regular-arithmetic-formulas/},
edition = {Symposium on Theory of Computing (STOC)},
}