A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

(1)

A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

Nutan Limaye

Compuer Science and Engineering Department, Indian Institute of Technology, Bombay, (IITB) India.

Joint work with

Suryajith Chillara, Christian Engels, Srikanth Srinivasan.

IIT Bombay, India.

Seminar 18391 – Algebraic Methods in Computational Complexity Dagstuhl, September 2018.

(2)

More Resources

More power?

(3)

More Resources

More power?

(4)

More Resources More power?

(5)

Power of resources

Turing machines

With more time, can Turing machines compute more languages? With more space, can Turing machines compute more languages? Theorem (Time Hierarchy Theorem, [Hartmanis and Stearns, 65]) There exists a language L that is computed by a TM in time

O(t(n) logt(n))such that no TM running in time o(t(n))can compute it.

Theorem (Space Hierarchy Theorem, [Stearns, Hartmanis, Lewis, 65]) There exists a language L that is computed by a TM in space O(s(n)) such that no TM running in space o(s(n))can compute it.

Non-explicit separations.

(6)

Power of resources

Turing machines

With more time, can Turing machines compute more languages?

With more space, can Turing machines compute more languages? Theorem (Time Hierarchy Theorem, [Hartmanis and Stearns, 65]) There exists a language L that is computed by a TM in time

(7)

Power of resources

Turing machines

With more space, can Turing machines compute more languages?

Theorem (Time Hierarchy Theorem, [Hartmanis and Stearns, 65]) There exists a language L that is computed by a TM in time

(8)

Power of resources

Turing machines

(9)

Power of resources

Turing machines

(10)

Power of resources

Turing machines

(11)

Power of resources

We can ask a similar question for any model of computation and a resource.

Model of computation Resources of interest

Turing machines time, space, number of random bits, non-determinism, advice

Boolean circuits size, depth

Today we will focus on arithmetic formulas as a model of computation.

(12)

Power of resources

(13)

Power of resources

(14)

Power of resources

(15)

Power of resources

(16)

A model of computation for polynomials

Arithmetic formula +

×

x1 x1

x₂

+

×

x1 x1

−1

Definition: An arithmetic formula

a directed tree

with nodes labeled by +,×, x₁, . . . ,x_n or constants

(say overF)

. indegree 0 nodes : input gates outdegree 0 nodes: output gates without loss of generality alternate +,

×layers.

Size and product-depth

The number of nodes in the tree is the size of the formula.

The maximum number of product gates along any leaf to root path is its product-depth. (Closely related to the depth.)

(17)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

Definition: An arithmetic formula a directed tree

(say overF)

×layers.

(18)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

(say overF)

.

indegree 0 nodes : input gates outdegree 0 nodes: output gates without loss of generality alternate +,

×layers.

(19)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

(say overF)

. indegree 0 nodes : input gates

outdegree 0 nodes: output gates without loss of generality alternate +,

×layers.

(20)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

(say overF)

. indegree 0 nodes : input gates outdegree 0 nodes: output gates

without loss of generality alternate +,

×layers.

(21)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

(say overF)

×layers.

(22)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

with nodes labeled by +,×,

x₁, . . . ,x_n or constants (say over F).

×layers.

(23)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

×layers.

The maximum number of product gates along any leaf to root path is its product-depth.

(Closely related to the depth.)

(24)

A model of computation for polynomials

×

x1 x1

x₂

+

×

x1 x1

−1

×layers.

(25)

Small depth formulas

We will focus on small product-depth formulas.

Product-depth ∆ = 1: P Q

formulas The model is complete.

Let X ={x₁, . . . ,x_n}. Letp(X)∈F[X] be a degree d polynomial. p(x) = X

m∈M

c_m·m,

whereMset of all monomials in n variables of degree at most d. It may not always be a succinct representation.

(26)

Small depth formulas

formulas

The model is complete.

m∈M

c_m·m,

(27)

Small depth formulas

m∈M

c_m·m,

(28)

Small depth formulas

Let X ={x₁, . . . ,x_n}.

Letp(X)∈F[X] be a degree d polynomial. p(x) = X

m∈M

c_m·m,

(29)

Small depth formulas

Let X ={x₁, . . . ,x_n}. Letp(X)∈F[X] be a degree d polynomial.

p(x) = X

m∈M

c_m·m,

(30)

Small depth formulas

p(x) = X

m∈M

c_m·m,

(31)

Small depth formulas

p(x) = X

m∈M

c_m·m,

whereMset of all monomials in n variables of degree at most d.

It may not always be a succinct representation.

(32)

Small depth formulas

p(x) = X

m∈M

c_m·m,

(33)

Examples of polynomials

Letp(X) = X

S⊆[n]

