Stathis has published research papers in several areas of computer science. His work on randomized complexity classes,[1][2]Arthur–Merlin protocols,[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]
↑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.
↑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". Theoretical Computer Science. Lecture Notes in Computer Science. Vol.145. pp.269–276. doi:10.1007/BFb0009651 (inactive 12 July 2025). ISBN978-3-540-11973-9.{{cite book}}: |journal= ignored (help)CS1 maint: DOI inactive as of July 2025 (link)
↑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.
