Lower Bounds for Small Depth Arithmetic Circuits

Lower bounds for small depth

arithmetic circuits

Chandan Saha

Joint work with 

Neeraj Kayal

(MSRI)

           Nutan Limaye   (IITB)

                            Srikanth Srinivasan   (IITB)

Arithmetic Circuit: A model of computation

+

x

x

x

x

+

+

+

+

x

x

x

x

….

…..

x

1

x

2

x

n-1

x

n

f(x

1

, x

2

, …, x

n

)

--> multivariate polynomial

in 

x

1

, …, x

n

x

g

h

gh

+

g

h

g+h

Product gate

Sum gate

There are `field constants’ on the wires

Arithmetic Circuit: A model of computation

+

x

x

x

x

+

+

+

+

x

x

x

x

….

…..

x

1

x

2

x

n-1

x

n

f(x

1

, x

2

, …, x

n

)

Depth = 4

Arithmetic Circuit: A model of computation

+

x

x

x

x

+

+

+

+

x

x

x

x

….

…..

x

1

x

2

x

n-1

x

n

f(x

1

, x

2

, …, x

n

)

Size 

= no. of gates

and wires

The lower bound question

Is there an 

explicit

 family of 

n

-variate, 

poly(n)

 degree

polynomials

 {f

n

} 

that requires…

                   …super-polynomial in

 n 

circuit size ?

The lower bound question

Is there an 

explicit

 family of 

n

-variate, 

poly(n)

 degree

polynomials

 {f

n

} 

that requires…

                   …super-polynomial in

 n 

circuit size ?

Note :

       A 

random polynomial 

has super-

poly(n) 

circuit size

The Permanent – an explicit family

Perm

n 

=  ∑     ∏   x

i 

σ

(i)

σ

є

 S

n

i 

є

 [n]

The Permanent – an explicit family

•

Degree of Perm

n

 is low.

                                   i.e. bounded by 

poly(n)

Perm

n 

=  ∑     ∏   x

i 

σ

(i)

σ

є

 S

n

i 

є

 [n]

The Permanent – an explicit family

•

Degree of Perm

n

 is low.

•

Coefficient of any given monomial can be found efficiently.

                            …given a monomial, there’s a poly-time 

algorithm to

                               determine the coefficient 

of the monomial.

Perm

n 

=  ∑     ∏   x

i 

σ

(i)

σ

є

 S

n

i 

є

 [n]

The Permanent – an explicit family

•

Degree of Perm

n

 is low. 

•

Coefficient of any given monomial can be found efficiently.

These two

properties

characterize

explicitness

Perm

n 

=  ∑     ∏   x

i 

σ

(i)

σ

є

 S

n

i 

є

 [n]

The Permanent – an explicit family

•

Degree of Perm

n

 is low. 

•

Coefficient of any given monomial can be found efficiently.

Define class 

VNP

Perm

n 

=  ∑     ∏   x

i 

σ

(i)

σ

є

 S

n

i 

є

 [n]

The Permanent – an explicit family

•

Degree of Perm

n

 is low. 

•

Coefficient of any given monomial can be found efficiently.

Define class 

VNP

Perm

n 

=  ∑     ∏   x

i 

σ

(i)

σ

є

 S

n

i 

є

 [n]

Class

VP

:   Contains families of low degree polynomials 

{f

n

}

 that

can be computed by 

poly(n)

-size circuits.

The Permanent – an explicit family

•

Degree of Perm

n

 is low. 

•

Coefficient of any given monomial can be found efficiently.

Perm

n 

=  ∑     ∏   x

i 

σ

(i)

σ

є

 S

n

i 

є

 [n]

VP vs VNP

:  Does 

Perm

n

family require 

super-poly(n) 

size circuits?

A strategy for proving arithmetic circuit lower bound

Step 1:

       Depth reduction

Step 2:

       Lower bound for small depth circuits

A strategy for proving arithmetic circuit lower bound

Step 1:

Depth reduction

Step 2:

       Lower bound for small depth circuits

Notations and Terminologies

Notations:

       n

 = no. of variables in 

f

n

d

 = degree bound on f

n

 = 

n

O(1)

Homogeneous polynomial

:    A polynomial is homogeneous

if all its monomials have the same degree (say, 

d

).

Homogeneous circuits

:     A circuit is homogeneous if every

gate outputs/computes a homogeneous polynomial.

Multilinear polynomial

:   In every monomial, degree of

every variable is at most 1.

Reduction to depth ≈ log d

Valiant, Skyum, Berkowitz, Rackoff (1983). 

Homogeneous, degree 

d, 

f

n 

 computed by 

poly(n) 

circuit

         f

n

 computed by 

homogeneous

poly(n) 

circuit of depth 

O(log d)

arbitrary depth

≈ log d

poly(n)

poly(n)

Reduction to depth 4

Agrawal, Vinay (2008); Koiran (2010); Tavenas (2013).

          Homogeneous, degree 

d

,  

f

n 

 computed by 

poly(n)

 circuit

          f

n  

computed by 

homogeneous 

depth 4

 circuit of size 

n

O(√d)

≈ log d

4

n

O(√d)

poly(n)

Reduction to depth 4

Agrawal, Vinay (2008); Koiran (2010); Tavenas (2013).

          Homogeneous, degree 

d

,  

f

n 

 computed by 

poly(n)

 circuit

          f

n  

computed by 

homogeneous 

depth 4

 circuit of size 

n

O(√d)

≈ log d

4

n

O(√d)

poly(n)

… 

f

n 

can have 

n

O(d) 

monomials !

A depth 4 circuit

+

x

x

x

x

+

+

+

+

x

x

x

x

….

…..

x

1

x

2

x

n-1

x

n

∑

∏

∑

∏

A depth 4 circuit

+

x

x

x

x

+

+

+

+

x

x

x

x

….

…..

x

1

x

2

x

n-1

x

n

∑  ∏  Q

ij

i

j

sum of monomials

Q

ij

Reduction to depth 3

Gupta, Kamath, Kayal, Saptharishi (2013); Tavenas (2013).

          Homogeneous, degree 

d

,  

f

n 

 computed by 

poly(n)

 circuit

                        f

n  

computed by 

depth 3

 circuit of size 

n

O(√d)

3

n

O(√d)

n

O(√d)

4

Reduction to depth 3

Gupta, Kamath, Kayal, Saptharishi (2013); Tavenas (2013).

          Homogeneous, degree 

d

,  

f

n 

 computed by 

poly(n)

 circuit

                        f

n  

computed by 

depth 3

 circuit of size 

n

O(√d)

3

n

O(√d)

n

O(√d)

4

not homogeneous!

A depth 3 circuit

+

x

x

x

x

+

+

+

+

….

x

1

x

2

x

n-1

x

n

∑  ∏  l

ij

i

j

linear polynomial

l

ij

bottom fanin

Implication of the depth reductions

Let 

{f

n

} 

be an explicit family of polynomials.

if 

f

n

takes

n

ω

(√d)

size 

homogeneous

if 

f

n

takes

n

ω

(√d)

size

VP ≠ VNP

or

4

3

A strategy for proving arithmetic circuit lower bound

Step 1:

       Depth reduction

Step 2:

Lower bound for small depth circuits

Lower bound for homogeneous depth 4

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP

 (with 

deg f

n

 = d

) such that…

    …any homogeneous 

depth-4

 circuit computing 

f

n

 has size 

n

Ω

(√d)

size = 

n

Ω

(√d)

4

f

n

Lower bound for homogeneous depth 4

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP (with 

deg f

n

 = d

) such that…

    …any homogeneous 

depth-4

 circuit computing 

f

n

 has size 

n

Ω

(√d)

size = n

Ω

(√d)

4

f

n

f

n

 =

i

∑  ∏  Q

ij

… has size 

n

Ω

(√d)

j

sum of monomials

Lower bound for homogeneous depth 4

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP (with 

deg f

n

 = d

) such that…

    …any homogeneous 

depth-4

 circuit computing 

f

n

 has size 

n

Ω

(√d)

size = n

Ω

(√d)

4

f

n

…joint work with 

Kayal, Limaye , Srinivasan

Lower bound for homogeneous depth 4

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP (with 

deg f

n

 = d

) such that…

    …any homogeneous 

depth-4

 circuit computing 

f

n

 has size 

n

Ω

(√d)

size = n

Ω

(√d)

4

f

n

…the technique appears to be using 

homogeneity

 crucially

Lower bound for depth 3

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP

 (with 

deg f

n

 = d

) such that…

any 

depth-3

 circuit 

(bottom fanin ≤

√d

)

 computing 

f

n

 has size 

n

Ω

(√d)

size = 

n

Ω

(√d)

3

f

n

Lower bound for depth 3

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP (with 

deg f

n

 = d

) such that…

any 

depth-3

 circuit 

(bottom fanin ≤

√d

)

 computing 

f

n

 has size 

n

Ω

(√d)

size = n

Ω

(√d)

3

f

n

needn’t be homogeneous

Lower bound for depth 3

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP (with 

deg f

n

 = d

) such that…

any 

depth-3

 circuit 

(bottom fanin ≤

√d

)

 computing 

f

n

 has size 

n

Ω

(√d)

size = n

Ω

(√d)

3

f

n

Note:

      Even for bottom fanin

                ≤ 

√d, depth-3 

circuits

n

ω

(√d)

           VP ≠ VNP 

Lower bound for depth 3

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP (with 

deg f

n

 = d

) such that…

any 

depth-3

 circuit 

(bottom fanin ≤

t

)

 computing 

f

n

 has size 

n

Ω

(d/t)

size = 

n

Ω

(d/t)

3

f

n

…joint work with 

Kayal

Lower bound for depth 3

Theorem: 

There is a family of homogeneous polynomials 

{f

n

}

 in

VNP (with 

deg f

n

 = d

) such that…

any 

depth-3

 circuit 

(bottom fanin ≤

t

)

 computing 

f

n

 has size 

n

Ω

(d/t)

size = n

Ω

(d/t)

3

f

n

… answers a question by 

Shpilka & Wigderson (1999)

Proof ideas

Homogeneous depth-4 lower bound

Complexity measure

•

A measure is a function

μ

: F[x

1

, …, x

n

] -> R.

•

We wish to find a measure 

μ

such that

1.

If 

C

 is a circuit (say, a depth 4 circuit) then

μ

(C) ≤ s. “small quantity” 

, where 

s = size(C)

2.

For an “explicit” polynomial 

f

n

 ,

μ

(f

n

) ≥ “large quantity”

•

Implication:

 If 

C = f

n 

then 

s ≥

“large quantity”

“small quantity”



Upper bound



Lower bound

Some complexity measures

Measure                                        Model

Partial derivatives (

Nisan & Wigderson

)      homogeneous depth-3 circuits

Evaluation dimension (

Raz

)                            multilinear formulas

Hessian (

Mignon & Ressayre

)                        determinantal complexity permanent

Jacobian (

Agrawal et. al.

)                                occur-k, depth-4 circuits

Incomplete list ?

Some complexity measures

Measure                                        Model

Partial derivatives 

(

Nisan & Wigderson

)      homogeneous depth-3 circuits

Evaluation dimension (

Raz

)                            multilinear formulas

Hessian (

Mignon & Ressayre

)                        determinantal complexity permanent

Jacobian (

Agrawal et. al.

)                                occur-k, depth-4 circuits

Shifted partials 

(

Kayal; Gupta et. al.

)  

homog. depth-4 with low bottom fanin

Projected shifted partials 

homogeneous depth-4 circuits;

depth-3 circuits

(with low bottom fanin)

Space of Partial Derivatives

Notations:

∂

=k 

f :    

Set of all 

k

th 

order derivatives of 

f(x

1

, …, x

n

)

< S > 

:  The vector space spanned by F-linear combinations of

             polynomials in S

Definition:          

PD

k

(f)  =  dim(< ∂

=k 

f >)

Sub-additive property:          

PD

k

(f

1

 +  f

2

)  ≤  PD

k

(f

1

) + PD

k

(f

2

)

Space of Shifted Partials

Notation: 

x

=ℓ

 = 

Set of all monomials of degree

 ℓ

Definition:      

SP

k,ℓ

(f) :=  dim (< x

=ℓ

 . ∂

=k 

f >)

Sub-additivity:

SP

k,ℓ 

(f

1

 + f

2

)  ≤  SP

k,ℓ 

(f

1

)  +  SP

k,ℓ 

(f

2

)

Space of Shifted Partials

Notation: 

x

=ℓ

 = 

Set of all monomials of degree

 ℓ

Definition:      

SP

k,ℓ

(f) :=  dim (< x

=ℓ

 . ∂

=k 

f >)

Sub-additivity:

SP

k,ℓ 

(f

1

 + f

2

)  ≤  SP

k,ℓ 

(f

1

)  +  SP

k,ℓ 

(f

2

)

Why do we expect 

SP(C)

to be small ?

Shifted partials – the intuition

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Q

ij

= Sum of monomials

Shifted partials – the intuition

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Observation:

∂

=k

 Q

i1

…Q

im

has “many roots” if 

k <<

m << n

… any common root of 

Q

i1

…Q

im

 is also a common root of 

∂

=k

 Q

i1

…Q

im

Shifted partials – the intuition

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Observation:

  Dimension of the variety of 

∂

=k

 Q

i1

…Q

im

is

                          large if 

k <<

m << n

Shifted partials – the intuition

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Observation:

  Dimension of the variety of 

∂

=k

 Q

i1

…Q

im

is

                          large if 

k <<

m << n

[Hilbert’s] Theorem 

(informal): 

If dimension of the variety

of 

{g}

 is large then 

dim (< x

=ℓ

 . {g} >) 

is small.

Shifted partials – the intuition

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Observation:

  Dimension of the variety of 

∂

=k

 Q

i1

…Q

im

is

                          large if 

k <<

m << n

[Hilbert’s] Theorem 

(informal): 

If dimension of the variety

of 

{g}

 is large then 

dim (< x

=ℓ

 . {g} >) 

is small.

… so we expect 

SP

k,ℓ

(Q

i1

…Q

im

) 

to be a `small quantity’

