ピーター・ガックス

ペーテル・ガックス（ハンガリー語発音: ['pe:ter 'ga:tʃ]、1947年5月9日生まれ）は、職業上はピーター・ガックスとしても知られるハンガリー系アメリカ人の 数学者、コンピュータ科学者、教授であり、ハンガリー科学アカデミーの外部会員である。彼は、信頼性の高い計算、計算におけるランダム性、アルゴリズムの複雑性、アルゴリズムの確率、情報理論に関する研究でよく知られている。

ピーター・ガックスは故郷の高校に通い、1970年にブダペストのロラーンド・エトヴェシュ大学で修士号を取得した。ガックスはハンガリー科学アカデミー応用数学研究所の研究員としてキャリアをスタートさせた。^{[1] 1978年に}フランクフルト・ゲーテ大学で博士号を取得した。研究中はモスクワ国立大学を訪れ、アンドレイ・コルモゴロフとその学生レオニード・A・レヴィンのもとで研究する機会を得た。1979年までスタンフォード大学の客員研究員を務めた。1980年から1984年までロチェスター大学の助教授を務め、その後ボストン大学に移り、1985年に終身在職権を得た。1992年からは教授を務めている。^[2]

ガックスはコンピュータサイエンスの多くの分野で貢献してきました。 1979年8月に楕円体法の証明といくつかの改良を発表し、初めて国際社会の注目を集めたのはガックスとラスロー・ロヴァースでした。 ^{[3] [4] [5]ガックスは}シプサー・ラウテマンの定理にも貢献しました。^[6]彼の主な貢献と研究の焦点は、セルオートマトンとコルモゴロフ複雑性に集中していました。

GKL規則（ガッツ・クルデュモフ・レビン規則）の他にセルオートマトン分野における彼の最も重要な貢献は、信頼性の高い1次元セルオートマトンの構築であり、これにより正率予想に対する反例が提示された。^[7] 彼が提案した構築は、マルチスケールかつ複雑である。^[8]後に、同じ手法が非周期タイリングセットの構築に使用された。^[9]

ガックスは、アルゴリズム情報理論の分野とコルモゴロフ複雑性に関する重要な論文をいくつか執筆した。レオニード・A・レビンとともに、ペアの複雑性の公式^[10]や、後に再発見され、現在では十分過剰補題として知られている結果を含むランダム性欠陥の公式など、プレフィックス複雑性の基本特性を確立した。^{[11] [12]}彼は、プレフィックス複雑性に当てはまる複雑性と事前確率の対応は、単調複雑性と連続事前確率には当てはまらないことを示した。^{[13] [14]}関連するアルゴリズムランダム性理論では、すべてのシーケンスがランダムなシーケンスにチューリング還元可能であることを証明した（この結果は、アントニン・クチェラによって独立に証明されたため、現在ではガックス・クチェラ定理として知られている）。^[14]その後、彼は（共著者とともに）アルゴリズム距離の概念を導入し、条件付き複雑性との関連性を証明した。^{[15] [14]}

彼はアルゴリズム統計学の先駆者の一人であり、^[16]アルゴリズムの複雑性の量子バージョンの一つを導入し、^[17]一般空間^{[18] [19]}および一般測度のクラス^[20 ] に対するアルゴリズムのランダム性の特性を研究した。これらの結果のいくつかは、彼のアルゴリズム情報理論の調査で取り上げられている。^{[21] [22]}彼はまた、古典的情報理論とアルゴリズム情報理論の境界に関する結果を証明した。共通情報量と相互情報量の違いを示す画期的な例である（ヤノシュ・ケルナーと共著）。^[23]ルドルフ・アールスヴェーデおよびケルナー と共著で、彼は爆発の補題を証明した。^[24]