Mihalis Yannakakis
Encyclopedia
Mihalis Yannakakis is a Professor of Computer Science at Columbia University
. He is noted for his work in computational complexity
, databases, and other related fields. He won the Donald E. Knuth Prize
in 2005.
High School for his early education. He graduated from the National Technical University of Athens
in 1975 with a diploma in Electrical Engineering, and then earned his Ph.D. in Computer Science from Princeton University
in 1979. His dissertation was entitled "The Complexity of Maximum Subgraph Problems".
In 1978 he joined Bell Laboratories 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
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
and was the Editor-in-chief between 1998 and 2003. He also served on the editorial board of the Journal of the ACM
from 1986 to 2000.
He serves on the editorial boards of several other journals, including the Journal of Computer and System Sciences
, 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 and the IEEE Symposium on Foundations of Computer Science.
, database theory
, computer aided verification and testing, and algorithmic graph theory.
Notable among his contributions to complexity theory are two key papers about the PCP theory and about hardness of approximation
.
In the Annual ACM Symposium on Theory of Computing of 1988, Yannakakis and Christos Papadimitriou
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
, the Independent Set problem, and the Travelling Salesman Problem
.
Yannakakis and Carsten Lund
presented a number of important 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
and Set covering. Given the unlikely scenario that NP-hard
problems such as Graph coloring and Set covering would be solved optimally in polynomial time, there had been many attempts to develop efficient approximation solutions for them; the results obtained by Yannakakis and Carsten proved the unlikeliness of achieving this task.
In the area of database theory
, his principal 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
(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
, 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
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 temporal logic
, 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
s(MSC), where it was shown that weak realizability
is undecidable for bounded MSC-graphs and that safe-realizability is in EXPSPACE
, along with other interesting results related to the verification of MSC-graphs.
for the significance, impact and astonishing breadth of 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.
Columbia University
Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...
. He is noted for his work in computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
, databases, and other related fields. He won the Donald E. Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
in 2005.
Education and career
Yannakakis was born in Athens, Greece in 1953 and attended VarvakeioVarvakeio
Varvakeio High School is a public Greek high school located in Psychiko. It was initially founded by Ioannis Varvakis, who donated a big part of his fortune to the state, in order to build a high school, that everyone could attend without paying, that would be the best in Greece...
High School for his early education. He graduated from the National Technical University of Athens
National Technical University of Athens
The National Technical University of Athens , sometimes simply known as Athens Polytechnic, is among the oldest and most prestigious higher education institutions of Greece....
in 1975 with a diploma in Electrical Engineering, and then earned his Ph.D. in Computer Science from Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
in 1979. His dissertation was entitled "The Complexity of Maximum Subgraph Problems".
In 1978 he joined Bell Laboratories 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
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
where he was a Professor of Computer Science, and left in 2003 to join Columbia University
Columbia University
Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...
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
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 . As of September 2008, Éva Tardos serves as editor-in-chief.-External links:** on DBLP...
and was the Editor-in-chief between 1998 and 2003. He also served on the editorial board of the Journal of the ACM
Journal of the ACM
The Journal of the ACM is the flagship scientific journal of the Association for Computing Machinery . It is peer-reviewed and covers computer science in general, especially theoretical aspects. Its current editor-in-chief is Victor Vianu, from University of California, San Diego.The journal has...
from 1986 to 2000.
He serves on the editorial boards of several other journals, including the Journal of Computer and System Sciences
Journal of Computer and System Sciences
The Journal of Computer and System Sciences is a peer-reviewed scientific journal 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 in JCSS; these include four papers that have won the Gödel...
, 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 and the IEEE Symposium on Foundations of Computer Science.
Research
Yannakakis is known for his contributions to computer science in the areas of computational complexity theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, database theory
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....
, computer aided verification and testing, and algorithmic graph theory.
Notable among his contributions to complexity theory are two key papers about the PCP theory and about hardness of approximation
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. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can...
.
In the Annual ACM Symposium on Theory of Computing of 1988, Yannakakis and Christos Papadimitriou
Christos Papadimitriou
Christos Harilaos Papadimitriou is a Professor in the Computer Science Division at the University of California, Berkeley, United States...
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
3sat
3sat is the name of a public, advertising-free, television network in Central Europe. The programming is in German and is broadcast primarily within Germany, Austria and Switzerland .3sat was established for cultural...
, the Independent Set problem, and the Travelling Salesman Problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
.
Yannakakis and Carsten Lund
Carsten Lund
Carsten Lund is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Florham Park, New Jersey, United States.Lund was born in Aarhus, Denmark, and received the...
presented a number of important 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
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 of a graph such that no two adjacent vertices share the...
and Set covering. Given the unlikely scenario that NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problems such as Graph coloring and Set covering would be solved optimally in polynomial time, there had been many attempts to develop efficient approximation solutions for them; the results obtained by Yannakakis and Carsten proved the unlikeliness of achieving this task.
In the area of database theory
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....
, his principal contributions include the initiation of the study of acyclic
Acyclic
Acyclic can refer to:* In chemistry, a compound which is not cyclic, e.g. alkanes and acyclic aliphatic compounds* In mathematics:** A graph without a cycle, especially*** A directed acyclic graph...
databases and of non-two-phase locking. Acyclic database schemes are schemes that contain a single acyclic join dependency
Join dependency
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 T...
(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
Two-phase locking
In databases and transaction processing two-phase locking, is a concurrency control method that guarantees serializability.It is also the name of the resulting set of database transaction schedules...
, 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
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
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 temporal logic
Temporal logic
In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. In a temporal logic we can then express statements like "I am always hungry", "I will eventually be hungry", or "I will be hungry...
, 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
Message Sequence Chart
A Message Sequence Chart is an interaction diagram from the SDL family very similar to UML's sequence diagram, standardized by the International Telecommunication Union....
s(MSC), where it was shown that weak realizability
Realizability
Realizability is a part of proof theory which can be used to handle information about formulas instead of about the proofs of formulas. A natural number n is said to realize a statement in the language of arithmetic of natural numbers...
is undecidable for bounded MSC-graphs and that safe-realizability is in EXPSPACE
EXPSPACE
In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n...
, along with other interesting results related to the verification of MSC-graphs.
Awards
Yannakakis was awarded the seventh Knuth prizeKnuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
for the significance, impact and astonishing breadth of 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.