Shifted partials – the intuition

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Observation:

  Dimension of the variety of 

∂

=k

 Q

i1

…Q

im

is

                          large if 

k <<

m << n

[Hilbert’s] Theorem 

(informal): 

If dimension of the variety

of 

{g}

 is large then 

dim (< x

=ℓ

 . {g} >) 

is small.

… by subadditivity,  

SP

k,ℓ

(C) ≤

s . `small quantity’

Depth-4 with low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Q

ij

= Sum of monomials of degree 

≤ t

(w.l.o.g  

m ≤ 2d/t 

)

Depth-4 with low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

degree 

≤ k.t

Depth-4 with low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

at most  

(   ) 

terms

m

k

Depth-4 with low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

u . ∂

=k

 Q

i1

…Q

im

 =

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

X

degree = 

ℓ

degree 

≤ ℓ + k.t

Depth-4 with low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

u . ∂

=k

 Q

i1

…Q

im

 =

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

X

n + ℓ + kt

n

m

k

SP

k,ℓ

(Q

i1

…Q

im

)  ≤  (              ) . (    )

Depth-4 with low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

u . ∂

=k

 Q

i1

…Q

im

 =

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

X

n + ℓ + kt

n

m

k

SP

k,ℓ

(C)  ≤ s. (              ) . (    )



Upper bound

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

(homog. depth 4)

Q

ij

= Sum of monomials    (NO degree restriction)

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Idea:  

Reduce to the case of low bottom degree using

•

Random restriction

•

Multilinear projection

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Random restriction:  

Set every variable to zero independently at

                                      random with a certain probability.

…denoted naturally by a map 

σ

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Random restriction:  

Set every variable to zero independently at

                                      random with a certain probability.

…denoted naturally by a map 

σ

σ

(C)  =  

σ

(Q

11

) 

σ

(Q

12

)…

σ

(Q

1m

)   + … +   

σ

(Q

s1

) 

σ

(Q

s2

)…

σ

(Q

sm

)

Obs:   

If a monomial 

u

 has many variables (

high support

)

           then 

σ

(u) = 0 

w.h.p

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Random restriction:  

Set every variable to zero independently at

                                      random with a certain probability.

…denoted naturally by a map 

σ

σ

(C)  =  

σ

(Q

11

) 

σ

(Q

12

)…

σ

(Q

1m

)   + … +   

σ

(Q

s1

) 

σ

(Q

s2

)…

σ

(Q

sm

)

w.l.o.g

σ

(Q

ij

)  

=  sum of ‘

low support

’ monomials

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Random restriction:  

Set every variable to zero independently at

                                      random with a certain probability.

Homogeneous depth 4        



       homogenous depth 4 

with low bottom

                                                                                        support

… w.l.o.g assume that 

C

 has low bottom support

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Projection map:  

π

 (g) 

=

sum of the multilinear monomials in 

g

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Projection map:  

π

 (g) 

=

sum of the multilinear monomials in 

g

Observation:

π

 (

sum of ‘

low support

’ monomials

) 

=

sum of ‘

low degree

’ monomials 

Reduction to low bottom degree

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Projection map:  

π

 (g) 

=

sum of the multilinear monomials in 

g

Observation:

π

 (Q

ij

 ) 

=

sum of ‘

low degree

’ monomials

Projected Shifted Partials

PSP

k,ℓ

 (f) := dim (

π

 (

x

=ℓ

. ∂

=k 

f) )

(obeys subadditivity)

Projected Shifted Partials

PSP

k,ℓ

 (f) := dim (

π

 (

x

=ℓ

. ∂

=k 

f) )

(obeys subadditivity)

multilinear shifts only!

Projected Shifted Partials

PSP

k,ℓ

 (f) := dim (

π

 (

x

=ℓ

. ∂

=k 

f) )

(obeys subadditivity)

multilinear derivatives!

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

support of every monomial bounded by 

t

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Q

ij

   =   Q’

ij

   + 

Every variable in every monomial

has degree 2 or less

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Q

ij

   =   Q’

ij

   + 

Every monomial has a variable

with degree 3 or more

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Q

ij

   =   Q’

ij

   + 

Q

i1

Q

i2

…Q

im

      =   Q’

i1

Q’

i2

…Q’

im

   +

Every monomial has a variable

with degree 3 or more

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Q

ij

   =   Q’

ij

   + 

Q

i1

Q

i2

…Q

im

      =   Q’

i1

Q’

i2

…Q’

im

   +

PSP

k,ℓ

 (Q

i1

Q

i2

…Q

im

)  ≤  

PSP

k,ℓ

(Q’

i1

Q’

i2

…Q’

im

) + 

PSP

k,ℓ

(                      )

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Q

ij

   =   Q’

ij

   + 

Q

i1

Q

i2

…Q

im

      =   Q’

i1

Q’

i2

…Q’

im

   +

PSP

k,ℓ

 (Q

i1

Q

i2

…Q

im

)  ≤  

PSP

k,ℓ

(Q’

i1

Q’

i2

…Q’

im

) + 

PSP

k,ℓ

(                      )

0

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Q

ij

   =   Q’

ij

   + 

Q

i1

Q

i2

…Q

im

      =   Q’

i1

Q’

i2

…Q’

im

   +

PSP

k,ℓ

 (Q

i1

Q

i2

…Q

im

)  ≤  

PSP

k,ℓ

(Q’

i1

Q’

i2

…Q’

im

) + 

PSP

k,ℓ

(                      )

0

degree ≤ 

2t

Depth-4 with low bottom support

C  =  Q

11

Q

12

…Q

1m

 + … + Q

s1

Q

s2

…Q

sm

Q

ij

   =   Q’

ij

   + 

Q

i1

Q

i2

…Q

im

      =   Q’

i1

Q’

i2

…Q’

im

   +

PSP

k,ℓ

 (Q

i1

Q

i2

…Q

im

)  ≤  

PSP

k,ℓ

(Q’

i1

Q’

i2

…Q’

im

)

Abusing notation:    

Call  

Q’

ij

 as  

Q

ij

Depth-4 with low bottom support

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

degree 

≤ 2kt

Depth-4 with low bottom support

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

u . ∂

=k

 Q

i1

…Q

im

 =

u.

Q

i k+1

 … Q

im

   + u.               Q

i1

 Q

i k+2

 … Q

im

 +

X

degree = 

ℓ

degree 

≤ 2kt

Depth-4 with low bottom support

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

π

(u.∂

=k

 Q

i1

…Q

im

) =

π

( 

Q

i k+1

 … Q

im

) + 

π

(            Q

i1

 Q

i k+2

 … Q

im

) +

X

multilinear,   degree 

≤ ℓ + 2k.t

Depth-4 with low bottom support

∂

=k

 Q

i1

…Q

im

 =     

Q

i1 

Q

i2

…Q 

ik

 …Q

im

    +    Q

i1 

Q

i2

…Q 

ik

Q 

i k+1

…Q

im

 + …

X

.

.

.

.

.

.

=                 

Q

i k+1

 … Q

im

   +                Q

i1

 Q

i k+2

 … Q

im

 + …

π

(u.∂

=k

 Q

i1

…Q

im

) =

π

( 

Q

i k+1

 … Q

im

) + 

π

(            Q

i1

 Q

i k+2

 … Q

im

) +

X



Upper bound

ℓ + 2kt

n

m

k

SP

k,ℓ

(C)  ≤ s. (          ) . (    )

How large can 

PSP(f)

 be?

•

Trivially,

PSP

k,ℓ

 (f) ≤ min { 

(  ).(  ) , (        ) 

}

n

k

n

ℓ

n

 ℓ + d - k

How large can 

PSP(f)

 be?

•

Trivially,

PSP

k,ℓ

 (f) ≤ min { 

(  ).(  ) , (        ) 

}

n

k

n

ℓ

n

 ℓ + d - k

•

Size of the set { 

x

=ℓ

. ∂

=k 

f 

}  ≤ 

(  ).(  )

•

Number of monomials in any polynomial in  

π

 (

x

=ℓ

. ∂

=k 

f)  ≤ 

(          )

n

k

n

ℓ

n

 ℓ + d - k

Let 

f

 be a multilinear  polynomial

How large can 

PSP(f)

 be?

•

Trivially,

PSP

k,ℓ

 (f) ≤ min {

(  ).(  ) , (       )

}

•

Best lower bound for 

s

s ≥

n

k

n

ℓ

n

ℓ + d - k

min

 {(  ).(  ) , (       )}

(

)

.

(

)

m

k

n

ℓ + 2kt

n

k

n

ℓ

n

ℓ + d - k

=  

n

Ω

(d/t)

After setting 

k 

and 

ℓ

appropriately

How large can 

PSP(f)

 be?

•

Trivially,

PSP

k,ℓ

 (f) ≤ min {

(  ).(  ) , (       )

}

•

Best lower bound for 

s

s ≥

•

There’s an explicit 

f

 such that 

PSP

k,ℓ

 (f) 

is close to the

trivial upper bound.         



(lower bound)

n

k

n

ℓ

n

ℓ + d - k

min

 {(  ).(  ) , (       )}

(

)

.

(

)

m

k

n

ℓ + 2kt

n

k

n

ℓ

n

ℓ + d - k

=  n

Ω

(d/t)

Depth-3 lower bound

Trading depth for homogeneity

Idea:             

Depth-3 

with low bottom fanin

Homogeneous 

depth-4

 with low bottom support

Size

 = s

Bottom fanin 

= t

3

f

n

4  (homogeneous)

f

n

Size

 = s . 

2

O(√d)

Bottom support 

= t

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

C =  

α

1

.(1 + l

11

)(1 + l

12

)…(1 + l

1m

)  + …. +  

α

s

.(1 + l

s1

)(1 + l

s2

)…(1 + l

sm

)

linear forms

field constants

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

C =  (1 + l

11

)(1 + l

12

)…(1 + l

1m

)  + …. +  (1 + l

s1

)(1 + l

s2

)…(1 + l

sm

)

Notation:     

[g]

d

= 

d-th

 homogeneous part of 

g

Easy observation: 

If 

C = f , 

which is homogeneous 

deg d

polynomial, then 

[C]

d

 = f.

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

C =  (1 + l

11

)(1 + l

12

)…(1 + l

1m

)  + …. +  (1 + l

s1

)(1 + l

s2

)…(1 + l

sm

)

[C]

d

 = [(1 + l

11

)(1 + l

12

)…(1 + l

1m

)]

d

  +….+  [(1 + l

s1

)(1 + l

s2

)…(1 + l

sm

)]

d

idea:

  transform these to homogeneous 

depth-4

Newton’s identities

•

E

d 

(y

1

, y

2

, …, y

m

) :=   ∑        ∏   y

j

•

P

r

 (y

1

, y

2

, …, y

m

) :=   ∑   y

j

r

S in 2

[m]

|S| = d

j in S

(elementary symmetric polynomial of degree 

d

)

j in [m]

(power symmetric polynomial of degree 

r

)

Newton’s identities

•

E

d 

(y

1

, y

2

, …, y

m

) :=   ∑        ∏   y

j

•

P

r

 (y

1

, y

2

, …, y

m

) :=   ∑   y

j

r

S in 2

[m]

|S| = d

j in S

j in [m]

Lemma:     

E

d 

(

y

)  =      ∑          

β

a

     ∏   P

r   

(

y

)

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

a

r

e.g.

2y

1

y

2

 =  (y

1

 + y

2

)

2

 – y

1

2

 – y

2

2

 =   P

1

2

 – P

2

field constant

Newton’s identities

•

E

d 

(y

1

, y

2

, …, y

m

) :=   ∑        ∏   y

j

•

P

r

 (y

1

, y

2

, …, y

m

) :=   ∑   y

j

r

S in 2

[m]

|S| = d

j in S

j in [m]

Lemma:  

E

d 

(

y

)  =      ∑          

β

a

     ∏   P

r   

(

y

)

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

a

r

Hardy-Ramanujan estimate:

The number of 

a

 = (a

1

, …, a

d

)

 such that 

∑ r.a

r

 = d    

is

2

O(√d)

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

[(1 + l

i1

)(1 + l

i2

)…(1 + l

im

)]

d

   =   E

d 

( l

i1

 , … , l

im 

)

=   

∑          

β

a

     ∏   P

r   

( l

i1

 , … , l

im 

)

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

a

r

2

O(√d)

summands

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

[(1 + l

i1

)(1 + l

i2

)…(1 + l

im

)]

d

   =   E

d 

( l

i1

 , … , l

im 

)

=   

∑          

β

a

     ∏   P

r   

( l

i1

 , … , l

im 

)

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

a

r

2

O(√d)

summands

Suppose every 

l

ij 

 has at most 

t

 variables, then…

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

[(1 + l

i1

)(1 + l

i2

)…(1 + l

im

)]

d

   =   E

d 

( l

i1

 , … , l

im 

)

=   

∑          

β

a

     ∏   P

r   

( l

i1

 , … , l

im 

)

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

a

r

=   

∑          

β

a

     ∏   Q

i,

a

,r

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

every monomial has

support 

≤ t

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

[(1 + l

i1

)(1 + l

i2

)…(1 + l

im

)]

d

   =   E

d 

( l

i1

 , … , l

im 

)

=   

∑          

β

a

     ∏   P

r   

( l

i1

 , … , l

im 

)

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

a

r

=   

∑          

β

a

     ∏   Q

i,

a

,r

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

[C]

d

   =  ∑

∑          

β

a

     ∏   Q

i,

a

,r

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

i in [s]

Depth-3 to Depth-4

•

Implicit in 

Shpilka & Wigderson ; Hrubes & Yehudayoff  (2011)

[(1 + l

i1

)(1 + l

i2

)…(1 + l

im

)]

d

   =   E

d 

( l

i1

 , … , l

im 

)

=   

∑          

β

a

     ∏   P

r   

( l

i1

 , … , l

im 

)

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

a

r

=   

∑          

β

a

     ∏   Q

i,

a

,r

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

[C]

d

   =  ∑

∑          

β

a

     ∏   Q

i,

a

,r

a

 = (a

1

, … , a

d

)

∑ r . a

r

 = d

r in [d]

i in [s]

Homogeneous 

depth-4

 with low

bottom support and size 

s.

2

Ω

(√d)

An explicit family with high 

PSP

k,ℓ

An explicit family of polynomials

•

Nisan-Wigderson family of polynomials:

NW

r

  :=    ∑      ∏  

x

i, h(i)

d

2

 h(z) in F   [z],

deg(h) ≤ r

i in [d]

identifying  the elements of 

F

   with 

{1,2, … , d

2

}

d

2

An explicit family of polynomials

•

Nisan-Wigderson family of polynomials:

NW

r

  :=    ∑      ∏  

x

i, h(i)

d

2

h(z) in F   [z],

deg(h) ≤ r

i in [d]

`Disjointness’ property:    

