Improved Lower Bound for Multi-r-ic Depth Four Circuits as a Function of the Number of Input Variables

Abstract

An arithmetic circuit (respectively, formula) is a rooted graph (respectively, tree) whose nodes are addition or multiplication gates and input variables/nodes. It computes a polynomial in a natural way. The formal degree of an addition (respectively, multiplication) gate with respect to a variable x is defined as the maximum (respectively, sum) of the formal degrees of its children, with respect to x. The formal degree of an input node with respect to x is 1 if the node is labelled with x, and 0 otherwise.
In a multi-r-ic formula, the formal degree of every gate with respect to every variable is at most r. Multi-r-ic formulas make an intermediate model between multilinear formulas (the r=1 case), for which lower bounds are relatively well-understood, and general formulas (the unbounded-r case), which are conjectured to have superpolynomial size lower bound.

On depth four multi-r-ic formulas/circuits computing IMM_{n,d} -- the product of d symbolic matrices of dimension n each, Kayal, Saha and Tavenas (2016) showed a lower bound of (N/dr^2)^{Omega(sqrt{d/r})} (where N = n^2.d, the total number of underlying variables). As a function of N and r, the lower bound is at most 2^{Omega({sqrt{N/r^3}})} when d=Theta(N/r^2), and so for the bound to remain superpolynomial (as a function of N), r can be at most N^{1/3}. Our work proves a superpolynomial lower bound (as a function of N) on the same model (but computing a VNP-polynomial), for r as high as (N log N)^{0.9}. It also yields a better lower bound than that of Kayal et. al. (2016), when viewed as a function of N and r.