Loading article…
ランス・フォートナウ | |
|---|---|
| 生まれる | 1963年8月15日（年齢 61) |
| 国籍 | アメリカ人 |
| 母校 | コーネル大学 マサチューセッツ工科大学 |
| 知られている | インタラクティブな証明 |
| 受賞歴 | ACMフェロー、NSF大統領教員フェロー、フルブライト奨学生、ネロード賞 |
| 科学者としてのキャリア | |
| フィールド | コンピュータサイエンス |
| 機関 | イリノイ工科大学 ジョージア工科 大学 ノースウェスタン大学 シカゴ大学 |
| 博士課程の指導教員 | マイケル・シプサー |
| 博士課程の学生 | カーステン・ルンド |
| Webサイト | http://lance.fortnow.com/ http://blog.computationalcomplexity.org/ |
ランス・ジェレミー・フォートナウ（1963年8月15日生まれ）は、計算複雑性と対話型証明システムにおける主要な成果で知られるコンピュータ科学者である。彼はイリノイ工科大学のコンピューティング学部の学部長である。
バイオグラフィー
ランス・フォートナウは1989年にマイケル・シプサーの指導の下、 MITで応用数学の博士号を取得しました。 [1]卒業後はシカゴ大学（1989〜1999年、2003〜2007年）、ノースウェスタン大学（2008〜2012年）、ジョージア工科大学（2012〜2019年）で教鞭をとり、コンピュータサイエンス学部の学部長を務めました。[2] [3]
フォートナウは2009年に雑誌ACM Transactions on Computation Theoryの創刊編集長を務めた。[4]彼はACM SIGACT [5]の議長を務め、ポール・ビームが後を継いだ。彼は2000年から2006年までIEEE Conference on Computational Complexity [6]の議長を務めた。2002年に理論計算機科学に特化した最初のブログの1つを開始し[7]、それ以来ブログを書いている。2007年以来、彼には共同ブロガーのウィリアム・ガサーチがいる。2009年9月、フォートナウはCommunications of the Association for Computing MachineryにP対NP問題の進歩を調査した記事を発表し、複雑性理論に主流の注目を集めた。[8]
仕事
フォートナウは多くの出版物で計算複雑性の分野に重要な成果をもたらしました。MITの大学院生だったころ、フォートナウは多項式階層が崩壊しない限りNP完全言語には完全なゼロ知識プロトコルは存在しないことを示しました。 [9]また、マイケル・シプサーとともに、特定のオラクルに対して対話型プロトコルを持たないco-NP言語が存在することも実証しました。 [10]
1989 年 11 月、フォートナウは、co-NP には多重証明者対話型証明 (MIP) があることを示すNoam Nisanからの電子メールを受け取りました。Carsten Lundおよび Howard Karloff とともに、彼はこの結果を使用して対話型証明システムの構築のための代数的手法を開発し、多項式時間階層内のすべての言語に対話型証明システムがあることを証明しました。[11]彼らの研究が始まってわずか 2 週間で、Adi Shamir がその手法を使用してIP = PSPACE であることを証明しました。[12]これにすぐに追従して (1990 年 1 月 17 日、Nisan の電子メールを受け取ってから 2 か月も経たないうちに)、フォートナウはLászló Babaiおよび Carsten LundとともにMIP = NEXPであることを証明しました。[13]これらの代数的手法は、Fortnow、Babai、 Leonid Levin、およびMario Szegedyによってさらに拡張され、彼らは計算をチェックするための新しい一般的なメカニズムを提示しました。[14]
フォートナウは、デランダム化、スパース言語、オラクルマシンなど、計算複雑性の分野におけるさまざまなトピックについて論文を発表し続けており、量子コンピューティング、ゲーム理論、ゲノム配列、経済学についても論文を発表しています。
フォートナウの経済学の研究には、ゲーム理論、最適戦略、予測の研究が含まれる。デューク・ワンとともに、彼は囚人のジレンマという古典的なゲーム理論の問題を研究し、ジレンマが無限回連続して提示されるように問題を拡張した。彼らは、計算的に制限された集合から戦略を導き出し、復讐的な戦略の優位性を防ぐために「猶予期間」を導入するという制約を与えられたプレイヤーがどのような戦略を取るべきかを調査した。[15]フォートナウはまた、マーケットメーカーとともに対数市場スコアリングルール（LMSR）も研究した。彼は、LMSR価格設定が#P困難であることを示すのに貢献し、順列市場の価格設定の近似手法を提案した。[16]彼はまた、LMSRマーケットメーカーと協力する情報トレーダーの行動の研究にも貢献した。[17]
フォートナウは、 2009年にCACMに寄稿した論文を基にした人気科学書『The Golden Ticket: P, NP and the Search for the Impossible』[18]も執筆している。 [19]この本の中で、フォートナウはP対NP問題とそのアルゴリズムの限界について、技術的でない入門書を提供している。彼はさらに、データ懐疑論者のポッドキャストで、この本について説明し、なぜNP問題がそれほど重要なのかを説明している。[20]
受賞と栄誉
- 2007 ACMフェロー
- 1992年から1998年までNSF大統領教員フェロー
- 1996年と1997年にオランダのフルブライト奨学生として滞在
- 2014年ネロード賞
参考文献
- ^ 数学系譜プロジェクトのランス・フォートナウ
- ^ 「College of Computing Hires Fortnow, Anton to Lead Schools」（プレスリリース）ジョージア工科大学コンピューティング学部。2012年3月19日。 2012年10月4日閲覧。
- ^ ノースウェスタン大学電気工学・コンピュータサイエンス学部教授
- ^ ACM 計算理論トランザクション
- ^ ACM シグアクト
- ^ IEEE 計算複雑性会議
- ^ 計算複雑性ウェブログ
- ^ J. Markoff、「賞品はさておき、P-NP パズルには結果がある」ニューヨーク タイムズ、2009 年 10 月 7 日(購読が必要)
- L. Fortnow、「P 対 NP 問題の現状」、Communications of the ACM 9 (2009) - ^ L. Fortnow、「完全なゼロ知識の複雑さ」、S. Micali 編著、Randomness and Computation 、 Advances in Computing Research第 5 巻、327-343 ページ。JAI Press、グリニッジ、1989 年
- ^ L. Fortnow と M. Sipser、「共NP言語のための対話型プロトコルはあるか?」、Information Processing Letters、28:249-251、1988
- ^ C. Lund、L. Fortnow、H. Karloff、N. Nisan、「対話型証明システムのための代数的手法」、Journal of the ACM、39 (4):859-868、1992
- ^ A. シャミール、「IP = PSPACE」、ACM ジャーナル 39 (4):869-877、1992
- ^ L. Babai、L. Fortnow、C. Lund、「非決定性指数時間には2つの証明者対話型プロトコルがある」、Computational Complexity、1 (1):3-40、1991
- ^ L. Babai、L. Fortnow、L. Levin、M. Szegedy。「ポリログ時間での計算のチェック」、第 23 回 ACMコンピューティング理論シンポジウムの議事録、21 ～ 31 ページ。ACM、ニューヨーク、1991 年
- ^ L. Fortnow および D. Whang、「制限されたプレイヤーとの繰り返しゲームにおける最適性と支配」、第 26 回 ACM コンピューティング理論シンポジウムの議事録、741-749 ページ。ACM、ニューヨーク、1994 年
- ^ Y. Chen、L. Fortnow、N. Lambert、D. Pennock、J. Wortman、「Combinatorial Market Makers の複雑性」、第 9 回 ACM 電子商取引会議の議事録、190 ～ 199 ページ。ACM、ニューヨーク、2008 年
- ^ Y. Chen、S. Dimitrov、R. Sami、D. Reeves、D. Pennock、R. Hanson、L. Fortnow、および R. Gonen、「ゲーム予測市場: マーケットメーカーによる均衡戦略」、Algorithmica、2009 年
- ^ フォートナウ、ランス『黄金のチケット：P、NP、そして不可能の探求』、プリンストン大学出版、2013年
- ^ フォートナウ、ランス、「P対NP問題の現状」、Communications of the ACMのレビュー記事、52 (9): 78-86、2009年9月
- ^ 「P vs NP」、データ スケプティック、2017 年
外部リンク
- フォートナウのホームページ
- 出版物一覧