스타티스 자코스

Stathis Zachos

Stathis K. Zachos(그리스어: στάηηη ( ( () (χςςς; 1947년 아테네 출생)은 수학자, 논리학자, 이론 컴퓨터 과학자다.

전기

자코스는 1978년 수학(및 컴퓨터 과학)의 ETHZ(스위스 연방 기술 연구소)에서 박사학위를 받았다. 그는 UCSB, CUNY, NTUA의 컴퓨터 사이언스 교수, ETHZ의 보조 교수직을 역임했다. 그는 브라운-보베리 MIT에서 연구원으로 일해왔다.

Stathis는 컴퓨터 과학의 여러 분야에 대한 연구 논문을 발표했다. 랜덤화 복잡성 클래스, [1][2]Arthur-Merlin Games [3]및 Interactive Proof[4] Systems에 대한 그의 연구는 중요한 이론들을 입증하는 데 큰 영향을 미쳤으며 계산 복잡성의 주요 교과서에 인용되어 있다.[5][6][7] 대화형 증명 시스템과 확률론적 정량자를 사용한 그의 중요한 기여 중 하나는 그래프 이형성 문제가 NP-완전성이 아닐 가능성이 낮다는 것이다(R과 공동). 보파나, J. 헤스타드).[8] Graph Isomorphism은 NP-Complete 또는 P Zachos의 가장 영향력 있는 작업은 Parity-P(Christos Papadimitriou와 함께) 등급의 속성을 소개하고 증명하는 것이었다.[9] 그는 또한 다양한 복잡성 등급과 대화형 증명 시스템 및 확률론적 게임들을 균일하게 기술하기 위해 확률론적 정량기와 확률론적 정량자의 교체를 도입했다.[10]

그의 현재 관심사는 확률론적 및 기능적 복잡성 클래스, 연산 이론의 기초가 되는 조합적 알제브라스, 암호 기법과 계산 복잡성의 상호연결, 그래프 문제를 위한 알고리즘 등이다. He has co-organized International Conferences: STOC '87 (and programming committee of STOC '01), ICALP, CiE (Computability in Europe), PLS, ASL (Association for Symbolic Logic) European Summer Meeting, ACAC (Athens Colloquium on Algorithms and Complexity) and NYCAC (New York Colloquium on Algorithms and Complexity).

그는 이론 물리학자 코스마스 자초스의 형이다.

참고 항목

참조

  1. ^ Zachos, Stathis (1982). "Robustness of probabilistic computational complexity classes under definitional perturbations". Information and Control. 54 (3): 143–154. doi:10.1016/s0019-9958(82)80019-3.
  2. ^ Zachos, Stathis; Hans Heller (1986). "A decisive characterization of BPP". Information and Control. 69 (1–3): 125–135. doi:10.1016/s0019-9958(86)80044-4.
  3. ^ Zachos, Stathis; Martin Fürer (1987). Probabilistic quantifiers vs. distrustful adversaries. Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 287. pp. 443–455. doi:10.1007/3-540-18625-5_67. ISBN 978-3-540-18625-0.
  4. ^ Fürer, Martin; Oded Goldreich; Yishay Mansour; Michael Sipser; Stathis Zachos (1989). "On completeness and soundness in interactive proof systems". Advances in Computing Research: Randomness and Computation. 5: 25–32. CiteSeerX 10.1.1.39.9412.
  5. ^ Papadimitriou, Christos H. (1994). Computational Complexity. Addison Wesley.
  6. ^ Hemaspaandra, Lane A.; Mitsunori Ogihara (2001). The Complexity Theory Companion. Springer. ISBN 978-3540674191.
  7. ^ Du, Ding-Zhu; Ker-I Ko (2000). Theory of Computational Complexity. Wiley-Interscience.
  8. ^ Boppana, Ravi B.; Hastad, Johan; Zachos, Stathis (6 May 1987). "Does co-NP have short interactive proofs?". Information Processing Letters. 25 (2): 127–132. doi:10.1016/0020-0190(87)90232-8.
  9. ^ Papadimitriou, Christos H.; Stathis Zachos (1982). "Two remarks on the power of counting". In Proceedings of the 6th GI-Conference on Theoretical Computer Science. Lecture Notes in Computer Science. 145: 269–276. doi:10.1007/BFb0009651. ISBN 978-3-540-11973-9.
  10. ^ Zachos, Stathis (1988). "Probabilistic quantifiers and games". Journal of Computer and System Sciences. 36 (3): 433–451. doi:10.1016/0022-0000(88)90037-2.

외부 링크