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

  • Sumant Hegde Indian Institute of Science
  • Chandan Saha Indian Institute of Science
Keywords: Arithmetic circuits, Multi-r-ic formulas, Lower bounds, Shifted Partial Derivatives, Nisan-Wigderson polynomial


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.

Author Biographies

Sumant Hegde, Indian Institute of Science
M.Sc. Student, Department of Computer Science and Automation
Chandan Saha, Indian Institute of Science
Assistant Professor, Department of Computer Science and Automation