米哈利斯·扬纳卡基斯（Mihalis Yannakakis）于1975年从雅典国立技术大学获得电气工程学位，这标志着他在计算复杂性理论领域漫长职业生涯的开始。他1953年出生于雅典，后来在普林斯顿大学获得计算机科学博士学位，随后对数据库理论、验证和算法图论产生了影响。
复杂性基础
扬纳卡基斯在工业研究中度过了二十多年，于1978年在贝尔实验室开始其职业生涯。1991年至2001年，他在该实验室担任计算原理研究部主任。在此期间，他于1988年与克里斯托斯·帕帕迪米特里乌合作定义了复杂性类 Max-NP 和 Max-SNP，为旅行商问题和 3SAT 等 NP-hard 问题近似中观察到的局限性提供了严格的解释。他1983年（注：原文1993）与卡斯滕·伦德合作的工作进一步阐明了计算如图着色等最小化问题的近似解所固有的困难。
数据库创新
他对数据库理论的贡献集中于通过研究无环模式来优化查询处理。他引入了用于无环连接查询的扬纳卡基斯算法，证明了这些结构可以在多项式时间内求解。除了查询优化之外，他还研究了锁策略，证明了通过利用数据的超图结构和事务一致性约束来防止死锁，可以在两阶段锁定的严格限制之外维持数据库的安全性。
验证与学术领导力
转入学术界后，扬纳卡基斯于2002年在斯坦福大学担任教授，随后于2004年加入哥伦比亚大学。他目前担任珀西·K·和维达·L·W·哈德逊计算机科学教授。他在计算机辅助验证方面的研究为测试线性时序逻辑和消息序列图建立了算法基础。他还与亚历克斯·格罗斯和多龙·佩莱德共同开发了自适应模型检测，这是一种根据验证结果精炼系统模型的方法。
专业认可
扬纳卡基斯在编辑界保持着重要的影响力，曾于1998年至2003年担任《SIAM计算期刊》主编。他的学术地位体现在他是美国国家科学院、美国国家工程院、美国艺术与科学院以及欧洲科学院的院士。他获得的奖项包括2005年的高德纳奖和2023年的约翰·冯·诺伊曼理论奖。
核心事实
- 出生：1953年，希腊雅典 - 博士学位：普林斯顿大学，1979年 - 高德纳奖：2005年 - 约翰·冯·诺伊マン理论奖（约翰·冯·诺伊曼理论奖）：2023年 - ACM会士：1998年 - 国籍：美国；希腊 - 语言：现代希腊语
读者常见问题
### 什么是扬纳卡基斯算法？
它是一种用于在数据库系统中执行无环连接查询的方法，允许在多项式时间内对其进行求解。
### 扬纳卡基斯曾隶属于哪些机构？
他曾在贝尔实验室、亚美亚实验室、斯坦福大学和哥伦比亚大学工作过。
.jpg)
