Fødsel | 1982 |
---|---|
Nasjonalitet | amerikansk |
Områder | teoretisk informatikk , algoritmisk spillteori |
Institusjoner | Institute for Advanced Study , Princeton University , Columbia University |
Opplæring | Tsinghua University |
Veileder | Bo Zhang |
Kjent for | fullstendighet PPAD av Nash-likevekt |
Utmerkelser | SIAM Outstanding Paper Prize (2016), Presburger Prize (2015), Alfred P. Sloan Research Fellowship (2011) |
Nettstedet | www.cs.columbia.edu/~xichen/Homepage/Welcome.html |
Xi Chen , født i 1982, er en amerikansk datalteoretiker , professor i informatikkavdelingen ved Columbia University . Hans forskningsemner er teoretisk informatikk, inkludert algoritmisk teori og økonomi, kompleksitetsteori, grafisomorfistesting og eiendomstesting.
Xi Chen ble uteksaminert fra Tsinghua University med en BA i fysikk og matematikk i 2003 og en doktorgrad i 2007 under veiledning av Bo Zhang. Der var han medlem av Institutt for teoretisk informatikk ledet av Andrew Chi-Chih Yao. Han var da, fra 2007 til 2010, post-doc ved Institute for Advanced Study ved Princeton University , ved University of Southern California og til slutt ved Columbia University . Siden januar 2011 har han vært lektor i informatikkavdelingen ved Columbia University .
Xi Chen har gitt grunnleggende bidrag innen ulike teoretiske felt. Hans arbeid innen algoritmisk spillteori og beregningsøkonomi inkluderer svaret på et lenge forble åpent spørsmål om kompleksiteten i beregningen av Nash-likevekt for tospillerspill, hvor han demonstrerer fullstendigheten PPAD i felles arbeid med Xiaotie Deng. Det demonstrerte også PPAD- fullstendighet for ulike markedskategorier og nyttefunksjoner som er mye brukt i økonomi.
I kompleksitetsteori viser Xi Chen en komplett dikotomi-teorem for kompleksiteten til visse funksjoner, og viser at den enten er polynom eller # P-komplett ; dette inkluderer beregning av partisjonsfunksjoner samt problemer med å tilfredsstille begrensninger med komplekse vekter, konsepter som inkluderer for eksempel oppregning av homomorfismer av grafer . Hans bidrag til algoritmikk inkluderer et bevis på at sterkt regelmessig grafisomorfisme, et vanskelig tilfelle av grafisomorfismeproblemet , kan testes i en tid som er eksponentiell i .
Xi Chen jobber også med eiendomstesting , et område som studerer sublinear tidsalgoritmer som kan avgjøre om et massivt sett med data har en bestemt egenskap eller er langt fra å ha den egenskapen. Det etablerer nye øvre og nedre grenser for eiendomstester av naturlige egenskaper for boolske funksjoner som monotoni og egenskapen til å være en junta.
I 2006 ble han tildelt den Best Paper Award på 47 th IEEE Symposium på Foundations of Computer Science. I 2011 fikk Xi Chen et Alfred P.Sloan Research Fellowship . 201 I 2015 tildelte EATCS Presburgerprisen til Xi Chen I 2016 fikk han en SIAM Outstanding Paper Prize for artikkelen "How to Compress Interactive Communication" med Boaz Barak, Mark Braverman og Anup Rao