Christos Harilaos Papadimitriou (en ), né le à Athènes, est un professeur et chercheur en informatique grec. Il travaille à l'université de Californie à Berkeley. Il a coécrit le roman graphique Logicomix avec Apóstolos Doxiádis.
Christos Papadimitriou obtient le prix Knuth en 2002, le prix Kalai en 2008, le prix Gödel en 2012 et le prix de l'European Association for Theoretical Computer Science en 2015.
Il est surtout connu pour son travail dans les domaines de la complexité algorithmique, des bases de données et l'optimisation combinatoire.
Biographie
Papadimitriou a obtenu son PhD en 1976 à l'université de Princeton sous la direction de Kenneth Steiglitz.
Il est professeur à l'université de Berkeley depuis 1996.
Travaux
Papadimitriou s'est intéressé à de nombreux sujets. Il est notamment connu pour son étude du calcul des équilibres de Nash (et la définition de la classe de complexité PPAD), pour son rôle de cofondateur de la théorie algorithmique des jeux (notamment en définissant le prix de l'anarchie) et pour ses travaux sur les liens biologie/informatique. Dans les domaines plus classiques de l'informatique théorique, il a apporté des éléments importants en optimisation, pour les algorithmes d'approximation et en théorie des bases de données.
Prix Papadimitriou a reçu le prix Knuth en 2002 pour son travail en informatique théorique, notamment en complexité.
En 2008, il reçoit le premier Prix Kalai avec Constantinos Daskalakis et Paul W. Goldberg pour leur article The Complexity of Computing a Nash Equilibrium.
Il est lauréat du prix Gödel en 2012, avec Elias Koutsoupias, Noam Nisan, Amir Ronen, Tim Roughgarden et Éva Tardos, pour la création de la théorie algorithmique des jeux.
Il reçoit le prix de l'European Association for Theoretical Computer Science en 2015.
Publications
Références
Liens externes
Catégorie:Naissance en août 1949 Catégorie:Naissance à Athènes Catégorie:Personnalité en informatique théorique Catégorie:Lauréat du prix Knuth Catégorie:Lauréat du prix Gödel Catégorie:Lauréat du prix de théorie John-von-Neumann Catégorie:Étudiant de l'université polytechnique nationale d'Athènes Catégorie:Étudiant de l'université de Princeton Catégorie:Professeur à l'université de Californie à Berkeley Catégorie:Professeur à l'université Harvard Catégorie:Professeur à l'université de Californie à San Diego Catégorie:Professeur au Massachusetts Institute of Technology Catégorie:Lauréat du prix EATCS