MacTutor

伝記

レスリー-ヴァリアントの両親はレスリー-ヴァリアントとエヴァ-ジュリア-ウジュラキであった。 イングランドで育ち、ノース-シールズのタインマス-ハイスクールに通っていた。 この学校はヴァリアントが去った数年後の1969年に改名され、ノーラム高校として知られるようになった。 ヴァリアントはロンドンのハマースミス、キングストリートにあるラティマー高等学校で学校教育を修了した。 これは、1624年にEdward Latymerによって設立された有名な選択的な独立した学校でした(そしてまだあります)。 ラティマー高等学校を卒業した後、彼はキングスカレッジ、ケンブリッジ大学で学び、その後、彼の最初の学位、数学の学士号の賞の後、彼は理論的なコンピ コンピュータサイエンスのインペリアル-カレッジの卒業証書を授与された後、ヴァリアントはウォリック大学に行き、マイケル-スチュワート-パターソンを顧問にしてコンピュータサイエンスの博士号の研究を行った。
博士号授与前 1973年から74年にかけて、ペンシルベニア州ピッツバーグのカーネギーメロン大学の客員助教授としてアメリカで過ごした。 彼は1974年にウォリック大学から決定論的プッシュダウンオートマトンの家族のための彼の論文の決定手順のための彼の博士号を授与されました。 ヴァリアントは論文アドバイザーのM S Patersonと共同で、1973年にボンのErste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachenòに論文決定論的な1対オートマトンを発表した。 Wilfried Brauerはこの論文をレビューし、次のように書いています:-

決定論的ワンカウンターオートマトン(doca)は、一要素スタックアルファベットを持つ決定論的プッシュダウンオートマトンです。 Docaの包含問題と交差点の無効性問題は決定不可能であることは容易にわかります。 これとは対照的に,著者らはdocaの等価性の決定手順を与え,その時間複雑度が検定されたdocaの状態数の平方根について指数関数関数によって上に制限されることを示した。

Valiantは1974年に論文the equivalence problem for deterministic finite-turn pushdown automataを発表した。 S A Greibachはこの論文の重要性を指摘している:-

プッシュダウンストアオートマトン(pda)は、任意の入力の計算中にプッシュ(プッシュダウンストアの長さを増加)からポップ(プッシュダウンストアの長さを減少させる)に切り替えることができる回数に一様な限界がある場合、有限ターンである。 著者は等価問題の決定可能性を確立する(二つのマシンは同じ言語を受け入れるのですか?)決定論的有限回転pdaのために。 結果の重要性は、それを確立するために使用される証明技術にあり、それが決定論的pda(dpda)の等価問題が決定可能であるという長い未解決の推測を解決するための主要なブレークスルーの一つを表しているという事実にある(対応する問題は、非常に限られた場合でも、非決定論的pdaのために決定不可能であることが知られている)。

1974年に米国から帰国した後、ヴァリアントはリーズ大学で講義を受け、1974年から1976年の二年間働いた。 私たちは彼の初期の論文の別の例を与えてみましょう,これは再びM Sパターソンと共同で書かれました,. この1975年の論文Deterministic one-counter automataは、以下の著者の紹介から始まります:-

我々は、それらの等価問題が決定可能であることを示すために、決定論的one-counter automataの分析を提示 私たちのすべての議論と結果は、スキーマ理論的用語に直接翻訳することができます。 その結果、Janovスキーマが補助カウンタを許可されている場合でも、等価性は決定可能であるという結果が得られます。

