6
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Is d specified in unary or binary? $\endgroup$
    – SamiD
    Commented Sep 19, 2015 at 18:02

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ What if the variables $x_i$ are non-commutative? $\endgroup$
    – user34945
    Commented Mar 28, 2016 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$
    – Joshua Grochow
    Commented Mar 28, 2016 at 4:36
  • $\begingroup$ If we power and $d$ is allowed to grow, then wouldn't number of bits to represent matrix entries could be exponential. Correct? Would the answers still hold? $\endgroup$
    – Turbo
    Commented Feb 23 at 4:48
  • 1
    $\begingroup$ If M is m x m with n-bit entries, then bit-size of entries of M^d is roughly d(n + log m), so I don't think there's an issue... (Maybe you're thinking of "repeated squaring circuits"? Which are circuits of N size computing x^{2^N}, which can have bit-size 2^N. But that's not what's happening here.) $\endgroup$
    – Joshua Grochow
    Commented Feb 23 at 5:08
  • 1
    $\begingroup$ Instead of M^{2^N} if we are asked M^{2^N} mod q where q is of order 2^N (that is N bits) then is the problem in NC^2? $\endgroup$
    – Turbo
    Commented Feb 24 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.