# Mihalis Yannakakis

> Greek theoretical computer scientist

**Wikidata**: [Q92825](https://www.wikidata.org/wiki/Q92825)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Mihalis_Yannakakis)  
**Source**: https://4ort.xyz/entity/mihalis-yannakakis

## Summary
Mihalis Yannakakis is a Greek-American theoretical computer scientist known for his foundational contributions to computational complexity theory. He is a professor at Columbia University and a recipient of prestigious awards such as the Knuth Prize (2005) and the John von Neumann Theory Prize (2023).

## Biography
- Born: September 13, 1953, in Athens, Greece
- Nationality: Greece, United States
- Education: National Technical University of Athens, Princeton University
- Known for: Advances in computational complexity theory and algorithms
- Employer(s): Columbia University
- Field(s): Theoretical computer science, computational complexity theory

## Contributions
Mihalis Yannakakis has made significant contributions to theoretical computer science, particularly in computational complexity theory. His work includes seminal research on the complexity of counting problems, the structure of NP-complete problems, and the development of algorithms for graph problems. Yannakakis introduced the concept of "Yannakakis's algorithm" for the graph isomorphism problem, which has had a lasting impact on the field. He has also contributed to the understanding of the complexity of logical theories and the development of efficient algorithms for database queries. His research has been published in top-tier conferences and journals, influencing both theoretical and practical aspects of computer science.

## FAQs
### Q: What is Mihalis Yannakakis known for?
A: Mihalis Yannakakis is known for his foundational work in computational complexity theory, including contributions to the complexity of counting problems and graph algorithms.

### Q: Where does Mihalis Yannakakis work?
A: Mihalis Yannakakis is a professor at Columbia University.

### Q: What awards has Mihalis Yannakakis received?
A: He has received several prestigious awards, including the Knuth Prize (2005) and the John von Neumann Theory Prize (2023).

### Q: Who was Mihalis Yannakakis's doctoral advisor?
A: His doctoral advisor was Jeffrey David Ullman.

### Q: What organizations is Mihalis Yannakakis a member of?
A: He is a member of the National Academy of Engineering, the Association for Computing Machinery (ACM Fellow since 1998), Academia Europaea, the National Academy of Sciences, and the American Academy of Arts and Sciences.

## Why They Matter
Mihalis Yannakakis's work has significantly advanced the field of theoretical computer science, particularly in understanding the inherent difficulty of computational problems. His research on computational complexity has provided foundational insights that have shaped the development of algorithms and the classification of problems according to their complexity. Yannakakis's contributions have influenced both academic research and practical applications in computer science, making him a key figure in the field. His work continues to inspire and guide new generations of computer scientists.

## Notable For
- Recipient of the Knuth Prize (2005) and the John von Neumann Theory Prize (2023)
- ACM Fellow (since 1998)
- Member of the National Academy of Engineering, Academia Europaea, National Academy of Sciences, and American Academy of Arts and Sciences
- Doctoral advisor to notable computer scientists such as Spyridon Antonakopoulos and Ilias Diakonikolas
- Foundational contributions to computational complexity theory and graph algorithms

## Body
### Early Life and Education
Mihalis Yannakakis was born on September 13, 1953, in Athens, Greece. He earned his undergraduate degree from the National Technical University of Athens and later pursued advanced studies at Princeton University.

### Career and Research
Yannakakis has had a distinguished career in theoretical computer science. He is currently a professor at Columbia University, where he continues to conduct research in computational complexity theory. His work has focused on the complexity of counting problems, the structure of NP-complete problems, and the development of efficient algorithms for graph problems.

### Awards and Honors
Throughout his career, Yannakakis has received numerous awards and honors. He was awarded the Knuth Prize in 2005 for his contributions to theoretical computer science. In 2023, he received the John von Neumann Theory Prize, recognizing his significant impact on the field. He has also been elected as a fellow of the Association for Computing Machinery (ACM) and a member of several prestigious academies, including the National Academy of Engineering, Academia Europaea, the National Academy of Sciences, and the American Academy of Arts and Sciences.

### Influence and Legacy
Yannakakis's research has had a profound influence on the field of theoretical computer science. His work on computational complexity has provided foundational insights that have shaped the development of algorithms and the classification of problems according to their complexity. He has also mentored numerous students who have gone on to make significant contributions to the field, further extending his impact.

## Schema Markup
```json
{
  "@context": "https://schema.org",
  "@type": "Person",
  "name": "Mihalis Yannakakis",
  "jobTitle": "Theoretical Computer Scientist",
  "worksFor": {"@type": "Organization", "name": "Columbia University"},
  "nationality": [{"@type": "Country", "name": "Greece"}, {"@type": "Country", "name": "United States"}],
  "birthDate": "1953-09-13",
  "birthPlace": "Athens, Greece",
  "alumniOf": [{"@type": "EducationalOrganization", "name": "National Technical University of Athens"}, {"@type": "EducationalOrganization", "name": "Princeton University"}],
  "knowsAbout": ["Computational Complexity Theory", "Theoretical Computer Science"],
  "sameAs": ["https://www.wikidata.org/wiki/Q97033143", "https://en.wikipedia.org/wiki/Mihalis_Yannakakis"],
  "description": "Greek-American theoretical computer scientist known for his contributions to computational complexity theory."
}

## References

1. Mathematics Genealogy Project
2. [Source](https://awards.acm.org/fellows/award-recipients)
3. [Source](https://www.informs.org/Recognizing-Excellence/Award-Recipients/Christos-Papadimitriou)
4. [Source](https://www.ae-info.org/ae/User/Yannakakis_Mihalis)
5. Freebase Data Dumps. 2013
6. [Source](http://www.nasonline.org/member-directory/living-member-list.html)