Skip to main content
added 322 characters in body
Source Link
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]). [Update: As far as I know, this is only true for iterated matrix multiplication $tr(M_1 M_2 \dotsb M_d)$, rather than matrix powering $tr(M^d)$. When $m$ is allowed to grow these two are essentially equivalent, but for fixed $m$, e.g. $m=3$ I don't know if $3 \times 3$ matrix powering is poly-formula-size-complete.]

If $m$ can grow but $d$ is fixed, then this is the same as matrix multiplication, up to $O(\log d) = O(1)$ factors. Since circuits for matrix multiplication can be converted to bilinear circuits with only a factor 2 blow-up in size, circuit and formula size here are essentially the same, and the question boils down to the classic open question of the exponent of matrix multiplication.

If both $m$ and $d$ can grow, then this is equivalent in power to the determinant (corresponding to the Boolean class $\mathsf{DET}$ and the algebraic class $\mathsf{VP}_{ws}$). So here the question becomes about the circuit/formula complexity of the determinant. Both of these are well-known open questions (obviously there are cubic circuits; the best known upper bound on formula size of the determinant is quasi-polynomial).

Most (perhaps even all) nontrivial algorithms for matrix multiplication use cancellations in a crucial way, so I would expect there is a difference between the monotone case and the unrestricted case. Also, note that the equivalence between matrix powering and determinant in the last case is necessarily non-monotone (since matrix powering is a polynomial with all nonnegative coefficients, but the determinant is not).

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]).

If $m$ can grow but $d$ is fixed, then this is the same as matrix multiplication, up to $O(\log d) = O(1)$ factors. Since circuits for matrix multiplication can be converted to bilinear circuits with only a factor 2 blow-up in size, circuit and formula size here are essentially the same, and the question boils down to the classic open question of the exponent of matrix multiplication.

If both $m$ and $d$ can grow, then this is equivalent in power to the determinant (corresponding to the Boolean class $\mathsf{DET}$ and the algebraic class $\mathsf{VP}_{ws}$). So here the question becomes about the circuit/formula complexity of the determinant. Both of these are well-known open questions (obviously there are cubic circuits; the best known upper bound on formula size of the determinant is quasi-polynomial).

Most (perhaps even all) nontrivial algorithms for matrix multiplication use cancellations in a crucial way, so I would expect there is a difference between the monotone case and the unrestricted case. Also, note that the equivalence between matrix powering and determinant in the last case is necessarily non-monotone (since matrix powering is a polynomial with all nonnegative coefficients, but the determinant is not).

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]). [Update: As far as I know, this is only true for iterated matrix multiplication $tr(M_1 M_2 \dotsb M_d)$, rather than matrix powering $tr(M^d)$. When $m$ is allowed to grow these two are essentially equivalent, but for fixed $m$, e.g. $m=3$ I don't know if $3 \times 3$ matrix powering is poly-formula-size-complete.]

If $m$ can grow but $d$ is fixed, then this is the same as matrix multiplication, up to $O(\log d) = O(1)$ factors. Since circuits for matrix multiplication can be converted to bilinear circuits with only a factor 2 blow-up in size, circuit and formula size here are essentially the same, and the question boils down to the classic open question of the exponent of matrix multiplication.

If both $m$ and $d$ can grow, then this is equivalent in power to the determinant (corresponding to the Boolean class $\mathsf{DET}$ and the algebraic class $\mathsf{VP}_{ws}$). So here the question becomes about the circuit/formula complexity of the determinant. Both of these are well-known open questions (obviously there are cubic circuits; the best known upper bound on formula size of the determinant is quasi-polynomial).

Most (perhaps even all) nontrivial algorithms for matrix multiplication use cancellations in a crucial way, so I would expect there is a difference between the monotone case and the unrestricted case. Also, note that the equivalence between matrix powering and determinant in the last case is necessarily non-monotone (since matrix powering is a polynomial with all nonnegative coefficients, but the determinant is not).

Post Undeleted by Joshua Grochow
Post Deleted by Joshua Grochow
Source Link
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]).

If $m$ can grow but $d$ is fixed, then this is the same as matrix multiplication, up to $O(\log d) = O(1)$ factors. Since circuits for matrix multiplication can be converted to bilinear circuits with only a factor 2 blow-up in size, circuit and formula size here are essentially the same, and the question boils down to the classic open question of the exponent of matrix multiplication.

If both $m$ and $d$ can grow, then this is equivalent in power to the determinant (corresponding to the Boolean class $\mathsf{DET}$ and the algebraic class $\mathsf{VP}_{ws}$). So here the question becomes about the circuit/formula complexity of the determinant. Both of these are well-known open questions (obviously there are cubic circuits; the best known upper bound on formula size of the determinant is quasi-polynomial).

Most (perhaps even all) nontrivial algorithms for matrix multiplication use cancellations in a crucial way, so I would expect there is a difference between the monotone case and the unrestricted case. Also, note that the equivalence between matrix powering and determinant in the last case is necessarily non-monotone (since matrix powering is a polynomial with all nonnegative coefficients, but the determinant is not).