dc.contributor.advisor Saha, Chandan dc.contributor.author Hegde, Sumant dc.date.accessioned 2019-09-23T07:08:20Z dc.date.available 2019-09-23T07:08:20Z dc.date.submitted 2017 dc.identifier.uri http://etd.iisc.ac.in/handle/2005/4281 dc.description.abstract In this work we study the multi-r-ic formula model introduced by [KS15c] and improve upon en_US 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. dc.language.iso en_US en_US dc.relation.ispartofseries G28609; dc.rights I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part en_US of this thesis or dissertation dc.subject Multi-r-ic Circuits en_US dc.subject Arithmetic Circuits en_US dc.subject Shifted Partials Dimension (SPD) en_US dc.subject Multi-r-ic Depth Four Circuits en_US dc.subject Arithmetic Complexity Classes en_US dc.subject.classification Computer Science en_US dc.title An Improved Lower Bound for Multi-r-ic Depth Four Circuits as a Function of the Number of Input Variables en_US dc.type Thesis en_US dc.degree.name MSc Engg en_US dc.degree.level Masters en_US dc.degree.grantor Indian Institute of Science en_US dc.degree.discipline Engineering en_US
﻿