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

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})}$$.
• 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? Commented Jun 8, 2021 at 6:19
• I’m not sure it has been published yet. In the slides there are some limits on $d$. Commented Jun 8, 2021 at 6:49