On the occasion of Stathis Zachos' retirement from CUNY.
Thursday, November 11, 2010,
New York City
The Graduate Center, CUNY
Room TBA
Stathis Zachos received his PhD from the ETHZ (Swiss Federal Institute of Technology Zurich) in Mathematics (and Computer Science), 1978. He was a visiting scientist in MIT in 1982 and 1983 and he served as faculty at UCSB, CUNY and NTUA. Stathis works on the area 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 C. 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 teaching many classes, particularly undergraduate, and thinking about research problems in 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. Recently, he co-organized International Conferences in Greece, STOC, ICALP, PLS, ASL European Summer Meeting and ACAC (Athens Colloquium on Algorithms and Complexity), in Athens. He was affiliated with CUNY from 1984 to 2011.