| dc.description.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. | en_US |
