ジョセフ・F・トラウブ

ジョセフ・フレデリック・トラウブ（1932年6月24日 - 2015年8月24日）は、アメリカのコンピュータ科学者。コロンビア大学のコンピュータサイエンスのエドウィン・ハワード・アームストロング教授であり、サンタフェ研究所の外部教授でもあった。ベル研究所、ワシントン大学、カーネギーメロン大学、コロンビア大学で職を歴任し、また、スタンフォード大学、^{[3] 、}バークレー大学、プリンストン大学、カリフォルニア工科大学、ミュンヘン工科大学でも研究職を務めた。^[4]

トラウブは、コンピュータサイエンス、数学、物理学、金融、経済学の分野で10のモノグラフと約120の論文の著者または編集者でした。^[4] 1959年に彼は最適反復理論の研究を開始し、1964年のモノグラフ「方程式を解くための反復法」で最高潮に達しました。その後、ヘンリク・ウォジニャコフスキと協力し、連続的な科学的問題に適用される計算複雑性（情報ベースの複雑性）に関する研究を先駆的に進めました。彼は、多項式ゼロに対するジェンキンス-トラウブアルゴリズム、ショー-トラウブ、^{[2] [5]}クン-トラウブ、^[6]ブレント-トラウブアルゴリズムなどの重要な新しいアルゴリズムの作成に協力しました。彼の研究分野の1つは連続量子コンピューティングでした。^[7] 2015年11月10日現在、彼の作品は8500回引用されており、h指数は35です。 ^[8]

1971年から1979年まで、トラウブはカーネギーメロン大学の重要な時期にコンピュータサイエンス学部を率いた。1979年から1989年まで、コロンビア大学のコンピュータサイエンス学部の初代学部長を務めた。1986年から1992年まで、全米科学アカデミーのコンピュータサイエンスおよび電気通信委員会の初代委員長を務め、2005年から2009年まで同職を務めた。^[9]トラウブは、Annual Review of Computer Science（1986–1990）^{[10]の創刊編集者であり、} Journal of Complexity（1985–2015）^[11]の編集長も務めた。彼の研究と組織構築活動は、コンピュータサイエンスの分野に大きな影響を与えた。^[4]

トラウブはブロンクス科学高校に通い、チェスチームのキャプテンと第一理事を務めた。ニューヨーク市立大学を卒業後、1954年にコロンビア大学に入学し、物理学の博士号を取得する予定だった。1955年、同級生の勧めで、トラウブはコロンビア大学のIBMワトソン研究所を訪れた。当時、ここは学生がコンピューターを利用できる国内でも数少ない場所の1つだった。トラウブは、アルゴリズム的思考の能力がコンピューターと完全に一致していることに気付いた。1957年、コロンビア大学のワトソンフェローになった。論文は計算量子力学に関するものだった。 1959年の博士号は応用数学で、コンピューターサイエンスの学位はまだ取得できなかったためである（実際、コロンビア大学にはコンピューターサイエンス学部は存在せず、1979年にトラウブが招かれて学部を設立した）。^{[12] [4]}

1959 年、トラウブはニュージャージー州マレーヒルのベル研究所の研究部門に加わった。ある日、同僚が彼に、ある問題の解を計算する方法を尋ねた。トラウブはその問題を解くいくつかの方法を思いついた。最適なアルゴリズム、つまり必要な計算リソースを最小化する方法は何か。驚いたことに、最適なアルゴリズムの理論は存在しなかった。(計算上の問題を解決するのに必要な最小限のリソースの研究である計算複雑性という用語は、1965 年まで導入されていなかった。) トラウブは、連続問題を解くための最適なアルゴリズムは利用可能な情報に依存するという重要な洞察を持っていた。これは、最終的に情報ベースの複雑性の分野につながることになる。トラウブがその洞察を適用した最初の分野は、非線形方程式の解であった。この研究は、1964 年のモノグラフ「方程式の解法のための反復法」につながった。^{[12] [6]} これは現在も印刷されている。^[13]

