Zachos received his PhD from the ETHZ (Swiss Federal Institute of Technology Zurich) in Mathematics (and Computer Science), 1978. He has held the posts of professor in Computer Science at UCSB, CUNY and NTUA and Adjunct professor at ETHZ. He has worked as a researcher at MIT, Brown-Boveri.
Stathis has published research papers in several areas of Computer Science. His work on Randomized Complexity Classes,[1][2]Arthur–Merlin Games,[3] and Interactive Proof Systems[4] has been very influential in proving important theorems and is cited in main textbooks of computational complexity.[5][6][7] One of his important contributions, using Interactive Proof Systems and Probabilistic Quantifiers, is that the Graph Isomorphism Problem is not likely to be NP-complete (joint with R. Boppana, J. Hastad).[8] Graph Isomorphism is one of the very few celebrated problems in NP that have not been shown yet to be either NP-Complete or in P. Zachos's most influential work was introducing and proving properties of the class Parity-P (with Christos Papadimitriou).[9] He also introduced Probabilistic Quantifiers and Alternations of Probabilistic Quantifiers to uniformly describe various Complexity Classes as well as Interactive Proof Systems and Probabilistic Games.[10]
His current interests include Probabilistic and Functional Complexity Classes, Combinatory Algebras as a foundation to Theory of Computations, the interconnections of Cryptographic Techniques and Computational Complexity as well as Algorithms for Graph Problems. 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).
He is the brother of theoretical physicist Cosmas Zachos.
^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.
^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.
^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. ISBN978-3-540-18625-0.
^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. CiteSeerX10.1.1.39.9412.
^Papadimitriou, Christos H. (1994). Computational Complexity. Addison Wesley.
^Hemaspaandra, Lane A.; Mitsunori Ogihara (2001). The Complexity Theory Companion. Springer. ISBN978-3540674191.
^Du, Ding-Zhu; Ker-I Ko (2000). Theory of Computational Complexity. Wiley-Interscience.
^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.
^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. ISBN978-3-540-11973-9.
^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.
stathis, zachos, stathis, zachos, greek, Στάθης, Ευστάθιος, Ζάχος, born, 1947, athens, mathematician, logician, theoretical, computer, scientist, contents, biography, also, references, external, linksbiography, editzachos, received, from, ethz, swiss, federal,. Stathis K Zachos Greek Sta8hs Eysta8ios Zaxos born 1947 in Athens is a mathematician logician and theoretical computer scientist Contents 1 Biography 2 See also 3 References 4 External linksBiography EditZachos received his PhD from the ETHZ Swiss Federal Institute of Technology Zurich in Mathematics and Computer Science 1978 He has held the posts of professor in Computer Science at UCSB CUNY and NTUA and Adjunct professor at ETHZ He has worked as a researcher at MIT Brown Boveri Stathis has published research papers in several areas of Computer Science His work on Randomized Complexity Classes 1 2 Arthur Merlin Games 3 and Interactive Proof Systems 4 has been very influential in proving important theorems and is cited in main textbooks of computational complexity 5 6 7 One of his important contributions using Interactive Proof Systems and Probabilistic Quantifiers is that the Graph Isomorphism Problem is not likely to be NP complete joint with R Boppana J Hastad 8 Graph Isomorphism is one of the very few celebrated problems in NP that have not been shown yet to be either NP Complete or in P Zachos s most influential work was introducing and proving properties of the class Parity P with Christos Papadimitriou 9 He also introduced Probabilistic Quantifiers and Alternations of Probabilistic Quantifiers to uniformly describe various Complexity Classes as well as Interactive Proof Systems and Probabilistic Games 10 His current interests include Probabilistic and Functional Complexity Classes Combinatory Algebras as a foundation to Theory of Computations the interconnections of Cryptographic Techniques and Computational Complexity as well as Algorithms for Graph Problems 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 He is the brother of theoretical physicist Cosmas Zachos See also EditList of Greek mathematiciansReferences Edit 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 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 Zachos Stathis Martin Furer 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 Furer 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 Papadimitriou Christos H 1994 Computational Complexity Addison Wesley Hemaspaandra Lane A Mitsunori Ogihara 2001 The Complexity Theory Companion Springer ISBN 978 3540674191 Du Ding Zhu Ker I Ko 2000 Theory of Computational Complexity Wiley Interscience 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 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 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 External links EditProfile at the National Technical University of Athens Stathis Zachos at DBLP Bibliography Server Stathis Zachos at the Mathematics Genealogy Project Retrieved from https en wikipedia org w index php title Stathis Zachos amp oldid 1091328455, wikipedia, wiki, book, books, library,
