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

Abstract

In this work we study the multi-r-ic formula model introduced by [KS15c] and improve upon the lower bound for multi-r-ic depth four circuits given in [KST16b], when viewed as a function of the number of input variables N. The improvement leads to superpolynomial lower bounds for values of r signi cantly higher than what is known from prior works. A (syntactically) multi-r-ic formula is an arithmetic formula in which the formal degree with respect to every variable is at most r at every gate. The formal degree of an input gate with respect to a variable x is de ned to be 1 if the gate is labelled with x and 0 if it is labelled with a eld element or a di erent variable. The formal degree of a sum (respectively, product) gate with respect to x is de ned as the maximum (respectively, sum) of the formal degrees of its children with respect to x. Naturally, a multi-r-ic formula computes a polynomial with individual degree of every variable bounded by r. Multi-r-ic formulas are a natural extension of the relatively well-studied multilinear formulas [Raz09, RY09]. In this work, we focus on multi-r-ic formulas that compute multilinear polynomials. They are interesting because they allow the formal degree of the root node of the formula to be as high as r times the number of underlying variables. This gives extra room for `clever' cancellations of the high degree components inside the formula thereby making this type of formulas harder to analyze (as formula homogenization is not known to be doable without blowing up the size superpolynomially unless degree is very small [Raz10]). Most lower bound proofs in the literature operate under the restriction of low formal degree or multilinearity [Raz09, RY09, KSS14, KLSS]. In this light, multi-r-ic formulas computing multilinear polynomials form a reasonable intermediate model to study in order to gain some insight on how to deal with high formal degree in general formulas. Another motivation for understanding the high formal degree case better (even at depth three) comes from the depth reduction result in [GKKS14]. With the aim of making progress on multi-r-ic formula lower bound, [KST16b] gave a ( N d r2 ) ( p d=r) lower bound for multi-r-ic depth four formulas computing the N-variate Iterated iii

Matrix Multiplication (IMM) polynomial of degree d. As a function of N, the lower bound is at most 2 ( p N=r3) when d = (N=r2). In this thesis, our focus is on getting multi-r-ic depth four formulas with larger r into the arena of models that provenly admit a superpolynomial lower bound. In [KST16b], r can be at most N1=3 for the bound to remain superpolynomial. Our result (stated below) gives a superpolynomial lower bound for multi-r-ic depth four formulas where r can be as high as (N logN)0:9. Theorem. Let N; d; r be positive integers such that 0:51 N d 0:9 N and r (N logN)0:9. Then there is an explicit N-variate degree-d multilinear polynomial in VNP such that any multi-r-ic depth four circuit computing it has size 2

p N logN r

. The theorem yields a better lower bound than that of [KST16b], when viewed as a function of N. Also, the bound matches the best known lower bound (as a function of N) for multilinear (r = 1) depth four circuits [RY09] which is 2 ( p N logN). The improvement is obtained by analyzing the shifted partials dimension (SPD) of an N- variate polynomial in VNP (as opposed to a VP polynomial in [KST16b]) of high degree range of (N), and comparing it with the SPD of a depth four multi-r-ic circuit. In [KST16b] a variant of shifted partials, called shifted skewed partials, is critically used to analyze the IMM polynomial (which is in VP) and obtain a lower bound as a function of N and d (particularly for low d). We observe that SPD (without `skew') is still e ective for the Nisan-Wigderson polynomial (which is in VNP), and yields a better lower bound as a function of only N when degree d is naturally chosen to be high. Our analysis gives a better range for r and a better lower bound in the high degree regime, not only for depth four multi-r-ic circuits but also for the weaker models: multi-r-ic depth three circuits and multi-r-ic depth four circuits with low bottom support. These (weaker) models are instrumental in gaining insight about general depth four multi-r-ic circuits, both in [KST16b] and our work.