1966年、トラウブはスタンフォード大学で1年間の休暇を過ごし、そこでマイケル・ジェンキンスという学生と出会った。2人は一緒に多項式零点を求めるジェンキンス・トラウブアルゴリズムを開発し、ジェンキンスの博士論文として出版された。このアルゴリズムは今でもこの問題に対する最も広く使われている方法の1つであり、多くの教科書に掲載されている。^{[14] [1]}

1970年にトラウブはワシントン大学の教授となり、1971年にはカーネギーメロン大学のコンピュータサイエンス学部長に就任した。^{[15]学部はかなり小規模だったが、それでも}アレン・ニューウェルやハーバート・A・サイモンなどの「巨人」がいた。1978年までに、トラウブのリーダーシップの下、学部は50名ほどの教員と研究者を抱えるまでに成長した。^[16]

トラウブの博士課程の学生の一人に、現在ハーバード大学の教授であるHT・クンがいた。彼らは代数関数の展開を計算するためのクン・トラウブアルゴリズムを考案した。彼らは、最初の項を計算することは2つの次多項式を掛け合わせることよりも難しくないことを示した。 ^{[6] [17] [18]}${\displaystyle N}$${\displaystyle N}$

1973年、トラウブはヘンリク・ウォジニャコフスキーをCMUに招待した。^[1]二人は情報ベース複雑性の分野を切り開き、3つのモノグラフと多数の論文を共著した。ウォジニャコフスキーはコロンビア大学とポーランドのワルシャワ大学の教授となった。^[19]

1978年、バークレーで休暇を取っていた彼はピーター・リキンスにスカウトされ、コロンビア大学のコンピュータサイエンス学部の初代学部長およびエドウィン・ハワード・アームストロング・コンピュータサイエンス教授に就任した。彼は1979年から1989年まで学部長を務めた。^[20]

1980年に彼はウォジニャコフスキーと共著で『最適アルゴリズムの一般理論』を執筆した。これは情報ベースの複雑性に関する最初の研究モノグラフであった。^[21]グレッグ・ワシルコフスキーはトラウブとウォジニャコフスキーと共に、さらに2つのモノグラフ『情報、不確実性、複雑性』（アディソン・ウェズリー、1983年）^[22]と『情報ベースの複雑性』（アカデミック・プレス、1988年）を執筆した。^[23]

1985年、トラウブはJournal of Complexityの創刊編集長に就任した。^{[2] [24]これはおそらく、}計算複雑性という意味での複雑性をタイトルに使った最初の雑誌であった。^[25]

1986年、トラウブは全米科学アカデミーからコンピュータサイエンス委員会の設立を依頼された。委員会の当初の名前はコンピュータサイエンスおよびテクノロジー委員会 (CSTB) であった。数年後、CSTB は電気通信についても責任を負うよう求められたため、略称 CSTB はそのままに、コンピュータサイエンスおよび電気通信委員会に改名された。委員会はコンピュータサイエンスと電気通信における重要な国家的問題を扱っている。トラウブは 1986 年から 1992 年まで創設委員長を務め、2005 年から 2009 年までその職を務めた。^[12]

1990年、トラウブはサンタフェ研究所（SFI）のサマースクールで教鞭を執った。以来、彼はSFIで様々な役割を果たしてきた。^{[2] 1990年代には、}アルフレッド・P・スローン財団の資金援助を受けて、科学的知識の限界に関する一連のワークショップを組織した。その目的は、ゲーデルとチューリングによる数学の限界に関する研究が科学を豊かにしたのと同じように、科学を豊かにすることだった。物理学、経済学、地球物理学など、様々な分野で限界に関する一連のワークショップが開催された。^[26]

1991年からトラウブはドイツのダグシュトゥール城で「連続アルゴリズムと複雑性」に関する国際セミナーの共同主催者を務めた。セミナーの講演の多くは情報ベースの複雑性に関するもので、最近では連続量子コンピューティングに関するものであった。^[27]