Two monomials can share at most 

r

≈ d/3

 variables.

=                   +                  + … 

d

r

r

d

2(r+1)

 monomials

Projected Shifted Partials of 

NW

r

•

The set 

π

 (

x

=ℓ

. ∂

=k 

NW

r

) 

has

(  ).(  ) 

elements.

•

Every polynomial in 

π

 (

x

=ℓ

. ∂

=k 

NW

r

)

 is multilinear & homogeneous of

degree

 (ℓ + d – k)

.

n

k

n

ℓ

Projected Shifted Partials of 

NW

r

•

The set 

π

 (

x

=ℓ

. ∂

=k 

NW

r

) 

has

(  ).(  ) 

elements.

•

Every polynomial in 

π

 (

x

=ℓ

. ∂

=k 

NW

r

)

 is multilinear & homogeneous of

degree

 (ℓ + d – k)

.

•

PSP

k,ℓ

 (NW

r

)  =   rank (M)

n

k

n

ℓ

M  :=

(  ).(  )

rows

π

 (

x

=ℓ

. ∂

=k 

NW

r

)

(0/1)-

matrix of coefficients

n

ℓ + d - k

(        )

columns

n

k

n

ℓ

Projected Shifted Partials of 

NW

r

•

Because of the `

disjointness property

’ of 

NW

r

, the columns of 

M

 are

almost orthogonal.

•

Hence, 

B := M

T 

M 

 is diagonally dominant.

•

Observe,   

rank (M)  ≥   rank (B) .

Projected Shifted Partials of 

NW

r

•

Because of the `

