László Babai
László „Laci“ Babai (20-iyul 1950- yilda Budapeşt tugʻilgan) [1] — Chikago universitetidagi kompyuter va matematika professoridir. Uning tadqiqotlari hisoblash murakkabligi nazariyasi, algoritmlar, kombinatorlik va cheklangan guruhlar qaratilgan, bu sohalar oʻrtasidagi oʻzaro taʼsirga eʼtibor qaratilmoqda.
Hayot
[tahrir | manbasini tahrirlash]1968-yilda Babai Xalqaro matematik olimpiada oltin medal qozondi. Babai 1968-yildan 1973-yilgacha Eötvös Loránd universiteti fan fakultetida matematika oʻrgandi, 1975-yilda Vengriya fanlar akademiyasi doktorlik darajasini oldi va 1984-yilda Vengriya Fanlar akademiyasida DSc diplomini oldi[1]. 1971-yildan boshlab Eötvös Loránd universiteti oʻqituvchisi lavozimini egalladi; 1987-yilda u Chikago universiteti algebra va kompyuter fanlari professorlari lavozimini qoʻshdi. 1995- yilda u Chikagoda matematika boʻlimida birgalikda tayinlanishni boshladi va Eötvös Lorándda lavozimidan voz kechdi[1].
U 180 dan ortiq ilmiy maqolalarning muallifidir[1]. Uning diqqatga sazovor yutuqlari orasida interaktiv dalil tizimlari, Las-Vegas algoritmi[2] va grafika izomorfizm sinovlarida guruh nazariy usullarini joriy etish kiradi[3]. 2015- yil noyabr oyida u graf isomorfizm muammosi uchun quasipolinom vaqt algoritmini eʼlon qildi[4][5].
U „Theory of Computing“ jurnalining bosh muharriri[6]. Babai shuningdek, „Budapest semestrlari“ matematika dasturini yaratishda ishtirok etdi va birinchi marta bu nomni yaratdi.
Quasipolinom vaqtida graf isomorfizm
[tahrir | manbasini tahrirlash]Babai 2015 yilda natijalarni eʼlon qilganidan soʻng[5][7] ACM Kompyuter nazariyasi simpoziumida grafika izomorfizmi muammosi 2016-yilda kvaz-polinomli vaqtda hal qilinishi mumkinligini isbotlovchi maqola taqdim etdi[8]. Harald Helfgott tomonidan aniqlangan xatoga javoban u 2017- yilda yangilanishni joylashtirdi[9].
Mahrlar
[tahrir | manbasini tahrirlash]1988-yilda Babai Vengriya davlat mukofotiga sazovor boʻldi, 1990-yilda Vengriya Fanlar akademiyasining muxbir aʼzosi etib saylandi va 1994-yilda toʻliq aʼzo boʻldi[1]. 1999-yilda Budapeşt texnologiyasi va iqtisodiyot universiteti unga faxriy doktorlik darajasini berdi[1].
1993-yilda Babai interaktiv dalil tizimlari boʻyicha maʼruzalari uchun Shafi Goldwasser, Silvio Micali, Shlomo Moran va Charlz Rakoff bilan birgalikda Gödel mukofoti sazovor boʻldi.
2015-yilda u Amerika sanʼat va fanlar akademiyasi aʼzosi etib saylandi va Knuth mukofoti sazovor boʻldi[10].
Babai Kiotoda (1990), Zürich (1994, plenar nutq) va Rio-de-Janeyro (2018) boʻlib oʻtgan Xalqaro matematiklar kongresslari taklif etilgan nutqchi boʻlgan.
Havolalar
[tahrir | manbasini tahrirlash]- Professor László Babai’s algorithm is next big step in conquering isomorphism in graphs // Published on Nov 20, 2015 Division of the Physical Sciences / The University of Chicago
- Mathematician claims breakthrough in complexity theory, by Adrian Cho 10 November 2015 17:45 // Posted in Math, Science AAAS News
- A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015, by j2kun
- Landmark Algorithm Breaks 30-Year Impasse, Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015 [sayt ishlamaydi]
- A Little More on the Graph Isomorphism Algorithm // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
Manbalar
[tahrir | manbasini tahrirlash]- ↑ 1,0 1,1 1,2 1,3 1,4 1,5 Curriculum vitae from Babai’s web site, retrieved 2016-01-28.
- ↑ Babai, László; Moran, Shlomo (1988), „Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class“, J. Comput. Syst. Sci., 36-jild, № 2, 254–276-bet, doi:10.1016/0022-0000(88)90028-1.
- ↑ Babai, László (1979), Monte-Carlo algorithms in graph isomorphism testing (PDF), Tech. Report, Université de Montréal.
- ↑ Cho, Adrian (November 10, 2015), „Mathematician claims breakthrough in complexity theory“, Science, doi:10.1126/science.aad7416
- ↑ 5,0 5,1 Klarreich. „Landmark Algorithm Breaks 30-Year Impasse“. quantamagazine.org. Quanta Magazine (2015-yil 14-dekabr).
- ↑ Theory of Computing editors, retrieved 2010-07-30.
- ↑ A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
- ↑ Babai, László (2016), „Graph Isomorphism in Quasipolynomial Time [Extended Abstract]“, Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC '16), New York, NY, USA: ACM, 684–697-bet, arXiv:1512.03547, doi:10.1145/2897518.2897542, ISBN 978-1-4503-4132-5, S2CID 17118954
- ↑ László Babai: Fixing the UPCC case of Split-or-Johnson, posted on 14 January 2017
- ↑ American Academy of Arts and Sciences. 2015 Fellows and Their Affiliations