2010年基礎科学部門数理科学(純粋数学を含む)
ラースロー・ロヴァース 写真

ラースロー・ロヴァース
(László Lovász)

  • ハンガリー・アメリカ / 1948年3月9日
  • 数学者
  • エトヴェシュ・ロラーンド大学 教授

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

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

プロフィール

略歴

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.

贈賞理由

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

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

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

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

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

記念講演

記念講演要旨

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

私が現在の主たる研究テーマであるグラフ理論に出会ったのは高校生の時でした。私は、幸運にも高等学校に新しく設置された数学の特別クラスに入ることができました。そこでは、多くの優秀な生徒(その中には現在の私の妻もいましたが)に知り合っただけでなく、かの有名な数学者、ポール・エルデシュ先生が何度か学校に来られたのです。先生は生徒たちに未解決の難問を与えたのですが、私は1問か2問を解くことができました。それがきっかけとなって、私の生涯にわたるグラフ理論と数学研究との関わりが始まりました。当時、グラフ理論は、数学の「主流」からは隔離されたような分野でしたので、のちになって、先輩の数学者からは、もっと重要なことをやるべきだと、たびたび忠告されました。それでも、私は、学問分野の新しさと、その応用の可能性に魅了されていました。

学生時代の終わりころには、オペレーションズ・リサーチとグラフ理論の強い関係に関心を抱くようになりました。私はパーフェクト・グラフに関するある問題を解きましたが、その解法は、整数計画法の興味深い結果をもたらし、多面体へとつながりました。私は、グラフ理論と、最適化と、そして幾何学との間の関係が非常に実り多いものであることを幾度となく確認しました。

その後まもなく、私は、新しい理論であるアルゴリズム的複雑さを学びました。それはグラフ理論に多くの結果をもたらしました。これにより、私は、計算理論とその数学的基盤である(グラフ理論を含む)離散数学が共に素晴らしい発展を遂げていく目撃者(そして、少しはその当事者)になりました。

グラフ理論は、また、新しい理論とは反対方向にある伝統的数学とも関連があります。そして、私は、グラフ理論の問題を解くための伝統的数学の手法の問題に魅了されました。例えば、代数学、トポロジー、幾何学、そして確率論が、興味深い手法でグラフ理論に適用できる分野です。

最近では、私は、(インターネットのような)巨大ネットワークの理論に関心を持つようになりました。これは、グラフ理論に新たな進展を生み、ここでは伝統的数学の今以上の分野が必要とされるようになります。私は、学生時代に習って以来、疎遠となっていた分野を改めて学ばなければならないのですが、それを大いに楽しんでいます。

【関連情報】
記念講演録(PDF)
ワークショップ

ワークショップ

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

Mathematical Development of Algorithm Science

日時
平成22年11月12日(金)13:00~17:20
場所
国立京都国際会館
企画・司会
室田 一雄 [(専門委員会 委員)東京大学 大学院情報理工学系研究科 教授]
主催
財団法人 稲盛財団
後援
京都府、京都市、NHK
協賛
情報処理学会、電子情報通信学会、日本オペレーションズ・リサーチ学会、日本応用数理学会、日本数学会(五十音順)

プログラム

13:00
開会挨拶 広中 平祐[(審査委員会 委員長)京都大学 名誉教授]
受賞者紹介 今井 浩[(専門委員会 委員)東京大学 大学院情報理工学系研究科 教授]
受賞者講演 ラースロー・ロヴァース[基礎科学部門 受賞者]
「巨大ネットワークにおける数学的課題」
講演 徳山 豪[東北大学 大学院情報科学研究科 教授]
「組合せ幾何学:幾何学データ処理のための数学」
講演 渡辺 治[東京工業大学 大学院情報理工学研究科 教授]
「計算世界観とLovász Local Lemma」
講演 岩田 覚[京都大学 数理解析研究所 教授]
「組合せ最適化における凸性」
講演 河原林 健一[国立情報学研究所 教授]
「グラフ理論における構造定理と分解定理」
17:20
閉会
PAGETOP