Blog
初めまして。研究開発チームの吉田です。定期的にエントリを書かせていただくことになりましたので、今後ともよろしくお願い致します。
突然ですが京都賞という賞が有るのをご存知でしょうか？先端技術部門、基礎科学部門、思想・芸術部門の三つの部門からなり、それぞれ毎年一人ずつ賞が贈られます。過去には確率微分方程式で有名な伊藤清氏も受賞されている権威ある賞です。今年は先端技術部門にiPS細胞で有名な京都大学の山中伸弥氏、基礎科学部門にラースロー・ロヴァース氏、思想・芸術部門にウィリアム・ケントリッジ氏が選ばれました。その授賞式は去る11月10日に開催され、流石現代と言うべきかその様子がustreamで配信されました。
さて、今回の話題は山中先生ではなくてロヴァース先生についてです。計算機科学の中には理論計算機科学と呼ばれる分野が有ります。簡単に説明するとP!=NPを証明したり、速いアルゴリズムを作るのを目的とする分野で、計算機を題材とする数学と表現することも出来るかもしれません。その理論計算機科学でロヴァース先生は非常に沢山の貢献をされてきました。
僕は弊社Preferred Infrastructureでプログラムを書く傍ら、理論計算機科学の研究をしていて、今回は折角の機会なのでロヴァース先生について紹介したいと思います。ロヴァース先生の成果は余りに多いので、どれが代表作かを決めるのがとても難しいのですが、僕がすぐに考えつくものを挙げると、
- Lovasz Local Lemma: ある事象が起こる確率が正であることを示すのに有用な定理。例えば疎なMax SATは常に充足可能などが示せる。
- LLL Algorithm: 格子の基底が与えられた時に、より短くより直交する規定を見つける
- Perfect Graph Theorem: 彩色数が最大クリークの大きさに一致するグラフをパーフェクトと呼ぶ。グラフがパーフェクトであるための必要十分条件を与えた。
- Lovasz’ Theta Function: 常に最大クリークの大きさと彩色数の間に入るグラフのパラメータ。多項式時間で計算可能で、これらの値の近似に使われる。
などです。分野外の方は殆ど聞いたことがない場合が殆どだと思いますが、どれも大きな成果です。理論計算機科学の世界の巨人と言って良いでしょう。
さて、そのロヴァース先生の京都賞受賞を記念してサテライトワークショップが開催されています。世界中からロヴァース先生とゆかりのある人たちを集めて、好きに講演してもらおうという企画です。内容は巡回セールスマン問題、圏論、主成分分析、ランダムグラフ、Lovasz Local Lemmaなど多岐に渡ります。
今この文章を書いているのがちょうど二日目が終わった後なのですが、流石というべきか、昔のロヴァース先生とのエピソードだけを語って終わるような人は一人もいなくて、全ての人が理論的な話をされていました。やはりそれが一番ロヴァース先生が喜ぶということなのでしょうか。今日はロヴァース先生自身の講演も有ったのですが、昔の思い出話でもするのかと思いきやそうではなくて最近書いた論文の内容の紹介でした。内容については次回のエントリで軽く触れたいと思っています。また、講演の他にも主に学生によるポスターセッションが有り、そこで僕も発表する機会を頂きました。これだけの人が日本に集まる機会はなかなか無いということで、日本中の理論計算機科学をやっている先生や学生方が集まっていました。そういう人たち、特に若い世代の間のコミュニティを作るという意味でもとても成功しているワークショップなのではないかと感じています。僕自身もこれまでお会いしたことの無かった人と話をする機会を持てています。
今回は京都賞とロヴァース先生の紹介をしました。次回はサテライトワークショップの講演のうち専門家でなくても判りやすそうなものに絞って内容について少し触れてみたいと思います。
Tag
