s have size $poly(n)$) in the simultaneous NOF model. This has important applications in circuit complexity, as it could help to separate $ACC^0$ from other complexity classes. One of the candidates belongs to the family of composed functions. The input to these functions is represented by a $k\times (t\cdot n)$ boolean matrix $M$, whose row $i$ is the input $x_i$ and $t$ is a block-width parameter. A symmetric composed function acting on $M$ is specified by two symmetric $n$- and $kt$-variate functions $f$ and $g$, that output $f\circ g(M)=f(g(B_1),\dots,g(B_n))$ where $B_j$ is the $j$-th block of width $t$ of $M$. As the majority function $MAJ$ is conjectured to be outside of $ACC^0$, Babai et. al. suggested to study $MAJ\circ MAJ_t$, with $t$ large enough.

So far, it was only known that $t=1$ is not enough for $MAJ\circ MAJ_t$ to break the $\log n$ barrier in the simultaneous deterministic NOF model. In this paper, we extend this result to any constant block-width $t>1$, by giving a protocol of cost $2^{O(2^t)}\log^{2^{t+1}}(n)$ for any symmetric composed function when there are $2^{\Omega(2^t)}\log n$ players.