I have by now seen some algorithms to compute the gcd of two multivariate polynomials from $\mathbb{Z}[x_1,...,x_k]$, but what I am really looking for are statements about the general complexity of the problem. All I could find so far was that it seems to be considered bad, and one should avoid gcd-computations if possible.
But how bad is it actually? Are there any known upper or lower bounds?
Edit: The simplest algorithm I found is to recursively use the Euclidean algorithm for univariate polynomials on $\mathbb{Z}[x_1,...,x_{k-1}][x_k]$ and then for the coefficients $\mathbb{Z}[x_1,...,x_{k-2}][x_{k-1}]$ and so on. I'm already not quite clear on what the complexity of this algorithm is. I can also not imagine that there is no better way to do it.