Microsoft ResearchのRavi Kannan 氏が ACM SIGACTの(Special Interest Group on Algorithms and Computation Theory) Knuth Prize 2011の受賞者に指名された。 プレス発表 によると Microsoft Researchの科学者である氏は、以下の研究に対して受賞した。
長い間あった計算上の問題を解くことを目的にした、有力なアルゴリズム上の技法
氏は ACM Symposium on Theory of Computingで Knuth Prize記念講演を行う予定だ。
多くのソフトウェア エンジニアはアルゴリズムに関しては、研究者に残されている問題など殆ど無い、と考えているかもしれない。コンピュータグラフィックスや数値計算の問題のようなライブラリは、実装の中に隠れている。しかしいくつかの本質的な問題は今だに解くのが難しかったり、効率的なアプローチが必要である。Bangalore (India) にある Microsoft Research LabsでのRavi氏の活動は色々な分野に焦点を当てたもので、例えば、理論的コンピュータサイエンス、幾何学的アルゴリズム、機械学習、コンピュータによる線形代数などがある。 研究グループ は2007年に設立され、21世紀のアルゴリズムにフォーカスし、大容量データを伴う、今日の計算環境における新しい要求に取り組もうとしている。
例として、ACMは1990年に刊行されたRavi氏の研究論文をこれまでのアルゴリズムにおける最も素晴らしい成果である、としている。
凸形の体積を近似するランダム多項式時間アルゴリズムは、University of LeedsのMartin Dyer氏と Carnegie Mellon UniversityのAlan Frieze氏によって書かれたが、任意の高次元の凸集合の体積をいかに効率よく概算するかを示している。彼らが開発した方法は幾何学的サンプリング行うのにランダムウォークを使っているが、アルゴリズムの理論の中心となる技法である。1991年の Discrete Mathematics（離散数学）の Fulkerson Prizeの受賞論文もまた幾何学的等周の概念、境界によって印された面積を測る方法を理論的コンピュータサイエンスに導入した。
Ravi氏の業績をもっと深く知りたい読者は、彼のホームページを見るのといい。