A super-polynomial lower bound for regular arithmetic formulas

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 ( n 2 + 1)-variate polynomial of degree 2 n in VNP such that any regular formula computing it must be of size at least n Ω(log n ) . Along the way, we examine depth four (ΣΠΣΠ) regular formulas wherein all multiplication gates in the layer adjacent to the inputs have fanin a and all multiplication gates in the layer adjacent to the output node have fanin b . We refer to such formulas as ΣΠ [ b ] ΣΠ [ a ] -formulas. We show that there exists an n 2 -variate polynomial of degree n in VNP such that any ΣΠ [ O (√ n )] ΣΠ [√ n ] -formula computing it must have top fan-in at least 2 Ω(√ n ·log n ) . In comparison, Tavenas [Tav13] has recently shown that every n O (1) -variate polynomial of degree n in VP admits a ΣΠ [ O (√ n )] ΣΠ [√ n ] -formula of top fan-in 2 O (√ n ·log n ) . This means that any further asymptotic improvement in our lower bound for such formulas (to say 2 ω (√ n log n ) ) will imply that VP is different from VNP.

Authors

• Neeraj Kayal
• Chandan Saha 0001
• Ramprasad Saptharishi

Keywords

• VNP
• VP
• arithmetic circuits
• depth-4 circuits
• lower bounds