Christos Charilaos Papadimitriou（希腊语：Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου；生于1949年8月16日）是一位希腊裔美国理论计算机科学家，现任哥伦比亚大学计算机科学系Donovan Family教授。他的研究涵盖计算复杂性理论、算法、数据库理论和算法博弈论，其贡献塑造了计算领域的理论基础和实际应用。他因在无政府状态价格、纳什均衡复杂性方面的研究，以及撰写有影响力的教科书和一本关于逻辑史的图像小说而广受认可。
Papadimitriou的职业生涯以跨学科见解为标志，将计算机科学与经济学、数学乃至神经科学联系起来。他与Elias Koutsoupias共同提出的无政府状态价格概念，建立了一个量化去中心化决策低效性的框架，这一概念现已成为算法博弈论的核心。他在复杂性理论方面的贡献厘清了计算机能高效计算的范围边界，对优化、数据库系统和人工智能具有深远影响。
教育背景
Papadimitriou就读于雅典国立技术大学，于1972年通过综合硕士项目获得电气工程学位。随后他在普林斯顿大学攻读研究生，于1976年获得电气工程和计算机科学博士学位。他的博士论文题为“组合优化问题的复杂性”，为他后来关于优化任务计算难度的研究奠定了基础。
学术生涯
Papadimitriou曾在多所顶尖机构担任教职，包括哈佛大学、麻省理工学院（MIT）、雅典国立技术大学、斯坦福大学、加州大学圣地亚哥分校和加州大学伯克利分校。自2014年起，他担任哥伦比亚大学计算机科学系Donovan Family教授，继续领导理论计算机科学领域的研究。
他职业生涯早期最著名的经历之一是与当时还是哈佛本科生的比尔·盖茨合作撰写了一篇关于煎饼排序的论文，该问题涉及通过翻转前缀来重新排列煎饼堆。该论文发表在一本数学期刊上，Papadimitriou后来回忆说，当他告知盖茨论文被接受时，盖茨已搬到阿尔伯克基经营一家小型软件公司，似乎对此不感兴趣。那家公司就是微软。
对复杂性理论的贡献
Papadimitriou在计算复杂性方面的研究具有奠基性意义。他的教科书《计算复杂性》（1994年）是该领域使用最广泛的参考书之一，涵盖从基本复杂性类到概率和交互式证明系统的高级结果。他还为数据库并发控制理论、组合优化以及人工智能中推理和规划等问题的复杂性做出了贡献。
他与学生Constantinos Daskalakis和Paul W. Goldberg合作研究计算纳什均衡的复杂性，证明了在某些博弈中找到纳什均衡在计算上是难解的，这一结果对算法博弈论和经济学具有深远影响。这项工作为他们赢得了2008年博弈论学会颁发的Kalai博弈论与计算机科学奖，以及工业与应用数学学会颁发的杰出论文奖。
算法博弈论与无政府状态价格
Papadimitriou与Elias Koutsoupias合作提出的无政府状态价格，引入了一种衡量系统因代理自私行为而性能下降程度的指标。这一概念已应用于网络路由、资源分配和市场设计，为理解去中心化系统中的低效性提供了理论基础。为此，他们获得了2012年哥德尔奖，这是理论计算机科学领域的最高荣誉之一。
他在算法博弈论方面的贡献还扩展到机制设计和大型系统中的均衡研究，这些领域随着在线平台和多智能体人工智能系统的兴起而变得越来越重要。
荣誉与奖项
Papadimitriou在其职业生涯中获得了众多荣誉。1997年，他获得苏黎世联邦理工学院荣誉博士学位。他于2001年当选为美国计算机协会会士，2002年获得克努斯奖并当选为美国国家工程院院士。2009年，他当选为美国国家科学院院士。他于2004年获得IEEE计算机学会Charles Babbage奖，2015年获得EATCS奖，2016年获得IEEE约翰·冯·诺依曼奖章。2019年，他获得以色列理工学院/以色列2018年度哈维奖。他还于2011年获得雅典国立技术大学荣誉博士学位，并于2013年获得洛桑联邦理工学院（EPFL）荣誉博士学位。
出版物与科普活动
Papadimitriou撰写或合著了多本有影响力的书籍。《计算理论要素》（与Harry R. Lewis合著，1982年）是自动机理论和形式语言的经典教科书。《组合优化：算法与复杂性》（与Kenneth Steiglitz合著，1982年）涵盖优化问题的算法设计与分析。《数据库并发控制理论》（1986年）探讨数据库系统中的问题。他的《计算复杂性》（1994年）至今仍是标准参考书。
他还为更广泛的读者写作。《图灵（关于计算的小说）》（2003年）是一部探索艾伦·图灵生平和思想的小说。《逻辑迷：对真理的史诗追寻》（2009年），与Apostolos Doxiadis合著，由Alecos Papadatos和Annie di Donna绘制插图，是一部讲述从伯特兰·罗素到库尔特·哥德尔数学和逻辑基础故事的图像小说。他还与Sanjoy Dasgupta和Umesh Vazirani合著了教科书《算法》（2006年），该书在计算机科学教育中被广泛使用。
个人生活
Papadimitriou以在学术之外从事创造性活动而闻名。2006年在加州大学伯克利分校时，他加入了一个由教授和研究生组成的乐队，名为Lady X and The Positive Eigenvalues，反映了他对音乐和合作的兴趣。
遗产与影响
Papadimitriou的工作对理论计算机科学及其应用产生了持久影响。他在无政府状态价格和均衡复杂性方面的研究影响了网络工程、经济学和人工智能等多个领域。他的教科书培养了一代又一代计算机科学家，他通过小说和图像小说传达复杂思想的能力将计算史带给了更广泛的公众。截至2020年代初，他仍是一位活跃的研究者，探索计算、进化和大脑之间的联系，对人工智能和机器学习具有启示意义。
他对计算理论的贡献也为现代人工智能系统的发展提供了信息，包括神经网络架构和大型语言模型，通过更深入地理解学习和推理的计算极限和可能性。他在组合优化和复杂性方面的工作对深度学习和生成式人工智能等领域高效算法的设计仍然具有相关性。
Papadimitriou的遗产不仅由他的技术成就定义，还由他作为传播者和教育者的角色定义，他弥合了抽象理论与计算及其他领域实际应用之间的鸿沟。