  We give lower bounds on the complexity of the word problem of certain
non-solvable groups: for a large class of non-solvable infinite groups,
including in particular free groups, Grigorchuk's group and Thompson's groups,
we prove that their word problem is $\mathsf{NC}^1$-hard. For some of these
groups (including Grigorchuk's group and Thompson's groups) we prove that the
compressed word problem (which is equivalent to the circuit evaluation problem)
is $\mathsf{PSPACE}$-complete.
