Babai László
Sablon:Személy infobox Babai László[1] (Budapest, 1950. július 20. –) magyar matematikus, egyetemi tanár, a Magyar Tudományos Akadémia rendes tagja. A kombinatorika, a csoportelmélet neves kutatója. 1994 óta a Chicagói Egyetemen tanít főállásban.[2]
Életpályája
1968-ban érettségizett a Fazekas Mihály Fővárosi Gyakorló Gimnáziumban, majd felvették az Eötvös Loránd Tudományegyetem Természettudományi Kar matematika szakára, ahol 1973-ban szerzett matematikus diplomát. Közben 1971-ben egy szemesztert töltött a Leningrádi Egyetemen. Diplomájának megszerzése után az egyetem algebra és számelmélet tanszékén kezdett el dolgozni. 1980 és 1983 között az MTA Számítástechnikai és Automatizálási Kutatóintézetének tanácsadója volt. 1985-ben Lovász Lászlóval létrehozta a Budapest Semesters in Mathematics-t, ahol az igazgatótanács elnöke lett. 1987-ben kapott egyetemi tanári kinevezést. 1984-től a Chicagói Egyetem Számítástudományi Intézetében is tanít, előbb vendégprofesszorként (1986-ig), makd félállásban és 1994-től főállásban oktat. 1987 és 1989 között a Budapesti Műszaki Egyetem Villamosmérnöki Karán is volt vendégtanár.
1975-ben védte meg a matematikai tudományok kandidátusi, 1984-ben akadémiai doktori értekezését. A Magyar Tudományos Akadémia Matematikai Bizottságának lett tagja. 1990-ben megválasztották az MTA levelező, 1995-ben rendes tagjává. A Bolyai János Matematikai Társulat felvette tagjai közé. 1981-ben Erdős Pállal és Lovász Lászlóval útjára indította a Combinatorica című folyóiratot, amelynek alapító főszerkesztője lett. A Theory of Computing című elektronikus folyóirat alapítója és főszerkesztője. 2010-től a Chicagói Egyetem „George and Elizabeth Yovovich” professzora.
Munkássága
Kutatási területe a kombinatorika, a csoportelmélet és a komplexitáselméletSablon:Wd. Még diákkorában foglalkozott gráfok automorfizmusaival. Az izomorfizmus-algoritmusok területén úgynevezett mély csoportelméleti eszközöket alkalmazott, főleg a részcsoporttorony-módszert. Emellett egy százéves csoportelméleti problémát megoldva bebizonyította, hogy egy n-edfokú primitív, nem kétszeresen tranzitív permutációcsoportSablon:Wd rendje legfeljebb
Megalkotta az interaktív bizonyításSablon:Wd fogalmát.
Több mint száznyolcvan kombinatorikával, algebrával és számítástudománnyal foglalkozó tudományos publikációja jelent meg, amelyeket jelentős részben angol nyelven adott ki. Erdős-száma 1.[3]
Gráfizomorfizmus kvázipolinomiális időben
2015. november 10. és december 1. között Babai három előadást tartott a Chicagói Egyetem Kombinatorika és elméleti számítástudomány szemináriumán „Gráfizomorfizmus kvázipolinomiális időben” témakörben. Az általa körvonalazott bizonyítás megmutatta, hogy a gráfizomorfizmus-probléma kvázipolinomiális időben (a polinomiális és az exponenciális közötti idő alatt) megoldható.[4][5][6][7] Az előadás videófelvételét 2015. december 10-én tették közzé,[8] majd egy előzetes változata a cikknek másnap felkerült az arXiv.orgSablon:Wd oldalra.[9] Sablon:Rejtett
Díjai, elismerései
- Grünwald Géza-díj (1972)
- MTA Matematikai Díj (1983)
- Állami Díj (1988) – Az algebra és számításelmélet terén elért nemzetközileg is kiemelkedő eredményeiért és kiváló oktató, iskolateremtő tevékenységéért.
- Gödel-díjSablon:Wd (1993)
- Szele Tibor-emlékérem (1993)
- a Budapesti Műszaki és Gazdaságtudományi Egyetem díszdoktora (1999)
- Llewellyn John and Harriet Manchester Quantrell Award (2005)
- Knuth-díjSablon:Wd (2015)[10]
Főbb publikációi
- On the Order of Uniprimitive Permutation Groups (1981)
- Computational complexity in Finite Groups (1990, 1991)
- Linear Algebraic Methods in Combinatorics (Frankl Péterrel, 1992)
- Automorphism Groups, Isomorphism, Reconstruction (1995)
Érdekesség
A Csillagkapu: Atlantisz című amerikai–kanadai sci-fi televíziós sorozat 5. évadának 10. epizódjában szóba kerül a neve:
- Ezredes, találtam valamit. Feltételezem, hogy mint mondta, a szerkezet, amit elvittek végigsugárzott valamit a szubtérben.
- Tudja követni?
- Ha Atlantiszról sugározna, igen tudnám, de láthatóan már nincs így.
- Szóval?
- Szóval. Babai László munkáját használom segítségként. Tudja, kombinatorika és… ne vegye zokon, de olyan bonyolult, nem tudom eléggé lebutítani, hogy értelmes legyen.
- Csak rajta!
Jegyzetek
Források
- Sablon:MTA1825-2002
- MTI Ki Kicsoda 2009, Magyar Távirati Iroda Zrt., Budapest, 2008, 41. old., Sablon:ISSN
- Adatlap a Magyar Tudományos Akadémia honlapján
- Szakmai életrajz a Chicagói Egyetem honlapján Sablon:Hivnyelv
- ↑ Egyes iratokban Laci néven szerepel.
- ↑ Curriculum Vitae a Chicagói Egyetem honlapján
- ↑ László Babai, Paul Erdős, Stanley M. Selkow: Random Graph Isomorphism. SIAM J. Comput. 9(3): 628-635 (1980)
- ↑ Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time I: The "Local Certificates Algorithm" // Combinatorics and Theoretical Computer Science seminar, 10 November 2015, 15:00 – 16:00
- ↑ A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
- ↑ Combinatorics and Theoretical Computer Science Sablon:Wayback calendar // Theoretical Computer Science at the University of Chicago. November 24, 2015, Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time II: The "Split-or-Johnson routine" (Combinatorics and TCS seminar)
- ↑ Claimed Breakthrough Slays Classic Computing Problem Sablon:Wayback // MIT Technology Review, by Tom Simonite on November 13, 2015
- ↑ Graph Isomorphism in Quasipolynomial Time I, seminar lecture by László Babai on November 10, 2015. The University of Chicago // youtube, 1 год. 40 хв. Опубліковано 10 грудня 2015
- ↑ László Babai. Graph Isomorphism in Quasipolynomial Time, 84 pages / abstract // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT
- ↑ Babai László nyerte a Knuth-díjat, a számítástudomány rangos elismerését