Y

i∈S

x_i

This has sizeO(2ⁿ).

However, here is its succinct representation. p(X) =Q

i∈[n](1 +xi) of sizeO(n). This is aQ P

formula for the same polynomial.

(34)

Examples of polynomials

Letp(X) = X

S⊆[n]

Y

i∈S

x_i

However, here is its succinct representation. p(X) =Q

(35)

Examples of polynomials

Letp(X) = X

S⊆[n]

Y

i∈S

x_i

However, here is its succinct representation.

p(X) =Q

(36)

Examples of polynomials

Letp(X) = X

S⊆[n]

Y

i∈S

x_i

p(X) =Q

i∈[n](1 +xi)

of sizeO(n). This is aQ P

(37)

Examples of polynomials

Letp(X) = X

S⊆[n]

Y

i∈S

x_i

p(X) =Q

i∈[n](1 +xi) of sizeO(n).

This is aQ P

(38)

Examples of polynomials

Letp(X) = X

S⊆[n]

Y

i∈S

x_i

p(X) =Q

i∈[n](1 +xi) of sizeO(n).

This is aQ P

(39)

Multilinear polynomials

Let X ={x₁, . . . ,x_N}.

Letp(X)∈F[X] be a degree d multilinear polynomial.

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

Many interesting polynomials are multilinear. Determinant: Det(X) =P

σ∈Snsgn(σ)Qn i=1x_i_σ(i) Permanent: Perm(X) =P

σ∈S_n

Qn i=1x_iσ(i) Matrix Multiplication: (X ×Y)i,j =Pn

k=1xik ×ykj

(40)

Multilinear polynomials

Let X ={x₁, . . . ,x_N}. Letp(X)∈F[X] be a degree d multilinear polynomial.

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

σ∈S_n

k=1xik ×ykj

(41)

Multilinear polynomials

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

σ∈S_n

k=1xik ×ykj

(42)

Multilinear polynomials

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

Many interesting polynomials are multilinear.

Determinant: Det(X) =P

σ∈S_n

k=1xik ×ykj

(43)

Multilinear polynomials

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

σ∈Snsgn(σ)Qn i=1x_i_σ(i)

Permanent: Perm(X) =P

σ∈S_n

k=1xik ×ykj

(44)

Multilinear polynomials

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

σ∈S_n

Qn

i=1x_iσ(i)

Matrix Multiplication: (X ×Y)i,j =Pn

k=1xik ×ykj

(45)

Multilinear polynomials

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

σ∈S_n

Qn

i=1x_iσ(i) Matrix Multiplication: (X ×Y)i,j =Pn

k=1x_ik ×y_kj

(46)

Multilinear polynomials

p(x) = X

S∈[n]:|S|≤d

c_S·Y

i∈S

x_i,

σ∈S_n

Qn

i=1x_iσ(i) Matrix Multiplication: (X ×Y)i,j =Pn

k=1x_ik ×y_kj

(47)

Multilinear formulas

A formula is multilinear if every gate in it computes a multilinear polynomial.

Many tools and techniques

A breakthrough result of Raz[Raz04] gave a strong lower bound. Multilinear formulas for Det/Perm must have superpolynomial size. A set of tools introduced in [Raz04].

Extended and appended by a line of work.

[Raz06,RSY07,RY09,DMPY12,KV17].

(48)

Multilinear formulas

A breakthrough result of Raz[Raz04] gave a strong lower bound.

Multilinear formulas for Det/Perm must have superpolynomial size. A set of tools introduced in [Raz04].

(49)

Multilinear formulas

Multilinear formulas for Det/Perm must have superpolynomial size.

A set of tools introduced in [Raz04]. Extended and appended by a line of work.

(50)

Multilinear formulas

A set of tools introduced in [Raz04].

(51)

Multilinear formulas

A set of tools introduced in [Raz04].

(52)

Small depth formulas

We will focus on small product-depth multilinear formulas.

or P Q P

formulas P Q formulas are not succinct.

What about P Q P

formulas? p(x) = X

i∈[s]

Y

j∈[s⁰]

Li,j,where, Li,j are linear polynomials inX.

The model is surprisingly powerful! [AV08,Koi09,Tav10,GKKS12] Any polynomial on n variables of degree d computable by a size s circuit can be computed by P Q P

formula of size s^O(

√ d). (Assume characteristic 0.)

ThisP Q P

realization is non-multilinear!

(53)

Small depth formulas

or P Q P

formulas

P Q formulas are not succinct. What about P Q P

formulas? p(x) = X

i∈[s]

Y

j∈[s⁰]

ThisP Q P

(54)

Small depth formulas

or P Q P

What about P Q P

