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
    $\begingroup$ Let's just say I don't feel like answering. You already got a better answer, so I guess it worked out fine for you. $\endgroup$
    – user114966
    Apr 2 at 21:51

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 at 21:22
  • $\begingroup$ The bound stated is incorrect or else it separate NC1 and AC1. I think m is restricted. $\endgroup$
    – Mr.
    Jun 8 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$
    – Mr.
    Jun 8 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 at 6:49
  • $\begingroup$ Yes unlikely these tricks can prove lower bounds. $\endgroup$
    – Mr.
    Jun 8 at 8:03

Your Answer

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

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