Штрассен, Фолькер

Штрассен родился 29 апреля 1936 года в дюссельдорфском районе Герресхайм^[5]. Изучал музыку, философию, физику и математику с 1955 года в Кёльнском, Фрайбургском, Мюнхенском и Гёттингенском университетах^[5][6]. В 1961 году он получил диплом по математике в Гёттингенском университете^[6], а в 1962 году — докторскую степень под руководством Конрада Якобса^[7]. Затем, занимая должность на кафедре статистики Калифорнийского университета в Беркли он подготовил свою хабилитацию для университета Эрлангена — Нюрнберга, куда переехал Якобс^[5].^[6] Защита состоялась в 1966 году, тема работы — «Almost Sure Behavior of Sums of Independent Random Variables and Martingales»^[6]. В 1968 году, Штрассен перешел в Институт Прикладной Математики Цюрихского университета, где проработал двадцать лет. В 1988 году он перешел в Констанцский университет^[5]. В 1998 году ушел на пенсию^[8].

Свои исследования Штрассен начал как вероятностник. В статье 1964 года «Принцип инвариантности для закона повторного логарифма» он дал функциональную форму закона повторного логарифма, демонстрирующую масштабную инвариантность случайного блуждания. Этот результат, известный сегодня как принцип инвариантности Штрассена или закон повторного логарифма Штрассена, обильно цитировался и был представлен в 1966 году на Международном конгрессе математиков.

В 1969, Штрассен сосредоточил свои усилия на анализе сложности алгоритмов и разработке быстрых алгоритмов. В статье о неоптимальности метода Гаусса^[9] он доказал, что для перемножения двух матриц 2 X 2 над некоммутативным кольцом достаточно семи умножений и, используя рекурсию, предложил быстрый алгоритм Штрассена для умножения больших матриц. Это первый алгоритм, который позволяет перемножать большие матрицы за время меньше, чем O(n³). В той же статье он предложил асимптотически быстрый алгоритм обращения матрицы, основанный на алгоритме быстрого умножения матриц. Этот результат был важным теоретическим прорывом, повлёкшим многочисленные дальнейшие исследования проблемы быстрого умножения матриц. Несмотря на последующие улучшения алгоритм Штрассена остаётся практическим методом умножения больших плотных матриц. Поставленная Штрассеном проблема быстрого умножения матриц^[10] остаётся открытой, но по состоянию на 2024 год верхняя оценка сложности умножения матриц снижена до O(n^2,371552) благодаря исследованиям группы учёных (Ж. Чжоу, Р. Дуань, Х. Ву, В. Василевска-Вильямс)^[11].

В 1971 году Штрассен совместно с Арнольдом Шёнхаге предложил метод асимптотически быстрого умножения больших целых чисел, основанный на быстром преобразовании Фурье.

В 1977 году он вместе с Робертом Соловеем предложил тест Соловея — Штрассена для определения простоты числа. Это был первый полиномиальный вероятностный алгоритм с ограниченной односторонней ошибкой для определения простоты числа — класс сложности RP. И один из первых результатов, привлекший внимание к возможностям вероятностных алгоритмов. В современной криптографии тест Соловэя — Штрассена имеет преимущественно историческое значение, так как на практике был вытеснен более эффективным тестом Миллера — Рабина^[12].

Был одним из основных создателей теории алгебраической сложности, в которой ему принадлежат многие классические теоремы.

В 1999 году Штрассен был награждён медалью Кантора^[5],. В 2003 году Фолькер Штрассен, Роберт Соловей, Гари Миллер и Михаэль Рабин получили премию Париса Канеллакиса за вклад в разработку вероятностного тестирования простоты чисел^[8]. В 2008 году он получил премию Кнута за «выдающийся вклад в разработку и анализ эффективных алгоритмов.» В 2011 году он получил медаль Конрада Цузе от Немецкого общества информатики^[13].

Штрассен является членом нескольких научных академий и обществ: Национальной академии наук Германии «Леопольдина», Гёттингенской академии наук, Гейдельбергской академии наук (действительный член с 1996 года), а также действительным членом (Fellow) Американского математического общества (с 2012 года)^[14][15].

• An Invariance Principle for the Law of the Iterated Logarithm (1964)^[16]
• Gaussian Elimination is not Optimal (1969)^[6]
• Schnelle Multiplikation großer Zahlen (1971, соавтор А. Шёнхаге)^[6]
• A fast Monte-Carlo test for primality (1977, соавтор Р. Соловэй)^[6]