Christos Charilaos Papadimitriou ( griego : Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου ; nacido el 16 de agosto de 1949) es un científico informático teórico greco-estadounidense 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 y ciencias de la computación en 1976 después de completar una disertación 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 la Familia Donovan de Ciencias de la Computación 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 después, 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, entre otras cosas. Recuerdo que pensé: 'Qué chico tan brillante. Qué desperdicio'". La empresa era Microsoft . [10]
Papadimitriou fue coautor de "La complejidad de calcular un equilibrio de Nash" con sus estudiantes Constantinos Daskalakis y Paul W. Goldberg, por el que recibieron el Premio Kalai de Teoría de Juegos y Ciencias de la Computación de 2008 de la Game Theory Society por "el mejor artículo en la interfaz de la teoría de juegos y la ciencia de la computación", [11] en particular "por sus contribuciones conceptuales y técnicas clave"; [12] y el Premio al artículo destacado de la Society for Industrial and Applied Mathematics .
En 2001, Papadimitriou fue incluido 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 Estados Unidos 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 ciencia informática. [14] En 2012, él, 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 Algorithms (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 número 19 de 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 de Zúrich . [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 John von Neumann del IEEE 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 del Technion/Israel para el año 2018. [19]
En 2006, en la Universidad de California en Berkeley, se unió a una banda formada por profesores y estudiantes de posgrado llamada Lady X and The Positive Eigenvalues. [21]
