Loading article…
スタティス K. ザコス(ギリシャ語: Στάθης (Ευστάθιος) Ζάχος ; 1947 年アテネ生まれ) は、数学者、論理学者、理論計算機科学者です。
バイオグラフィー
ザコス氏は、1978年にスイス連邦工科大学チューリッヒ校（ ETHZ ）で数学（およびコンピュータサイエンス）の博士号を取得しました。カリフォルニア大学サンタバーバラ校、ニューヨーク市立大学ブルックリンカレッジ、アテネ国立工科大学でコンピュータサイエンスの教授を務め、ETHZでは非常勤講師も務めました。マサチューセッツ工科大学、ブラウン・ボベリ研究所の研究員としても勤務しました。
Stathis はコンピュータサイエンスのいくつかの分野で研究論文を発表しています。ランダム化複雑性クラス[1] [ 2]、 アーサー・マーリンプロトコル[3]、対話型証明システム[4]に関する 研究は、重要な定理の証明に大きな影響を与え、計算複雑性の主要な教科書[ 5] [6]で引用されています。[7]対話型証明システムと確率量指定子を使用した彼の重要な貢献の 1 つは、グラフ同型性の問題がNP 完全ではない可能性があることです(R. Boppana、J. Hastad との共同研究)。[8]グラフ同型性は、NP における非常に数少ない有名な問題のうち、NP 完全または P であることがまだ示されていない問題の 1 つです。 Zachos の最も影響力のある研究は、クラスParity-Pの特性の導入と証明でした( Christos Papadimitriouとの共同研究)。[9]彼はまた、確率量指定子と確率量指定子の交替を導入し、さまざまな複雑性クラスや対話型証明システム、確率ゲームを統一的に記述しました。[10]
彼の現在の関心は、確率的および関数的複雑性クラス、計算理論の基礎としての組合せ代数、暗号技術と計算複雑性の相互関係、およびグラフ問題のアルゴリズムなどです。彼は、STOC '87 (および STOC '01 のプログラミング委員会)、ICALP、CiE ( Computability in Europe )、PLS、ASL ( Association for Symbolic Logic ) European Summer Meeting、ACAC (Athens Colloquium on Algorithms and Complexity)、および NYCAC ( New York Colloquium on Algorithms and Complexity) などの国際会議を共同主催しました。
彼は理論物理学者コスマス・ザホスの兄弟である。
参照
参考文献
- ^ Zachos, Stathis (1982). 「定義的摂動下における確率的計算複雑性クラスの堅牢性」.情報と制御. 54 (3): 143–154. doi :10.1016/s0019-9958(82)80019-3.
- ^ Zachos, Stathis; Hans Heller (1986). 「BPPの決定的な特徴」.情報と制御. 69 (1–3): 125–135. doi : 10.1016/s0019-9958(86)80044-4 .
- ^ Zachos, Stathis; Martin Fürer (1987)。「確率的量指定子と不信感を持つ敵対者」。ソフトウェア技術と理論コンピュータサイエンスの基礎。コンピュータサイエンスの講義ノート。第 287 巻。pp. 443–455。doi : 10.1007/ 3-540-18625-5_67。ISBN 978-3-540-18625-0。
- ^ Fürer, Martin; Oded Goldreich; Yishay Mansour; Michael Sipser; Stathis Zachos (1989). 「対話型証明システムにおける完全性と健全性について」.コンピューティング研究の進歩: ランダム性と計算. 5 : 25–32. CiteSeerX 10.1.1.39.9412 .
- ^ Papadimitriou, Christos H. (1994).計算の複雑さ. Addison Wesley.
- ^ ヘマスパアンドラ、レーンA。荻原光則（2001）。複雑性理論のコンパニオン。スプリンガー。ISBN 978-3540674191。
- ^ 杜、丁珠; Ker-I Ko (2000)。計算複雑性の理論。ワイリー・インターサイエンス。
- ^ Boppana, Ravi B.; Hastad, Johan; Zachos, Stathis (1987年5月6日). 「co-NPは短い対話型証明を持つか?」Information Processing Letters . 25 (2): 127–132. doi :10.1016/0020-0190(87)90232-8.
- ^ Papadimitriou, Christos H.; Stathis Zachos (1982). 「カウントの力に関する 2 つのコメント」.理論計算機科学. 計算機科学の講義ノート. 第 145 巻. pp. 269–276. doi :10.1007/BFb0009651 (2024 年 11 月 1 日非アクティブ). ISBN 978-3-540-11973-9。
{{cite book}}:|journal=無視されました (ヘルプ)CS1 メンテナンス: DOI は 2024 年 11 月時点で非アクティブです (リンク) - ^ Zachos, Stathis (1988). 「確率的量指定子とゲーム」. Journal of Computer and System Sciences . 36 (3): 433–451. doi :10.1016/0022-0000(88)90037-2.
外部リンク
- アテネ国立工科大学のプロフィール