У 1969, Штрассен зосередив свої зусилля на аналізі складності алгоритмів і розробці швидких алгоритмів. У статті[8] про неоптимальності методу Гауса він довів, що для перемноження двох матриць 2X2 достатньо семи множень і запропонував швидкий алгоритм Штрассена для множення матриць. Це перший алгоритм, який дозволяє перемножати великі матриці за час менше ніж O(n3). У тій же статті він запропонував асимптотично швидкий алгоритм оберненої матриці, заснований на алгоритмі швидкого множення матриць. Цей результат був важливим теоретичним проривом, що спричинило численні подальші дослідження проблеми швидкого множення матриць. Незважаючи на подальші поліпшення цей метод залишається практичним шляхом множення великих щільних матриць. Поставлена Штрассеном проблема швидкого множення матриць[9] донині не вирішена.
У 1977 році він разом з Робертом Соловеєм запропонував тест Соловея — Штрассена для визначення простоти числа. Це був перший поліноміальний ймовірнісний алгоритм з обмеженою односторонньої помилкою для визначення простоти числа — клас складності RP. І один з перших результатів, що привернув увагу до можливостей ймовірнісних алгоритмів.
↑ абPreis für Prof. Volker Strassen, uni'kon 16.2004, Univ. of Konstanz.
↑Фолькер Штрассен:Gaussian Elimination is not Optimal. In: Numerische Mathemetik, Bd. 13 (1969), S. 354–356, ISSN00298-599X
↑ Кібернетичний збірник. Нова серія. Вип. 25. Збірник статей 1983–1985 рр .: Пер. з англ. — М .: Світ, 1988 — В. Б. Алексеев. Складність множення матриць. Огляд.