Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where

  1. $m=\mathit{poly}(n)$
  2. $m=\mathit{poly}(\log n)$ which means $m=O(\log^k n)$ where $k\in\mathbb N_{>1}$
  3. $m=O(\log n)$?

Given $\mathit{poly}(n)$ inputs it is clearly in $\mathit{AC}^0$ to test the promise every input matrix is a permutation.

On other hand general iterated matrix multiplication is is $\mathit{NC}^2$.


1 Answer 1


Ben Rossman showed that any unbounded fan-in depth $d$ circuit for your problem has size at least $n^{\Omega(m^{1/2d})}$. Conversely, a simple recursive construction gives an unbounded fan-in depth $d$ formula of size $n^{O(m^{1/d})}$.

  • 2
    $\begingroup$ I trust that you can do the arithmetic on your own. $\endgroup$ Apr 2, 2021 at 21:22
  • $\begingroup$ The bound stated is incorrect or else it separate NC1 and AC1. I think m is restricted. $\endgroup$
    – Turbo
    Jun 8, 2021 at 0:21
  • $\begingroup$ Do you know the correct reference (I see R'08 R'14 etc but no right reference)? Are you certain $m$ is not bounded by $\log n$ or $\log\log n$ or anything? $\endgroup$
    – Turbo
    Jun 8, 2021 at 6:19
  • $\begingroup$ I’m not sure it has been published yet. In the slides there are some limits on $d$. $\endgroup$ Jun 8, 2021 at 6:49
  • $\begingroup$ Yes unlikely these tricks can prove lower bounds. $\endgroup$
    – Turbo
    Jun 8, 2021 at 8:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.