A super-polynomial lower bound for regular arithmetic formulas

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).