En 1969, Strassen desplazó sus esfuerzos investigadores hacia el análisis de algoritmos con un artículo sobre eliminación gaussiana, presentando el algoritmo de Strassen, el primer algoritmo para realizar multiplicación de matrices más rápido que O(n3), la complejidad temporal que tendría el algoritmo más sencillo.En el mismo artículo también presentó un método asintóticamente rápido para realizar la inversión de una matriz, basado en la multiplicación rápida de matrices.Este resultado fue un importante avance teórico, logrando mucha investigación adicional sobre la multiplicación rápida de matrices, y a pesar de las mejoras teóricas posteriores sigue siendo un método práctico para la multiplicación de matrices densas de tamaños moderados a grandes.En 1999 Strassen fue premiado con la Medalla Cantor,[2] y en 2003 fue codestinatario del Premio Paris Kanellakis con Solovay, Gary Miller y Michael Rabin por su trabajo en los métodos de prueba de primalidad aleatoria.[5] En 2008 recibió el Premio Knuth por sus “seminales e influyente contribuciones al diseño y análisis de algoritmos eficientes”.
