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
University of California, Santa Barbara,
Brooklyn College at the
City University of New York and
National Technical University of Athens and adjunct professor at
ETHZ. He has worked as a researcher at
Massachusetts Institute of Technology,
Brown-Boveri. Stathis has published research papers in several areas of computer science. His work on randomized
complexity classes,
Arthur–Merlin protocols, and
interactive proof systems has been very influential in proving important theorems and is cited in main textbooks of
computational complexity. 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). 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). 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. 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==