Христос Харилаос Пападимитриу ( греч . Χρήστος Χαρίλαος «Χρίστος» Παπαδημητρίου ; родился 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]
Пападимитриу является автором учебника «Вычислительная сложность» , одного из наиболее широко используемых учебников в области теории сложности вычислений . Он также является соавтором учебника «Алгоритмы» (2008 г.) с Санджоем Дасгуптой и Умешом Вазирани и графического романа «Логикомикс» (2009 г.) [16] с Апостолосом Доксиадисом .
Его имя было указано на 19-м месте в академической базе данных поисковой системы CiteSeer и в цифровой библиотеке .
В 1997 году Пападимитриу получил степень почетного доктора ETH Цюриха . [17]
В 2011 году Пападимитриу получил степень почетного доктора Афинского национального технического университета . [18]
В 2013 году Пападимитриу получил степень почетного доктора Федеральной политехнической школы Лозанны (EPFL) .
Пападимитриу был награжден медалью Джона фон Неймана IEEE в 2016 году, премией EATCS в 2015 году, премией Гёделя в 2012 году, премией Чарльза Бэббиджа IEEE Computer Society в 2004 году и премией Кнута в 2002 году. В 2019 году он получил премию Харви Технион/Израиль за 2018 год. [19]
В Калифорнийском университете в Беркли в 2006 году он присоединился к группе профессоров и аспирантов под названием Lady X and The Positive Eigenvalues. [21]