トラウブはイタリアのローマにある国立リンチェ音楽院に招かれ、1993年にリンチェ音楽院の講義を行った。^{[12]彼はピサの}師範学校で6回の講義を行うことを選択した。彼はアーサー・ウェルシュルツを招き、講義の出版に協力してもらった。講義は拡大版として『複雑性と情報』（ケンブリッジ大学出版、1998年）として出版された。^{[28] [29]}

1994年に彼は博士課程の学生スパシミール・パスコフに、トラウブがゴールドマン・サックスから入手した担保付住宅ローン債務（CMO）を計算する際のモンテカルロ法（MC）と準モンテカルロ法（QMC）を比較するように依頼した。これは、360次元における多数の積分の数値近似を伴った。研究グループを驚かせたのは、この問題ではQMCが常にMCに勝るとパスコフが報告したことだった。金融関係者はこうした問題に常にMCを使用しており、数論の専門家は12次元を超える積分にはQMCを使用するべきではないと信じていた。パスコフとトラウブは、当初はかなり懐疑的だったが、ウォール街の複数の企業に結果を報告した。彼らは1995年に初めてその結果を発表した。^{[30] [31] [32]理論とソフトウェアはアナルギロス・パパゲオルギウによって大幅に改良された。今日、QMCは}金融派生商品 を評価するのに金融セクターで広く使用されている。 QMCはすべての高次元積分に対する万能薬ではありません。^[33] QMCがMCよりも優れている問題の特徴づけに関する研究が継続されています。

1999年、トラウブは科学技術部門でニューヨーク市長賞を受賞しました。この賞の授与はニューヨーク科学アカデミーが行います。このメダルはグレイシーマンションで行われた式典でルディ・ジュリアーニ市長から授与されました。^[4]

トラウブと彼の同僚は、連続量子コンピューティングにも取り組んできた。ムーアの法則は、チップ上の機能の数が約18か月ごとに2倍になるという経験的観察である。これは60年代初頭から成り立っており、コンピュータと通信の革命の原因となっている。ムーアの法則は、シリコン技術を使用すると10〜15年で成立しなくなると広く信じられている。そのため、新しい技術を生み出すことに関心が集まっている。1つの候補は量子コンピューティングである。これは、量子力学の原理を使用してコンピュータを構築することである。その動機は、物理科学、工学、数理金融のほとんどの問題に連続的な数学モデルがあることである。^[34]

2005年にトラウブはカーネギーメロン大学図書館にアーカイブ資料を寄贈した。このコレクションはデジタル化されている。^[4]

米国特許US5940810およびUS0605837は、FinDerソフトウェアシステムに関してトラウブらに発行され、コロンビア大学に譲渡されました。これらの特許は、よく知られた技術（低矛盾シーケンス）をよく知られた問題（証券の評価）に適用したものです。^[35]

トラウブにはクラウディア・トラウブ・クーパーとヒラリー・スペクターという二人の娘がいた。彼は妻で作家のパメラ・マコーダックとともにマンハッタンとサンタフェに住んでいた。彼はニューヨーク・タイムズに寄稿して時事問題について意見を述べることが多く、同紙は彼のコメントを頻繁に掲載した。^{[36] [37]}

• 全米アカデミーズコンピュータサイエンスおよび電気通信委員会創設委員長、1986–92、2005–2009 ^[9]
• アレクサンダー・フォン・フンボルト財団優秀上級科学者賞、1992年、1998年^[9]
• 1993年 レジオーネ・リンセ、国立アカデミア・ナツィオナーレ・デイ・リンセイ、ローマ、イタリア^[12]
• ソ連、モスクワ、科学アカデミー幹部会講演 1990年
• 1989年、ポーランド教育省より研究論文「情報に基づく複雑性」で最優秀賞を受賞
• IEEEエマニュエル・R・ピオーレ賞– ^[38]
  1991年「アルゴリズムの複雑性、反復理論、並列性に関する先駆的な研究と、コンピューティング教育におけるリーダーシップに対して。」
  
