  We study the complexity of computing Kronecker coefficients
$g(\lambda,\mu,\nu)$. We give explicit bounds in terms of the number of parts
$\ell$ in the partitions, their largest part size $N$ and the smallest second
part $M$ of the three partitions. When $M = O(1)$, i.e. one of the partitions
is hook-like, the bounds are linear in $\log N$, but depend exponentially on
$\ell$. Moreover, similar bounds hold even when $M=e^{O(\ell)}$. By a separate
argument, we show that the positivity of Kronecker coefficients can be decided
in $O(\log N)$ time for a bounded number $\ell$ of parts and without
restriction on $M$. Related problems of computing Kronecker coefficients when
one partition is a hook, and computing characters of $S_n$ are also considered.