disjointness property

’ of 

NW

r

, the columns of 

M

 are

almost orthogonal.

•

Hence, 

B := M

T 

M 

 is diagonally dominant.

•

Observe,   

rank (M)  ≥   rank (B) .

Alon’s rank bound (for diagonally dominant matrix):

 If 

B

 is a real symmetric matrix then

rank (B)  ≥

Tr (B)

2

Tr (B

2

)

Projected Shifted Partials of 

NW

r

[Main lemma]:   

Using Alon’s bound and settings 

r 

,

 k 

and 

ℓ

appropriately,

PSP

k,ℓ

 (NW

r

) ≥  

η

. 

min {(  ).(  ) , (       )}

n

k

n

ℓ

n

ℓ + d - k

small factor

An explicit family in VP

•

[Kumar-Saraf (2014)] : 

Showed the same lower bound using

the 

Iterated Matrix multiplication 

polynomial, which is in 

VP

An explicit family in VP

•

[Kumar-Saraf (2014)] : 

Showed the same lower bound using

the Iterated Matrix multiplication polynomial, which is in 

VP

VNP

Circuits (VP)

ABPs

Formulas

Depth-4

exponential separation

An explicit family in VP

•

[Kumar-Saraf (2014)] : 

Showed the same lower bound using

the Iterated Matrix multiplication polynomial, which is in 

