HOME

TheInfoList



OR:

Mihalis Yannakakis ( el, Μιχάλης Γιαννακάκης; born 13 September 1953 in Athens,
Greece Greece,, or , romanized: ', officially the Hellenic Republic, is a country in Southeast Europe. It is situated on the southern tip of the Balkans, and is located at the crossroads of Europe, Asia, and Africa. Greece shares land borders with ...
)Columbia University: CV: Mihalis Yannakakis
(accessed 12 November 2009)
is professor of computer science at Columbia University. He is noted for his work in
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 ...
,
databases In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases span ...
, and other related fields. He won the Donald E. Knuth Prize in 2005.Knuth Prize
/ref>


Education and career

Yannakakis was born in Athens, Greece in 1953 and attended
Varvakeio The Varvakeio High School ( el, Πρότυπο Γυμνάσιο & ΓΕ.Λ Βαρβακείου Σχολής) is a public Greek junior high school and high school located in Psychiko. It was founded by Ioannis Varvakis, who donated a big part of ...
High School for his early education. He graduated from 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 ...
in 1975 with a diploma in Electrical Engineering, and then earned his PhD in Computer Science from
Princeton University Princeton University is a private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth as the College of New Jersey, Princeton is the fourth-oldest institution of higher education in the United States and one of the nin ...
in 1979. His dissertation was entitled "The Complexity of Maximum Subgraph Problems". In 1978 he joined
Bell Laboratories Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...
and served as Director of the Computing Principles Research Department starting from 1991 until 2001, when he left Bell laboratories and joined Avaya Laboratories. There he served as Director of the Computing Principles Research Department until 2002. In 2002 he joined
Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is considere ...
, where he was a professor of computer science, and left in 2003 to join Columbia University in 2004, where he is currently serving as the Percy K. and Vida L. W. Hudson Professor of Computer Science. From 1992 to 2003, Yannakakis served on the editorial board of the ''
SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ...
'' and was the
editor-in-chief An editor-in-chief (EIC), also known as lead editor or chief editor, is a publication's editorial leader who has final responsibility for its operations and policies. The highest-ranking editor of a publication may also be titled editor, managing ...
between 1998 and 2003. He also was a member of the editorial board of the ''
Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan ...
'' from 1986 to 2000. Other editorial board memberships include the ''
Journal of Computer and System Sciences The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been published ...
'', the ''Journal of Combinatorial Optimization'', and the ''Journal of Complexity''. He has also served on conference committees and chaired various conferences, such as the
ACM Symposium on Principles of Database Systems The ACM Symposium on Principles of Database Systems (PODS) is an international research conference on database theory, and has been held yearly since 1982. It is sponsored by three Association for Computing Machinery SIGs, SIGART, SIGACT, and SIG ...
and the IEEE Symposium on Foundations of Computer Science. As of June 2020, his publications have been cited close to 35,000 times, and he has an
h-index The ''h''-index is an author-level metric that measures both the productivity and citation impact of the publications, initially used for an individual scientist or scholar. The ''h''-index correlates with obvious success indicators such as w ...
of 93.


Research