ヴァリアントは1975年にスコットランドに移り、エディンバラ大学で講義を受けた。 1977年にゲイル-リン-ダイコフと結婚し、二人の息子グレゴリー-ジョン-ヴァリアントとポール-ア-ヴァリアントがいる。 エディンバラで彼は1981年にリーダーに昇進したが、彼はハーバード大学の客員教授だった1982年に米国に行ってきました。 その年の後半、彼はハーバード大学の計算機科学と応用数学のゴードン-マッケイ教授に任命された。 1987年から1988年までイギリスのオックスフォード大学で客員研究員として過ごしたが、ハーバード大学に留まった。 2001年、ハーバード大学工学応用科学大学院の計算機科学と応用数学の教授に指名された。
ヴァリアントが行った貢献は非常に顕著であり、彼は彼の業績に対して最高の栄誉を受けています。 1985年から1986年にかけてグッゲンハイム-フェローに選出され、1986年にネヴァンリンナ賞を受賞した。 彼は1991年にロンドン王立協会のフェローに選出され、翌年にはアメリカ人工知能協会のフェローに選出された。 彼は1997年に計算機械協会アルゴリズムと計算理論に関する特別関心グループと計算の数学的基礎に関する電気電子工学技術者技術委員会からクヌース賞を受賞した。 2001年に全米科学アカデミーに選出され、欧州理論計算機科学協会賞を受賞し、2010年には計算機械協会のA Mチューリング賞を受賞し、2011年4月にカリフォルニア州サンノゼで開催された協会の年次賞バンケットでヴァリアントに贈られる。 この賞にはcash250,000の賞金も含まれています。
我々は、ヴァリアントが可能な限り最高の賞を受賞したことにつながった貢献については説明していない。 これを行うには、チューリング賞の発表に伴う解説から引用します(2011年の記事は、その解説からの引用の下で参照されています)。 解説が始まる:-

過去30年間、Leslie Valiantは理論計算機科学の多くの側面に基本的な貢献をしてきた。 彼の作品は、新しいフロンティアを開き、独創的な新しい概念を導入し、偉大な独創性、深さ、美しさの結果を提示しています。 何度も何度も、Valiantの仕事は文字通りコンピュータサイエンスの研究風景を定義または変換しました。

その後、Valiantが見事な貢献をしたいくつかの分野の詳細を説明します。

  1. 計算学習理論の四つの領域のそれぞれからいくつかの短い抜粋を与えます。 ヴァリアントの最大の貢献は、計算学習理論の基礎を築いた彼の論文”a theory of the learnable”(1984年)かもしれない。 … Valiantの”おそらくほぼ正しい”(PAC)モデルは、学習の概念そのもののための美しい基礎を提供しました。
  2. 列挙の複雑さ。 1970年代初頭には、計算の複雑さは、一般的に、グラフが完全なマッチングを持っているかどうか、または旅行のセールスマンが最大で一定の長さのルートを見つ … Valiantの最も注目すべき発見の一つは、カウントの問題が以前の経験が示唆したよりもはるかに微妙であるということです。 カウント問題は、いくつかの組み合わせオブジェクトの数を要求します:例えば、グラフにはいくつの完全一致がありますか? 私たちは、その数が正であるかどうかの決定問題だけでなく、それがどれくらい大きいかを尋ねています。 決定問題が難しい場合は、カウント問題も同様でなければなりませんが、Valiantの驚くべき実現は、逆が失敗するということでした。 彼の論文”the complexity of computing the permanent”(1979年)では、グラフが完全一致を持つかどうかを判断する効率的なアルゴリズムがあるが、(P=NPでない限り)完全一致を数える効率的なアルゴリズムは存在せず、実際には完全一致を数えることはどのようなカウント問題と同じくらい難しいことを示した。 これは、決定問題が問題の主要な特徴を容易に捉えるという考えに慣れていた計算複雑性コミュニティに衝撃を与えました。
  3. 代数計算。 計算の複雑さへのもう一つの重要な貢献は、彼が効率的に評価することができる代数式を理解するためのフレームワークを確立した代数計算のヴァリアントの理論であった。 … 彼の論文”Completeness classes in algebra”(1979年)では、Valiantは線形代数からの2つの基本的かつ密接に関連する関数、すなわち行列式と永久的な点で代数計算の難しさを特徴づけた。
  4. 並列および分散コンピューティング。 計算学習理論と計算複雑さに加えて、Valiantが重要な貢献をした第三の広い分野は、並列計算と分散計算の理論です。 ここでの彼の結果は、シンプルではあるが強力でエレガントな洞察から、非常に基礎を再検討するまでの範囲です。 簡単な洞察の例は、論文”高速並列通信のためのスキーム”(1982)に記載されている彼の並列ルーティングスキームです。

私たちは、チューリング賞の引用の結論を完全に引用することによって、この伝記を終了します:-

ヴァリアントの作品のように深さと幅のような印象的 彼は本当に理論的なコンピュータサイエンスの英雄的な人物であり、科学の最も深い未解決の問題のいくつかに対処する彼の勇気と創造性のロールモデルです。

コメントを残す

メールアドレスが公開されることはありません。