VP

VNP

Circuits (VP)

ABPs

Formulas

Open:

 separation ?

…known in the multilinear setting

[Dvir, Malod, Perifel, Yehudayoff (2012)]

An explicit family in VP

•

[Kumar-Saraf (2014)] : 

Showed the same lower bound using

the Iterated Matrix multiplication polynomial, which is in 

VP

VNP

Circuits (VP)

ABPs

Formulas

Open:

 separation ?

…improve 

n

Ω

(√d)

to 

n

ω

(√d)

Some other open questions

1.

Prove a 

n

Ω

(√d)

 lower bound for general 

depth-3

 circuits 

(i.e.

without the low bottom fanin restriction)

.

Some other open questions

1.

Prove a 

n

Ω

(√d)

 lower bound for general 

depth-3

 circuits.

2.

Prove a 

n

Ω

(√d)

 lower bound for homogeneous 

depth-5 

circuits.

[open problem in Nisan & Wigderson (1996)]

(2)  



 (1)

Some other open questions

1.

Prove a 

n

Ω

(√d)

 lower bound for general 

depth-3

 circuits.

2.

Prove a 

n

Ω

(√d)

 lower bound for homogeneous 

depth-5 

circuits.

3.

Prove a 

n

Ω

(d)

 lower bound for multilinear 

