Christos Charilaos Papadimitriou ( griego : Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου ; nacido el 16 de agosto de 1949) es un científico informático teórico griego y profesor de informática de la familia Donovan en la Universidad de Columbia . [4] [1] [5] [6] [7] [8]
Papadimitriou estudió en la Universidad Técnica Nacional de Atenas , donde en 1972 recibió su licenciatura en ingeniería eléctrica . Luego realizó estudios de posgrado en la Universidad de Princeton , donde recibió su doctorado. en ingeniería eléctrica e informática en 1976 después de completar una tesis doctoral titulada "La complejidad de los problemas de optimización combinatoria". [9]
Papadimitriou ha enseñado en Harvard , MIT , la Universidad Técnica Nacional de Atenas , Stanford , UCSD , la Universidad de California, Berkeley y actualmente es profesor de Ciencias de la Computación de la Familia Donovan en la Universidad de Columbia.
Papadimitriou fue coautor de un artículo sobre la clasificación de panqueques con Bill Gates , entonces estudiante de Harvard. Papadimitriou recordó: "Dos años más tarde, lo llamé para decirle que nuestro artículo había sido aceptado en una excelente revista de matemáticas. Parecía eminentemente desinteresado. Se había mudado a Albuquerque , Nuevo México, para dirigir una pequeña empresa que escribía códigos para microprocesadores, nada menos. Recuerdo haber pensado: 'Qué niño tan brillante. Qué desperdicio'". La empresa era Microsoft . [10]
Papadimitriou fue coautor de "La complejidad de calcular un equilibrio de Nash" con sus alumnos Constantinos Daskalakis y Paul W. Goldberg, por el que recibieron el premio Kalai de teoría de juegos e informática de 2008 de la Game Theory Society por "el mejor artículo sobre la interfaz". de la teoría de juegos y la informática", [11] en particular "por sus contribuciones conceptuales y técnicas clave"; [12] y el premio al artículo destacado de la Sociedad de Matemáticas Industriales y Aplicadas .
En 2001, Papadimitriou fue admitido como miembro de la Association for Computing Machinery y en 2002 recibió el Premio Knuth . También en 2002, se convirtió en miembro de la Academia Nacional de Ingeniería de EE. UU. por sus contribuciones a la teoría de la complejidad, la teoría de bases de datos y la optimización combinatoria . [13] En 2009 fue elegido miembro de la Academia Nacional de Ciencias de Estados Unidos . Durante el 36º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2009), hubo un evento especial en honor a las contribuciones de Papadimitriou a la informática. [14] En 2012, junto con Elias Koutsoupias, recibió el Premio Gödel por su trabajo conjunto sobre el concepto del precio de la anarquía . [15]
Papadimitriou es el autor del libro de texto Computational Complexity , uno de los libros de texto más utilizados en el campo de la teoría de la complejidad computacional . También es coautor del libro de texto Algoritmos (2008) con Sanjoy Dasgupta y Umesh Vazirani , y de la novela gráfica Logicomix (2009) [16] con Apostolos Doxiadis .
Su nombre figuraba en la posición 19 en la base de datos académica y biblioteca digital del motor de búsqueda CiteSeer [ cita requerida ] .
En 1997, Papadimitriou recibió un doctorado honoris causa de la ETH Zurich . [17]
En 2011, Papadimitriou recibió un doctorado honoris causa de la Universidad Técnica Nacional de Atenas . [18]
En 2013, Papadimitriou recibió un doctorado honoris causa de la École polytechnique fédérale de Lausanne (EPFL) .
Papadimitriou recibió la Medalla IEEE John von Neumann en 2016, el Premio EATCS en 2015, el Premio Gödel en 2012, el Premio Charles Babbage de la IEEE Computer Society en 2004 y el Premio Knuth en 2002. En 2019 recibió el Premio Harvey de la Technion/Israel para el año 2018. [19]
En UC Berkeley, en 2006, se unió a una banda de profesores, estudiantes graduados llamada Lady X and The Positive Eigenvalues. [21]
