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

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

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

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

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

↑ ^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

[cv-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 ^1,5 Curriculum vitae from Babai’s web site, retrieved 2016-01-28.

[2] 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.

[lv79-3] Babai, László (1979), Monte-Carlo algorithms in graph isomorphism testing (PDF), Tech. Report, Université de Montréal.

[4] Cho, Adrian (November 10, 2015), „Mathematician claims breakthrough in complexity theory“, Science, doi:10.1126/science.aad7416

[quanta-5] 5,0 ^5,1 Klarreich. „Landmark Algorithm Breaks 30-Year Impasse“. quantamagazine.org. Quanta Magazine (2015-yil 14-dekabr).

[6] Theory of Computing editors, retrieved 2010-07-30.

[7] A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015

[8] 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

[9] László Babai: Fixing the UPCC case of Split-or-Johnson, posted on 14 January 2017

[10] American Academy of Arts and Sciences. 2015 Fellows and Their Affiliations

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]