depth-3

 circuits.

(current best is 

2

Ω

(d)

)

…interestingly, one can get this using PSP measure

Some other open questions

1.

Prove a 

n

Ω

(√d)

 lower bound for general 

depth-3

 circuits.

2.

Prove a 

n

Ω

(√d)

 lower bound for homogeneous 

depth-5 

circuits.

3.

Prove a 

n

Ω

(d)

 lower bound for multilinear 

depth-3

 circuits.

4.

A separation between homogeneous formulas and

homogeneous 

depth-4

 formulas.

Some other open questions

1.

Prove a 

n

Ω

(√d)

 lower bound for general 

depth-3

 circuits.

2.

Prove a 

n

Ω

(√d)

 lower bound for homogeneous 

depth-5 

circuits.

3.

Prove a 

n

Ω

(d)

 lower bound for multilinear 

depth-3

 circuits.

4.

A separation between homogeneous formulas and

homogeneous 

depth-4

 formulas.

5.

A separation between homogeneous formulas and multilinear

homogeneous formulas.

…exhibiting the power of non-multilinearity

Some other open questions

1.

Prove a 

n

Ω

(√d)

 lower bound for general 

depth-3

 circuits.

2.

Prove a 

n

Ω

(√d)

 lower bound for homogeneous 

depth-5 

circuits.

3.

Prove a 

n

Ω

(d)

 lower bound for multilinear 

depth-3

 circuits.

4.

A separation between homogeneous formulas and

homogeneous 

depth-4

 formulas.

5.

A separation between homogeneous formulas and multilinear

homogeneous formulas.

Thanks!