Let $f(x) = (f_1(x),...,f_n(x)) \in \mathbb{Q}[x]^n$, and $g \in \mathbb{Q}[x_1,...,x_n]$. Assume $\deg(f_i) \leq b$ for all $i$, and $\deg(g) \leq c$. Is there an efficient algorithm for computing $g \circ f$, and what is its complexity?
A naïve approach with a back-of-the-envelope bound leads to $O(b^2c^{n+2})$ operations. Can we avoid the exponential growth?
Well, there are $\binom{n+c-1}{c}$ monomials in $x_1, \ldots, x_n$ of degree $c$, which is like $n^{c-1}$ if $c$ is fixed and $n \to \infty$, and like $c^n$ if $n$ is fixed and $c \to \infty$. You could use exponentiation by squaring to handle each monomial reasonably quickly, though if $c$ is fixed and $n \to \infty$ you may as well just precompute all large enough powers of $f_i(x)$. You'd want to use FFT's for the univariate polynomial multiplications.