Complexity of computing homotopy groups of spheres.

I studied a 1957 algorithm of E.H. Brown, which can be used to determine the homotopy groups of any space obtained as the realization of a finite simplicial set.

I gave an explicit upper bound on the complexity of the algorithm when all homotopy groups are finite, and as a special case of when there are infinite homotopy groups, provided a bound on using the process to compute the homotopy groups of odd-dimensional spheres.

You can find a preliminary draft on the math department’s website.

Errata

I don’t think that my bound on the process involving the infinite group \(\pi_n(S^n) \simeq \mathbb{Z}\) is quite correct; this likely does not have an effect on the asymptotic complexity, but I will revise when I get a chance.