# Iterated multiplication of permutation matrices

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

• 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.
– 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})}$$.

• I trust that you can do the arithmetic on your own. Apr 2 at 21:22
• The bound stated is incorrect or else it separate NC1 and AC1. I think m is restricted.
– Mr.
Jun 8 at 0:21
• 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?
– Mr.
Jun 8 at 6:19
• I’m not sure it has been published yet. In the slides there are some limits on $d$. Jun 8 at 6:49
• Yes unlikely these tricks can prove lower bounds.
– Mr.
Jun 8 at 8:03