Yannakakis is known for his contributions to computer science in the areas of
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
,
database theory Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems. Theoretical aspects of data management include, among other areas, the foundations of q ...
, computer aided verification and testing, and algorithmic graph theory. Among his contributions to complexity theory are two papers about the PCP theory and about
hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of approximation algorithms by pr ...
. In the Annual
ACM Symposium on Theory of Computing The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for ...
of 1988, Yannakakis and
Christos Papadimitriou Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia U ...
introduced the definitions of the complexity classes Max-NP and Max-SNP. Max-NP and Max-SNP (which is a subclass of Max-NP) contain a number of interesting optimization problems, and it was shown by Yannakakis and Papadimitriou that these problems have some bounded error. These findings were able to explain the lack of progress that had been seen in the research community on the approximability of a number of optimization problems, including
3SAT In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
, the Independent Set problem, and the
Travelling Salesman Problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
. Yannakakis and
Carsten Lund Carsten Lund (born July 1, 1963) is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Bedminster, New Jersey, United States. Lund was born in Aarhus, Denmark, and received the "kandidat" degree in 1988 from the Unive ...
presented a number of findings regarding the hardness of computing approximations at the Annual ACM Symposium on Theory of Computing of 1993. These findings demonstrated the difficulty of efficiently computing approximate solutions to a number of minimization problems such as
Graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
and Set covering. Given the unlikely scenario that
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard p ...
problems such as Graph coloring and Set covering would be solved optimally in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, there had been many attempts to develop efficient approximation solutions for them; the results obtained by Yannakakis and Carsten proved the unlikelihood of achieving this task. In the area of
database theory Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems. Theoretical aspects of data management include, among other areas, the foundations of q ...
, his contributions include the initiation of the study of acyclic databases and of non-two-phase locking. Acyclic database schemes are schemes that contain a single acyclic
join dependency In database theory, a join dependency is a constraint on the set of legal relations over a database scheme. A table T is subject to a join dependency if T can always be recreated by joining multiple tables each having a subset of the attributes of ...
(a join dependency is a relationship governing the joining of tables of the database ) and a collection of functional dependencies; a number of researchers, including Yannakakis, pointed out the usefulness of these schemes by demonstrating the many useful properties they had: for example, the ability to solve many acyclic-scheme based problems in polynomial time, whereas the problem could easily have been NP-complete for other schemes. With regard to non
two-phase locking In databases and transaction processing, two-phase locking (2PL) is a concurrency control method that guarantees serializability. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987) ''Concurrency Control and Recovery in Database Systems'' ...
, Yannakakis demonstrated how knowledge about the structure of a database and the forms of various transactions executed on them could be used to establish whether a particular locking policy is safe or not. The commonly used two phase locking (2PL) policies consist of two stages – for locking and unlocking entities respectively – and to avoid such a policy it is necessary to impose some structure on the entities of a database; Yannakakis' results show how, by choosing a
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) w ...
resembling the consistency constraint-structure of a database, a locking policy that visits entities along the paths of this hypergraph will be safe. Such a policy need not be two-phase and these policies can be classified according to the connectivity of the above-mentioned hypergraph, 2PL policies being only one particular instance of these. Yannakakis went on to show that for the natural class of safe locking policies (L-policies), freedom from deadlocks is determined solely on the order in which entities are accessed by transactions, and from this derived simple conditions that would guarantee freedom from deadlocks for an L-policy. He has also contributed to the area of computer aided verification and testing, where he laid the rigorous algorithmic and complexity-theoretic foundations of the field. Some of his contributions include the designing of memory efficient algorithms for the verification of temporal properties of finite-state programs, determining the complexity of testing whether programs satisfy their specifications expressed in
linear-time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
temporal logic In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, "I am ''always'' hungry", "I will ''eventually'' be hungry", or "I will be hungry ''until'' I ...
, and verifying that a model with timing constraints satisfies a given temporal property. Along with Alex Groce and Doron Peled, he introduced Adaptive Model Checking, showing that when inconsistencies are present between a system and the corresponding model, the results of the verification can be used to improve the model. He has also contributed to research on
Message Sequence Chart A message sequence chart (or MSC) is an interaction diagram from the SDL family standardized by the International Telecommunication Union. The purpose of recommending MSC (Message Sequence Chart) is to provide a trace language for the specificati ...
s (MSC), where it was shown that weak
realizability In mathematical logic, realizability is a collection of methods in proof theory used to study constructive proofs and extract additional information from them. Formulas from a formal theory are "realized" by objects, known as "realizers", in a way t ...
is undecidable for bounded MSC-graphs and that safe-realizability is in
EXPSPACE In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2^) space, where p(n) is a polynomial function of n. Some authors restrict p(n) to be a linear fun ...
, along with other interesting results related to the verification of MSC-graphs.


Awards and recognition

Yannakakis is a member of both the
National Academy of Engineering The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of ...
and the
National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Natio ...
. He was awarded the seventh
Knuth prize The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth. History The Knuth Prize has been awarded since 1996 and includes an award of U ...
for his contributions to theoretical computer science. He has also been awarded the Bell Labs Distinguished Member of Technical Staff Award and the Bell Labs President's Gold Award, in 1985 and in 2000 respectively. He is a Fellow of the ACM and also a Fellow of
Bell Laboratories Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...
. He was elected fellow of the American Academy of Arts and Sciences (AAAS) in 2020.


References


External links


Home page at Columbia
{{DEFAULTSORT:Yannakakis, Mihalis 1953 births Living people Greek computer scientists American computer scientists Columbia School of Engineering and Applied Science faculty Knuth Prize laureates Fellows of the Association for Computing Machinery Theoretical computer scientists National Technical University of Athens alumni Greek academics Members of the United States National Academy of Engineering Members of the United States National Academy of Sciences People from Athens