In 1968 V. Strassen discovered the usual way we multiply matrices is not the most efficient one. This raised the question as to just how efficiently matrices can be multiplied, and led to the astounding conjecture that for large matrices, it is almost as easy to multiply them asto add them. After giving a brief history of the problem, I will explain how algebraic geometry and representation theory gives insight into this central question in computer science.

While much is known about existence of algorithms in the study of 3-manifolds and knot theory, much less is known about lower bounds on their complexity (hardness results). In this talk we will discuss hardness of several problems. We prove:

Theorem 1: given a 2- or 3-dimensional complex $X$, deciding if $X$ embed in $R^3$ in NP-hard.

We also prove that certain link invariants that are defined using 4-dimensional topology give rise to NP-hard problems; for example:

Theorem 2: deciding if a link in the 3-sphere bounds a smooth surface of non-negative Euler characteristic in the 4-ball is NP-hard.

For the main event we turn our attention to knots. The unknot recognition problem (solved by Haken in the 60's) is known to be in NP and co-NP, and as such, is not expected to be hard. Lackenby proved a polynomial bound on the number of Reidemeister moves needed to untangle an unknot diagram. In light of these two facts, one might hope for an efficient algorithm that find this optimal untangling. Unfortunately this is unlikely to happen since we prove:

Theorem 3: given an unknot diagram D and a positive integer n, deciding if D can be untangled using n Reidemeister moves is NP-hard.

This is joint work with Arnaud de Mesmay, Eric Sedgwick, and Martin Tancer.