Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables.

We know that size of smallest formula that computes $\mathsf{Tr}(M^d)$ where $d\in\Bbb N$ could be exponentially large in $n$ and $m$ at least when $n=m^2$.

Could it be possible that the smallest circuit size can be polynomial while formula size is exponential at least for case $n=m^2$?

Do the answers differ much if we seek monotone circuits and formulas?

  • 1
    $\begingroup$ Is d specified in unary or binary? $\endgroup$
    – SamiD
    Sep 19 '15 at 18:02

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).

  • $\begingroup$ What if the variables $x_i$ are non-commutative? $\endgroup$
    – user34945
    Mar 28 '16 at 3:14
  • 1
    $\begingroup$ In the second case (m growing, d fixed), the situation is essentially unchanged if the $x_i$ don't commute. I'd have to think a little about the various equivalences in the other cases. $\endgroup$ Mar 28 '16 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy