Stathis K. Zachos ( el, Στάθης (Ευστάθιος) Ζάχος; born 1947 in

Athens Athens ( ; el, Αθήνα, Athína ; grc, Ἀθῆναι, Athênai (pl.) ) is both the capital and largest city of Greece. With a population close to four million, it is also the seventh largest city in the European Union. Athens dominates ...

) is a

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

, logician and theoretical

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

Biography

Zachos received his

PhD PHD or PhD may refer to: * Doctor of Philosophy (PhD), an academic qualification Entertainment * '' PhD: Phantasy Degree'', a Korean comic series * ''Piled Higher and Deeper'', a web comic * Ph.D. (band), a 1980s British group ** Ph.D. (Ph.D. albu ...

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 Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

at UCSB,

CUNY , mottoeng = The education of free people is the hope of Mankind , budget = $3.6 billion , established = , type = Public university system , chancellor = Fél ...

and NTUA and Adjunct professor at ETHZ. He has worked as a researcher at MIT,

Brown-Boveri Brown, Boveri & Cie. (Brown, Boveri & Company; BBC) was a Swiss group of electrical engineering companies. It was founded in Zürich, in 1891 by Charles Eugene Lancelot Brown and Walter Boveri who worked at the Maschinenfabrik Oerlikon. In 1970 ...

. Stathis has published research papers in several areas of

. His work on Randomized Complexity Classes, Arthur–Merlin Games, and Interactive Proof Systems has been very influential in proving important theorems and is cited in main textbooks of

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

. 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 In computational complexity theory, the complexity class ⊕P (pronounced "parity P") is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting ...

(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 Algebra Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of comput ...

s as a foundation to Theory of Computations, the interconnections of

Cryptographic Techniques Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...

and

Computational Complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

as well as

Algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...

for

Graph Problems Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

. He has co-organized International Conferences: STOC '87 (and programming committee of STOC '01), ICALP, CiE (

Computability in Europe The Association Computability in Europe (ACiE) is an international organization of mathematicians, logicians, computer scientists, philosophers, theoretical physicists and others interested in new developments in computability and in their underly ...

), PLS, ASL (

Association for Symbolic Logic The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic. The ASL was founded in 1936, and its first president was Alonzo Church. The current president of the ASL is ...

) 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 Cosmas K. Zachos ( el, Κοσμάς Ζάχος; born 1951) is a theoretical physicist. He was educated in physics (undergraduate A.B. 1974) at Princeton University, and did graduate work in theoretical physics at the California Institute of Techno ...

References

External links

Profile
at the

National Technical University of Athens The National (Metsovian) Technical University of Athens (NTUA; el, Εθνικό Μετσόβιο Πολυτεχνείο, ''National Metsovian Polytechnic''), sometimes known as Athens Polytechnic, is among the oldest higher education institution ...

* * {{DEFAULTSORT:Zachos, Sathis 1947 births Greek computer scientists Scientists from Athens Living people Greek mathematicians Greek logicians ETH Zurich alumni University of California, Santa Barbara faculty City University of New York faculty Academic staff of the National Technical University of Athens Theoretical computer scientists

Biography

See also

References

External links