László Lovász

第26回(2010)受賞

基礎科学部門

数理科学(純粋数学を含む)

ラースロー・ロヴァース

/  数学者

1948 -

エトヴェシュ・ロラーンド大学 教授

記念講演会

数学の新展開—伝統的理論と新しい応用の架け橋—

2010年

11 /11

会場:国立京都国際会館

ワークショップ

アルゴリズム科学の数理的展開

2010年

11 /12

13:00~17:20

会場:国立京都国際会館

業績ダイジェスト

離散最適化アルゴリズムを軸とした数理科学への多大な貢献

離散構造に関する先端的な研究を行うことによって、アルゴリズムの観点からさまざまな数学分野を結びつけ、離散数学、組合せ最適化、理論計算機科学などを中心とする数理科学の広い範囲に影響を与え、学術的側面と技術的側面の両面において、数理科学の持つ可能性を拡大することに多大な貢献をした。

贈賞理由

ラースロー・ロヴァース博士は、離散構造に関する先端的な研究を行うことによって、アルゴリズムの観点から様々な数学分野を結びつけ、学術的側面と技術的側面の両方において、数理科学の持つ可能性を拡大することに多大な貢献をした。個々の具体的研究成果はグラフの性質の解明あるいはグラフに関するアルゴリズムの設計という形で述べられたものが多いが、そこに示された方法論はグラフ理論の枠を超えた数理科学としての意義を有し、離散数学、組合せ最適化、理論計算機科学などを中心とする数理科学の広い範囲に影響を与えた。

ロヴァース博士の初期の代表的な業績である1972年のパーフェクトグラフ(弱)定理は、グラフ理論における著名な未解決問題を肯定的に解決したものであるが、線形不等式系による離散構造の表現というパラダイムの一頂点としての意義を有する。1979年のシャノン容量に関する成果は、情報理論における著名な未解決問題を解決したものであるが、そこで導入された2次形式による離散構造の表現は、のちに最適化分野の中心的トピックの一つとなった半正定値計画法の嚆矢となった。さらに、これらの二つの先駆的業績を発展させる形で、楕円体法によるアルゴリズム設計の幾何学的方法論の展開においてその一翼を担った。これにより、劣モジュラ関数最小化などの未解決問題が解決しただけでなく、計算理論と最適化理論の新たな関係が拓かれた。さらに、ロヴァース博士の局所補題などを通して、離散構造の解析に確率的手法を取り入れる枠組みを示すとともに、確率的検査可能証明の提案にも貢献した。また、マトロイドマッチングのアルゴリズムや、暗号理論を展開する際の基礎的道具の一つとなっている整数格子の基底簡略化アルゴリズム(いわゆるLLLアルゴリズム)などの構築に寄与している。

このように、ロヴァース博士は、アルゴリズム理論とその周辺諸分野を双方向的に往来することによって、両者の発展に寄与するとともに、計算による構成を切り口とした分野横断的な数理科学を推進した。

以上の理由によって、ラースロー・ロヴァース博士に基礎科学部門における第26回(2010)京都賞を贈呈する。

プロフィール

略歴
1948年
ハンガリー ブダペスト生まれ
1971年
エトヴェシュ・ロラーンド大学 博士号(自然科学)
1971年
エトヴェシュ・ロラーンド大学 助手
1975年
ヨーゼフ・アッティラ大学 講師
1977年
ハンガリー科学アカデミー 博士号(数理科学)
1978年
ヨーゼフ・アッティラ大学 教授
1983年
エトヴェシュ・ロラーンド大学 教授
1993年
イエール大学 教授
1999年
マイクロソフト・リサーチ 上級研究員
2006年
エトヴェシュ・ロラーンド大学 数学研究所 所長
主な受賞・栄誉
1979年
ジョージ・ポリヤ賞、応用数理学会
1982年
ファルカーソン賞、アメリカ数学会
1998年
ハンガリー共和国中十字勲章
1999年
ウルフ賞数学部門、ウルフ財団
2001年
ゲーデル賞、アメリカ計算機学会・ヨーロッパ理論コンピュータ学会
2007年
ボーヤイ・ヤーノシュ研究賞、ボーヤイ賞財団
2008年
セーチェーニ大賞、ハンガリー共和国政府
会員:
ヨーロッパ芸術科学人文アカデミー、ハンガリー科学アカデミー、ロンドン数学会、レオポルディナドイツ科学アカデミー、ロシア科学アカデミー、オランダ王立芸術科学アカデミー、スウェーデン王立科学アカデミー
主な論文
1972年
Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics 2: 253-267, 1972.
1975年
Problems and results on 3-chromatic hypergraphs and some related questions (Erdős, P. and Lovász, L.). in Infinite and Finite Sets, North Holland, Amsterdam, 609-627, 1975.
1979年
On the Shannon capacity of graphs. IEEE Transactions on Information Society 25: 1-7, 1979.
1981年
The ellipsoid method and its consequences in combinatorial optimization (Grötschel , M., Lovász, L., and Schrijver, A). Combinatorica 1: 169-197, 1981.
1982年
Factoring polynomials with rational coefficients (Lenstra, A. K., Lenstra, H.W., and Lovász, L.) Mathematische Annalen 261: 515-534, 1982.
1996年
Interactive proofs and the hardness of approximating cliques (Feige, U., Goldwasser, S., Lovász, L., Safra, S., and Szegedy, M.) Journal of the ACM 43: 268-292, 1996.

プロフィールは受賞時のものです

インタビュー映像