formulas? p(x) = X

i∈[s]

Y

j∈[s⁰]

ThisP Q P

(55)

Small depth formulas

or P Q P

What about P Q P

formulas?

p(x) = X

i∈[s]

Y

j∈[s⁰]

ThisP Q P

(56)

Small depth formulas

or P Q P

What about P Q P

formulas?

p(x) = X

i∈[s]

Y

j∈[s⁰]

L_i,j,where, L_i,j are linear polynomials inX.

The model is surprisingly powerful!

[AV08,Koi09,Tav10,GKKS12] Any polynomial on n variables of degree d computable by a size s circuit can be computed by P Q P

ThisP Q P

(57)

Small depth formulas

or P Q P

What about P Q P

formulas?

p(x) = X

i∈[s]

Y

j∈[s⁰]

The model is surprisingly powerful! [AV08,Koi09,Tav10,GKKS12]

Any polynomial on n variables of degree d computable by a size s circuit can be computed by

P Q P

ThisP Q P

(58)

Small depth formulas

or P Q P

What about P Q P

formulas?

p(x) = X

i∈[s]

Y

j∈[s⁰]

Any polynomial on n variables of degree d computable by a size s circuit can be computed by P Q P

√ d).

(Assume characteristic 0.) ThisP Q P

(59)

Small depth formulas

or P Q P

What about P Q P

formulas?

p(x) = X

i∈[s]

Y

j∈[s⁰]

ThisP Q P

(60)

Small depth formulas

or P Q P

What about P Q P

formulas?

p(x) = X

i∈[s]

Y

j∈[s⁰]

ThisP Q P

(61)

Product-depth ∆ = 1

Non-multilinear to multilinear formula conversion.

Let p(X) be a multilinear polynomial computable by a P Q P formula of size s.

Does p(X) have a P Q P

multilinear formula of size s^O(1)? [Chillara,L, Srinivasan, 18]prove that the answer is no. Product-depth ∆ = 2 to ∆ = 1 conversion

Let p(X) be a multilinear polynomial computable by a P Q P Q multilinear formula of size s.

multilinear formula of size s^O(1)? [Kayal, Nair, Saha, 15]show that this is not possible.

(62)

Product-depth ∆ = 1

multilinear formula of size s^O(1)? [Chillara,L, Srinivasan, 18]prove that the answer is no. Product-depth ∆ = 2 to ∆ = 1 conversion

(63)

Product-depth ∆ = 1

multilinear formula of size s^O(1)?

[Chillara,L, Srinivasan, 18]prove that the answer is no. Product-depth ∆ = 2 to ∆ = 1 conversion

(64)

Product-depth ∆ = 1

multilinear formula of size s^O(1)? [Chillara,L, Srinivasan, 18]prove that the answer is no.

Product-depth ∆ = 2 to ∆ = 1 conversion

(65)

Product-depth ∆ = 1

(66)

Product-depth ∆ = 1

(67)

Product-depth ∆ = 1

multilinear formula of size s^O(1)?

[Kayal, Nair, Saha, 15]show that this is not possible.

(68)

Product-depth ∆ = 1

(69)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

formula of size s.

Consider theQ P

layer Q

i∈[t]Q_i. That is,P

Q[t]P Q.

Open up the multiplication of summands as a sum of multiplications. P

Q[t]P

Q −→ P

P[exp(t)]Q

Q −→ P[exp(t)]Q

The conversion incurs an exponential blow-up.

[Kayal, Nair, Saha, 15]show that this exponential blow-up is essential while going from ∆ = 2 to ∆ = 1.

(70)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

formula of size s. Consider theQ P

layer Q

i∈[t]Q_i.

That is,P

Q[t]P Q.

Q[t]P

Q −→ P

P[exp(t)]Q

Q −→ P[exp(t)]Q

(71)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

layer Q

Q[t]P Q.

Q[t]P

Q −→ P

P[exp(t)]Q

Q −→ P[exp(t)]Q

(72)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

layer Q

Q[t]P Q.

Open up the multiplication of summands as a sum of multiplications.

P

Q[t]P

Q −→ P

P[exp(t)]Q

Q −→ P[exp(t)]Q

(73)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

layer Q

Q[t]P Q.

P

Q[t]P

Q −→ P

P[exp(t)]Q Q

−→ P[exp(t)]Q

(74)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

layer Q

Q[t]P Q.

P

Q[t]P

Q −→ P

P[exp(t)]Q

Q −→ P[exp(t)]Q

(75)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

layer Q

Q[t]P Q.

P

Q[t]P

Q −→ P

P[exp(t)]Q

Q −→ P[exp(t)]Q

(76)

