Введение

Немецкий математик и исследователь алгоритмов (род. 1936)

Волкер Страссен (родился 29 апреля 1936 года) – немецкий математик, профессор-эмерит кафедры математики и статистики в Университете Констанца. За значительный вклад в анализ алгоритмов он был удостоен множества наград, включая медаль Кантора. После изучения музыки, философии, физики и математики в нескольких немецких университетах, он занял должность в отделе статистики Калифорнийского университета в Беркли, одновременно готовя диссертацию (абилитацию) в Университете Эрлангена-Нюрнберга, куда к тому времени переехал Джейкобс.

Исследования

Страссен начал свои исследования как теоретик вероятностей; его статья 1964 года «Принцип инвариантности для закона итерационного логарифма» определила функциональную форму закона итерационного логарифма, демонстрируя форму масштабной инвариантности в случайных блужданиях. Этот результат, теперь известный как принцип инвариантности Страссена или закон итерационного логарифма Страссена, был широко цитирован и привел к докладу на Международном конгрессе математиков в 1966 году. В 1969 году Страссен переключил свои исследовательские усилия на анализ алгоритмов, опубликовав статью о методе Гаусса, в которой представил алгоритм Страссена – первый алгоритм для умножения матриц, работающий быстрее, чем O(n³) – временная сложность, достигаемая наивным алгоритмом. В той же статье он также представил асимптотически быстрый алгоритм для инвертирования матриц, основанный на алгоритме быстрого умножения матриц. Этот результат стал важным теоретическим прорывом, стимулировавшим дальнейшие исследования в области быстрого умножения матриц, и, несмотря на последующие теоретические улучшения, он остается практичным методом для умножения плотных матриц умеренных и больших размеров. В 1971 году Страссен совместно с Арнольдом Шёнхаге опубликовал статью об асимптотически быстром умножении целых чисел, основанном на быстром преобразовании Фурье; см. алгоритм Шёнхаге — Страссена. Страссен также известен своей работой 1977 года с Робертом М. Соловеем над тестом простоты Соловея — Страссена, первым методом, показавшим, что проверка числа на простоту может быть выполнена за полиномиальное время с использованием рандомизации, и одним из первых результатов, продемонстрировавших возможности рандомизированных алгоритмов в целом.

Награды и почести

В 1999 году Страссен был удостоен медали Кантора, в 2011 году он получил медаль Конрада Цузе от Gesellschaft für Informatik. В 2012 году он стал членом Американского математического общества.