Христос Харилаос Пападимитриу ( греч . Χρήστος Χαρίλαος «Χρίστος» Παπαδημητρίου ; родился 16 августа 1949 г.) — греческий ученый-теоретик и профессор информатики семьи Донован в Колумбийском университете . [4] [1] [5] [6] [7] [8]
Пападимитриу учился в Национальном техническом университете Афин , где в 1972 году получил степень бакалавра искусств по электротехнике . Затем он продолжил обучение в аспирантуре Принстонского университета , где в 1976 году получил степень доктора философии по электротехнике и информатике после завершения докторской диссертации под названием «Сложность задач комбинаторной оптимизации». [9]
Пападимитриу преподавал в Гарварде , Массачусетском технологическом институте , Национальном техническом университете Афин , Стэнфорде , Калифорнийском университете в Сан-Диего , Калифорнийском университете в Беркли и в настоящее время является профессором компьютерных наук в Колумбийском университете.
Пападимитриу был соавтором статьи о сортировке блинов с Биллом Гейтсом , тогда студентом Гарварда. Пападимитриу вспоминал: «Два года спустя я позвонил ему, чтобы сказать, что наша статья была принята в хороший математический журнал. Он казался в высшей степени незаинтересованным. Он переехал в Альбукерке , штат Нью-Мексико, чтобы управлять небольшой компанией, пишущей код для микропроцессоров, и все такое. Я помню, как подумал: «Такой гениальный ребенок. Какая трата». Этой компанией была Microsoft . [10]
Пападимитриу был соавтором статьи «Сложность вычисления равновесия Нэша» вместе со своими студентами Константиносом Даскалакисом и Полом В. Голдбергом, за которую они получили премию Калаи по теории игр и компьютерным наукам 2008 года от Общества теории игр за «лучшую статью на стыке теории игр и компьютерных наук» [11] , в частности, «за ее ключевой концептуальный и технический вклад» [12] ; и премию за выдающуюся статью от Общества промышленной и прикладной математики .
В 2001 году Пападимитриу был избран членом Ассоциации вычислительной техники , а в 2002 году ему была присуждена премия Кнута . Также в 2002 году он стал членом Национальной инженерной академии США за вклад в теорию сложности, теорию баз данных и комбинаторную оптимизацию . [13] В 2009 году он был избран в Национальную академию наук США . Во время 36-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2009) состоялось специальное мероприятие, посвященное вкладу Пападимитриу в информатику. [14] В 2012 году он вместе с Элиасом Куцупиасом был награжден премией Гёделя за совместную работу над концепцией цены анархии . [15]
Пападимитриу является автором учебника Computational Complexity , одного из наиболее широко используемых учебников в области теории вычислительной сложности . Он также является соавтором учебника Algorithms (2008) с Санджоем Дасгуптой и Умешем Вазирани , а также графического романа Logicomix (2009) [16] с Апостолосом Доксиадисом .
Его имя заняло 19-е место в академической базе данных и цифровой библиотеке поисковой системы CiteSeer [ необходима ссылка ] .
В 1997 году Пападимитриу получил степень доктора honoris causa от ETH Zurich . [17]
В 2011 году Пападимитриу получил степень доктора honoris causa от Национального технического университета Афин . [18]
В 2013 году Пападимитриу получил степень почетного доктора Федеральной политехнической школы Лозанны (EPFL) .
Пападимитриу был награжден медалью Джона фон Неймана IEEE в 2016 году, премией EATCS в 2015 году, премией Гёделя в 2012 году, премией Чарльза Бэббиджа IEEE Computer Society в 2004 году и премией Кнута в 2002 году. В 2019 году он получил премию Харви Техниона/Израиль за 2018 год. [19]
В 2006 году в Калифорнийском университете в Беркли он присоединился к группе профессоров и аспирантов под названием Lady X and The Positive Eigenvalues. [21]
