Max Home IndustryРави Каннан был назван лауреатом Премии Кнута 2011 года, ежегодно присуждаемой Специальной группой по алгоритмам и теории вычислений ACM (Ассоциация вычислительной техники).
Группа алгоритмов и теории вычислений ACM вручила в этом году премию Кнута Рави Каннану из Microsoft Research Labs India за
«разработка влиятельных алгоритмических методов, направленных на решение давних вычислительных проблем».
Большая часть работ, которые упоминаются в качестве причины присуждения премии, могут показаться очень абстрактными, но есть также некоторые очень практические области исследований.
В цитируемой основной статье представлен алгоритм, который работает за полиномиальное время для оценки объема выпуклого тела в n-мерном пространстве. Он использует случайное блуждание по выпуклому телу, порожденному цепью Маркова. Большая часть работы Каннана посвящена случайным алгоритмам с использованием цепей Маркова.
Еще одна более практическая область исследований — это применение преимущественно случайных алгоритмов к большим данным и выборке. Например, быстрый алгоритм Монте-Карло, который производит приближенное умножение матриц, имеет всевозможные практические применения. Алгоритмы кластеризации также фигурируют в исследованиях, как и алгоритмы на решетке.
В целом исследование сосредоточено на алгоритмах, и поэтому Каннан — хороший выбор для этого приза, который связан с отцом анализа алгоритмов, Дональдом Кнутом.