Yoxan Xestad - Johan Håstad

Yoxan Xestad
Tug'ilgan (1960-11-19) 19 noyabr 1960 yil (60 yosh)
MillatiShvetsiya
Olma mater
Mukofotlar
Ilmiy martaba
MaydonlarKompyuter fanlari
InstitutlarQirollik texnologiya instituti
Doktor doktoriShafrira Goldwasser[1]

Yoxan Torkel Xastad (Shvedcha talaffuz:[ˈJûːan ˈhǒːsta]; 1960 yil 19-noyabrda tug'ilgan) a Shved nazariy kompyuter olimi ishi bilan eng taniqli hisoblash murakkabligi nazariyasi. U oluvchi edi Gödel mukofoti 1994 va 2011 yillarda va ACM Boshqa mukofotlar qatorida 1986 yilda doktorlik dissertatsiyasi mukofoti. U a professor yilda nazariy informatika da Qirollik texnologiya instituti yilda Stokgolm, 1988 yildan beri Shvetsiya, 1992 yilda to'liq professor bo'ldi. U a'zosi Shvetsiya Qirollik Fanlar akademiyasi 2001 yildan beri.

U uni qabul qildi B.S. yilda Matematika da Stokgolm universiteti 1981 yilda, uning XONIM. matematikada at Uppsala universiteti 1984 yilda va uning Ph.D. Matematika bo'yicha MIT 1986 yilda.[2]

Håstadning tezisi va 1994 y Gödel mukofoti uning ishi bilan bog'liq pastki chegaralar doimiy chuqurlik kattaligi bo'yicha Mantiqiy davrlar uchun paritet funktsiyasi. Keyin Endryu Yao bunday sxemalar eksponentsial kattalikka muhtojligini isbotladi, Håstad kerakli o'lchamdagi deyarli optimal chegaralarni o'zi orqali isbotladi lemmani almashtirish, bu muhim texnik vositaga aylandi elektronning murakkabligi ilovalar bilan o'rganish qobiliyati, IP ierarxiya va isbotlovchi tizimlar.[3]

U shuningdek yaqinlashmaslikning optimal natijalari bo'yicha ishi uchun 2011 yil Gödel mukofotiga sazovor bo'ldi. Xususan, u yaxshilandi PCP teoremasi (2001 yilda xuddi shu sovrinni qo'lga kiritgan) uchun ehtimollik tekshiruvchisini berish NP faqat uchta bitni o'qiydigan muammolar. Bundan tashqari, u ushbu natijalarni natijalarni isbotlash uchun ishlatgan yaqinlashishning qattiqligi.[4]

1998 yilda Xastad ma'ruzachi sifatida taklif qilingan Xalqaro matematiklar kongressi Berlinda.[5] 1999 yilda u Erdos o'qituvchisi da Quddusning ibroniy universiteti. 2012 yilda u sherigiga aylandi Amerika matematik jamiyati.[6] U sifatida saylandi ACM Fellow 2018 yilda "kontaktlarning zanglashiga olib keladigan murakkabligi, yaqinlashishi va yaqinlashmasligi va psevdandoming asoslariga qo'shgan hissasi" uchun.[7]

Adabiyotlar

  1. ^ Yoxan Xestad da Matematikaning nasabnomasi loyihasi
  2. ^ Simons instituti: Yoxan Xestad, olingan 2018-04-05.
  3. ^ 1994 yil Gödel mukofoti, olingan 2018-04-05
  4. ^ 2011 yil Gödel mukofoti, olingan 2018-04-05
  5. ^ Xestad, Yoxan (1998). "NP-hard optimallashtirish muammolarini taxmin qilish to'g'risida". Hujjat Matematika. (Bilefeld) Qo'shimcha jild ICM Berlin, 1998, jild. III. 441-450 betlar.
  6. ^ Amerika Matematik Jamiyati a'zolari ro'yxati, 2013-01-19 olingan.
  7. ^ Raqamli asrni qo'llab-quvvatlovchi muhim yutuqlar uchun 2018 yil ACM stipendiyalari, Hisoblash texnikasi assotsiatsiyasi, 2018 yil 5-dekabr

Tashqi havolalar