• ニューヨーク科学アカデミー理事会、1986-89年（執行委員会1987-89年）^[39]
• フェロー：アメリカ科学振興協会、1971年; ^[40] ACM 1994年;ニューヨーク科学アカデミー、1999年;アメリカ数学会、2012年^[41]
• 1999年ニューヨーク市長科学技術優秀賞^[4]
• ジョゼフ・F・トラウブのための祝典、アカデミック・プレス、1993年
• ジョゼフ・F・トラウブのための祝典、エルゼビア、2004
• セントラルフロリダ大学名誉理学博士号、2001年
• 1985年ジャーナル・オブ・コンプレキシティ創刊編集長^[2]

• 方程式の解法のための反復法、Prentice Hall、1964年。Chelsea Publishing Company、1982年に再発行。ロシア語訳MIR、1985年。American Mathematical Society、1998年に再発行。
• アルゴリズムと複雑性：新しい方向性と最近の結果、（編集者）Academic Press、1976年。
• Information-Based Complexity、Academic Press、1988年（G. WasilkowskiおよびH. Woźniakowskiとの共著）。
• 複雑性と情報、ケンブリッジ大学出版局、1998年（AG Werschulzとの共著）、日本語訳、2000年。

• ヘリウムの状態の変分計算${\displaystyle 2^{3}P}$、Phys. Rev. 116、1959、914–919。
• 科学雑誌の未来、サイエンス158、1966年、1153-1159（WSブラウン、JRピアスと共著）。
• 多項式零点に対する3段階変数シフト反復法と一般化レイリー反復法との関係、Numerische mathematik 14、1970、252–263（MA Jenkinsと共著）。
• 反復プロセスの計算複雑性、SIAM Journal on Computing 1、1972、167–179。
• 並列アルゴリズムと並列計算の複雑さ、Proceedings IFIP Congress、1974、685–687。
• 演算子方程式のニュートン反復法の収束と計算量、Journal of the ACM 26、1979、250–258（H. Woźniakowskiと共著）。
• すべての代数関数は高速に計算できる、Journal of the ACM 25、1978、245–260（HT Kungと共著）。
• 合成の複雑さとべき級数の一般化合成について、SIAM Journal on Computing 9、1980、54–66 (R. Brent と共著)。
• 線形計画法の複雑性、Operations Research Letters 1、1982、59–62（H. Woźniakowskiと共著）。
• 情報ベースの複雑性、Nature 327、1987年7月、29-33ページ（E. Packelと共著）。
• 擬似乱数ジェネレータを使用したモンテカルロアルゴリズム、計算数学58、199、303–339（H. Woźniakowskiと共著）。
• Breaking Intractability、Scientific American、1994年1月、102-107（H. Woźniakowskiとの共著）。ドイツ語、イタリア語、日本語、ポーランド語に翻訳。
• 線形不適切問題はすべてのガウス測度について平均で解ける、Math Intelligencer 16、1994、42–48 (AG Werschulz と共著)。
• 金融デリバティブの高速評価、ポートフォリオ管理ジャーナル22、1995年、113-120（S. Paskovと共著）。
• 計算の連続モデル、Physics Today、1999年5月、39-43ページ。
• 最悪のケースにおける収縮固定点には次元の呪いはない、Econometrics、第70巻、第1号、2002年1月、285-329ページ（J. RustおよびH. Woźniakowskiとの共著）。
• 量子コンピュータ上のパス積分、量子情報処理、2003年、365-388ページ（H. Woźniakowskiとの共著）。

• ジョセフ・トラウブのコロンビアホームページ
• カーネギーメロン大学のジョセフ・トラウブデジタルアーカイブ
• 研究論文「複雑性と情報」
• ジョセフ F. トラウブ氏への口述歴史インタビュー、1984 年 4 月、1984 年 10 月、1985 年 3 月、ミネソタ大学チャールズ バベッジ研究所にて。
• SIAM オーラルヒストリー
• CMU 特別講演ビデオ
• CMU 50周年記念ビデオ