Stathis Zachos
Stathis K. Zachos (Greek: Στάθης (Ευστάθιος) Ζάχος; born 1947, Athens) is a mathematician, logician and theoretical computer scientist.
Biography
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 has guided more than twenty doctoral students and more than fifty M.Sc./Diploma students, many of which have positions in Universities and research centers worldwide.
He is the brother of theoretical physicist Cosmas Zachos.
See also
References
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
External links
- Articles containing Greek-language text
- 1947 births
- Greek computer scientists
- People from Athens
- Living people
- Greek mathematicians
- Greek logicians
- ETH Zurich alumni
- University of California, Santa Barbara faculty
- City University of New York faculty
- National Technical University of Athens faculty
- Theoretical computer scientists
