Circuit complexity of group actions Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{0,1\}^{N}\rightarrow\{0,1\}^{N}$ is computed by a reversible circuit consisting of $t_{i}$ reversible gates and where $t=t_{1}+\dots+t_{k}$ (for definiteness, assume that we can use any reversible gate on three bits). Then we shall say that $G$ has action complexity at most $t$.

Let $\delta_{n}$ be the maximum action complexity of a group $G$ with $|G|\leq n$. What are some bounds on $\delta_{n}$?

To obtain a trivial lower bound, we observe that if $|G|=n$, then
$|G|\leq|S_{2^{N}}|=(2^{N})!$ and without loss of generality, $t\geq N/3$, so
$t\geq\sqrt[1+\epsilon]{\log_{2}(\log_{2}(n))}$.

For a trivial upper bound, we can set $k\leq\log_{2}(n)$ and by Cayley's theorem, $G$ embeds into $S_{2^{N}}$ where $N=\lceil\log_{2}(n)\rceil$. Let $\iota:G\rightarrow S_{2^{N}}$ be an embedding. Now, the functions $\iota(g_{1}),...,\iota(g_{k})$ along with their inverses can each by computed by circuits of size $O(2^{N})=O(n)$ which gives an upper bound of
$\delta_{n}\leq O(n\cdot\log_{2}(n))$.

There is a large gap between the lower bounds and the upper bounds which I gave, so I am looking for better bounds for $\delta_{n}$.

Since this is CSTheory and not MathOverflow, I am interested in upper bounds which are not be obtained simply by finding smaller $r$ such that $G$ embeds in $S_{2^{r}}$ or by finding a smaller generating set for $G$.

Note: I could have formulated this question in terms of conventional Boolean circuits since if $f$ is a bijective function and both $f,f^{-1}$ can be computed by conventional circuits on $n$ gates, then $f$ can be computed by a reversible circuit on $O(n)$ gates.
The number of isomorphism classes of groups of order $\leq n$ is asymptotically $n^{\Theta(\log^2 n)}$, so to even specify all such groups requires strings of length $\Omega(\log^3 n)$, so this is also a lower bound on your action complexity.