How expensive ∆ = 2 −→ ∆ = 1?

ConsiderP Q P Q

layer Q

Q[t]P Q.

P

Q[t]P

Q −→ P

P[exp(t)]Q

Q −→ P[exp(t)]Q

(77)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

formula of sizes and product depth

∆ + 1.

Consider theQ P

layer Q

i∈[t]Qi, such that t≤s^O^(1/∆). That is,P Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

Open up the multiplication of summands as a sum of multiplications. P Q. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P

−→ P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P −→

P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

Careful analysis shows a blow-up of exp(s^1/∆+o(1)). Is the blow-up essential?

(78)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

∆ + 1.

Consider theQ P

layer Q

i∈[t]Qi, such that t≤s^O^(1/∆).

That is,P Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

Q[(s^O(1/∆))]P

Q. . .P Q P

−→ P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P −→

P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

(79)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

∆ + 1.

Consider theQ P

layer Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

Q[(s^O(1/∆))]P

Q. . .P Q P

−→ P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P −→

P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

(80)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

∆ + 1.

Consider theQ P

layer Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

P Q. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P

−→ P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P −→

P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

(81)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

∆ + 1.

Consider theQ P

layer Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

P Q. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P

−→

P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P

−→ P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

(82)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

∆ + 1.

Consider theQ P

layer Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

P Q. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P

−→

P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P

−→

P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

(83)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

∆ + 1.

Consider theQ P

layer Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

P Q. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P

−→

P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P

−→

P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

Careful analysis shows a blow-up of exp(s^1/∆+o(1)).

Is the blow-up essential?

(84)

Larger product depth ∆ + 1 −→ ∆

ConsiderP Q P Q

. . .P Q P

∆ + 1.

Consider theQ P

layer Q

. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P .

P Q. . .P

Q[(s^O(1/∆))]P

Q. . .P Q P

−→

P Q. . .P

P[exp((s^O(1/∆)))]Q

Q. . .P Q P

−→

P Q. . .

P[exp((s^O(1/∆)))]Q

. . .P Q P

Careful analysis shows a blow-up of exp(s^1/∆+o(1)).

Is the blow-up essential?

(85)

Depth hierarchy theorem

More Resources

More power?

More Product-depth More power?

(86)

Depth hierarchy theorem

More Resources

More power?

More Product-depth More power?

(87)

Depth hierarchy theorem

More Resources More power?

More Product-depth More power?

(88)

Depth hierarchy theorem

More Resources More power?

More Product-depth

More power?

(89)

Depth hierarchy theorem

More Resources More power?

More Product-depth

More power?

(90)

Depth hierarchy theorem

More Resources More power?

More Product-depth More power?

(91)

Depth hierarchy theorems

Arithmetic circuit complexity world

[Raz and Yehudayoff, 2009]prove quasipolynomial depth-hierarchy theorem, i.e. they show quasipolynomial size lower bound for converting product-depth ∆ + 1 multilinear formula into product-depth ∆ formula, as long as ∆ is small.

[Kayal, Nair, Saha, 2015] show an exponential size lower bound for converting product-depth 2 multilinear formulas into product-depth 1 formulas.

Boolean circuit complexity world

[Ajtai,Frust et al.,Yao, H˚astad, 1980s]proved quasipolynomial depth-hierarchy theorem.

[H˚astad, 1986] proved exponential depth-hierarchy theorem.

(92)

Depth hierarchy theorems

[Raz and Yehudayoff, 2009]prove quasipolynomial depth-hierarchy theorem

, i.e. they show quasipolynomial size lower bound for converting product-depth ∆ + 1 multilinear formula into product-depth ∆ formula, as long as ∆ is small.

(93)

Depth hierarchy theorems

(94)

Depth hierarchy theorems

(95)

Depth hierarchy theorems

(96)

Depth hierarchy theorems

(97)

Depth hierarchy theorems

(98)

Depth hierarchy theorems

Our result: Near-optimal Depth Hierarchy Theorem

For any constant ∆, there is an explicit polynomial P_∆+1(x1, . . . ,xn) such that

P∆+1(X) is computed by multilinear formulaF∆+1 of product-depth

∆ + 1 and sizeO(n).

However, any multilinear formula of product-depth≤∆ forP∆+1(X) must have size exp(n^α^∆), where α∆= Ω(1/∆).

(99)

Depth hierarchy theorems

[Raz and Yehudayoff, 2009]prove quasipolynomial depth-hierarchy theorem

, i.e. they show quasipolynomial size lower bound for converting product-depth ∆ + 1 multilinear formula into product-depth ∆ formula, as long as ∆ is small.

(100)

Depth hierarchy theorems

(101)

Depth hierarchy theorems

(102)