Stathis K. Zachos ( Griechisch : Στάθης (Ευστάθιος) Ζάχος ; geboren 1947 in Athen) ist ein Mathematiker, Logiker und theoretischer Informatiker.

Biographie

Zachos promovierte 1978 an der ETH Zürich in Mathematik (und Informatik). Er war Professor für Informatik an der University of California, Santa Barbara , am Brooklyn College der City University of New York und an der Nationalen Technischen Universität Athen sowie Gastprofessor an der ETH Zürich . Er forschte außerdem am Massachusetts Institute of Technology (MIT) und am Brown-Boveri- Institut .

Stathis hat Forschungsarbeiten in verschiedenen Bereichen der Informatik veröffentlicht. Seine Arbeiten zu randomisierten Komplexitätsklassen [ 1 , 2 ] , Arthur-Merlin-Protokollen [ 3 ] und interaktiven Beweissystemen [ 4 ] waren maßgeblich für den Beweis wichtiger Theoreme und werden in Standardlehrbüchern der Komplexitätstheorie zitiert [ 5 , 6 , 7 ] . Ein wichtiger Beitrag von ihm ist der Nachweis, dass das Graphisomorphieproblem wahrscheinlich nicht NP-vollständig ist (gemeinsam mit R. Boppana und J. Hastad) [ 8 ] . Dabei verwendete er interaktive Beweissysteme und probabilistische Quantoren. Graphisomorphie ist eines der wenigen bekannten Probleme in NP, für die bisher weder NP-vollständig noch P-vollständig bewiesen wurde. Zachos' einflussreichste Arbeit war die Einführung und der Beweis der Eigenschaften der Klasse Parity-P (gemeinsam mit Christos Papadimitriou ). [ 9 ] Er führte außerdem probabilistische Quantoren und Alternationen probabilistischer Quantoren ein, um verschiedene Komplexitätsklassen sowie interaktive Beweissysteme und probabilistische Spiele einheitlich zu beschreiben. [ 10 ]

Zu seinen aktuellen Forschungsinteressen zählen probabilistische und funktionale Komplexitätsklassen , kombinatorische Algebren als Grundlage der Berechnungstheorie , die Zusammenhänge zwischen kryptographischen Techniken und Berechnungskomplexität sowie Algorithmen für Graphprobleme . Er war Mitorganisator internationaler Konferenzen wie STOC '87 (und Mitglied des Programmkomitees von STOC '01), ICALP , CiE ( Computability in Europe ), PLS, ASL ( Association for Symbolic Logic ) European Summer Meeting, ACAC (Athens Colloquium on Algorithms and Complexity) und NYCAC (New York Colloquium on Algorithms and Complexity).

Er ist der Bruder des theoretischen Physikers Cosmas Zachos .

Siehe auch

Referenzen

  1. ^ Zachos, Stathis (1982). „Robustheit probabilistischer Komplexitätsklassen unter Definitionsstörungen“. Information and Control . 54 (3): 143–154 . doi : 10.1016/s0019-9958(82)80019-3 .
  2. ^ Zachos, Stathis; Hans Heller (1986). „Eine entscheidende Charakterisierung von BPP“ . Information and Control . 69 ( 1–3 ): 125–135 . doi : 10.1016/s0019-9958(86)80044-4 .
  3. ^ Zachos, Stathis; Martin Fürer (1987). „Probabilistische Quantoren vs. Misstrauische Gegner“. Grundlagen der Softwaretechnologie und der Theoretischen Informatik . Lecture Notes in Computer Science. Band 287. S.  443–455 . doi : 10.1007/3-540-18625-5_67 . ISBN 978-3-540-18625-0Die
  4. ^ Fürer, Martin; Oded Goldreich; Yishay Mansour; Michael Sipser; Stathis Zachos (1989). „Über Vollständigkeit und Korrektheit in interaktiven Beweissystemen“. 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, Spur A.; Mitsunori Ogihara (2001). Der Begleiter zur Komplexitätstheorie . Springer. ISBN 978-3540674191Die
  7. ^ Du, Ding-Zhu; Ker-I Ko (2000). Theorie der rechnerischen Komplexität . Wiley-Interscience.
  8. ^ Boppana, Ravi B.; Hastad, Johan; Zachos, Stathis (6. Mai 1987). „Hat co-NP kurze interaktive Beweise?“. Information Processing Letters . 25 (2): 127–132 . doi : 10.1016/0020-0190(87)90232-8 .
  9. ^ Papadimitriou, Christos H.; Stathis Zachos (1982). „Zwei Bemerkungen zur Leistungsfähigkeit des Zählens“. Theoretische Informatik . Lecture Notes in Computer Science. Band 145. S.  269–276 . doi : 10.1007/BFb0009651 (zuletzt verfügbar seit 12. Juli 2025). ISBN 978-3-540-11973-9Die{{cite book}}: |journal=ignoriert ( Hilfe )CS1 maint: DOI inactive as of July 2025 (link)
  10. ^ Zachos, Stathis (1988). „Probabilistische Quantoren und Spiele“. Journal of Computer and System Sciences . 36 (3): 433–451 . doi : 10.1016/0022-0000(88)90037-2 .