Iterated multiplication of permutation matrices

Question

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

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