Stathis K. Zachos (; born 1947 in Athens) is a mathematician,

logician Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure of arg ...

and

theoretical A theory is a systematic and rational form of abstract thinking about a phenomenon, or the conclusions derived from such thinking. It involves contemplative and logical reasoning, often supported by processes such as observation, experimentation, ...

computer scientist.

Biography

Zachos received his

PhD A Doctor of Philosophy (PhD, DPhil; or ) is a terminal degree that usually denotes the highest level of academic achievement in a given discipline and is awarded following a course of graduate study and original research. The name of the deg ...

from the

ETHZ ETH Zurich (; ) is a public university in Zurich, Switzerland. Founded in 1854 with the stated mission to educate engineers and scientists, the university focuses primarily on science, technology, engineering, and mathematics. ETH Zurich ran ...

(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 The University of California, Santa Barbara (UC Santa Barbara or UCSB) is a Public university, public Land-grant university, land-grant research university in Santa Barbara County, California, United States. Tracing its roots back to 1891 as an ...

Brooklyn College Brooklyn College is a public university in Brooklyn in New York City, United States. It is part of the City University of New York system and enrolls nearly 14,000 students on a campus in the Midwood and Flatbush sections of Brooklyn as of fall ...

at the

City University of New York The City University of New York (CUNY, pronounced , ) is the Public university, public university system of Education in New York City, New York City. It is the largest urban university system in the United States, comprising 25 campuses: eleven ...

and

National Technical University of Athens The National (Metsovian) Technical University of Athens (NTUA; , ''National Metsovian Polytechnic''), sometimes known as Athens Polytechnic, a university in Athens, Greece. It is named in honor of its benefactors Nikolaos Stournaris, Eleni Tosi ...

and adjunct professor at

. He has worked as a researcher at

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of moder ...

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

. Stathis has published research papers in several areas of computer science. His work on randomized

complexity classes In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

Arthur–Merlin protocol In computational complexity theory, an Arthur–Merlin protocol, introduced by , is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). proved that all (formal) language ...

s, and

interactive proof system In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order ...

s 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 In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...

problem is not likely to be

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

(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 Christos Charilaos Papadimitriou (; born August 16, 1949) is a Greek-American theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University. Education Papadimitriou studied at the National Technical ...

). 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 class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

es,

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 computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., app ...

s, the interconnections of cryptographic techniques and

as well as

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

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 ICALP, the International Colloquium on Automata, Languages, and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe. Like most theoret ...

, CiE ( Computability in Europe), 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 Curt John Ducasse. The current president of the ASL ...

) 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 (; 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 Technology (Ph.D. 1979 ) under t ...

References

External links

Profile
at the

{{DEFAULTSORT:Zachos, Sathis 1947 births Living people 21st-century Greek mathematicians Greek computer scientists Scientists from Athens Greek logicians ETH Zurich alumni University of California, Santa Barbara faculty Brooklyn College faculty Academic staff of the National Technical University of Athens Theoretical computer scientists

Biography

See also

References

External links