Babai László

Babai László
Babai László egy konferencián 2013-ban
Született	1950. július 20. (73 éves) Budapest
Állampolgársága	magyar
Nemzetisége	magyar
Foglalkozása	matematikus, egyetemi tanár
Iskolái	Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium (–1968) Eötvös Loránd Tudományegyetem (–1973, matematika) Magyar Tudományos Akadémia (–1975, PhD)
Kitüntetései	Erdős Pál-díj Gödel-díj (1993) Knuth-díj (2015) Dijkstra Prize (2016)
weboldal MTMT MTA
A Wikimédia Commons tartalmaz Babai László témájú médiaállományokat.
Sablon • Wikidata • Segítség

Babai László (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.

É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élet. 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ócsoport rendje legfeljebb

$e^{(4{\sqrt {n}}\log ^{2}n)}.$

Megalkotta az interaktív bizonyítás 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.

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ó. Az előadás videófelvételét 2015. december 10-én tették közzé, majd egy előzetes változata a cikknek másnap felkerült az arXiv.org oldalra.

Az arXiv.org cikkének rövid összegzése

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial $\exp \left(\left(\log n\right)^{O\left(1\right)}\right)$ time. The best previous bound for GI was $\exp \left(O\left({\sqrt {n\log n}}\right)\right),$ where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $\quad \qquad \exp \left({\tilde {O}}\left({\sqrt {n}}\right)\right),$ where $n$ is the size of the permutation domain (Babai, 1983).
The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic «local certificates» and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning.

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íj (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íj (2015)

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!

Források

• A Magyar Tudományos Akadémia tagjai 1825–2002 I. (A–H). Főszerk. Glatz Ferenc. Budapest: MTA Társadalomkutató Központ. 2003. 65. o.
• MTI Ki Kicsoda 2009, Magyar Távirati Iroda Zrt., Budapest, 2008, 41. old., ISSN 1787-288X
• Adatlap a Magyar Tudományos Akadémia honlapján
• Szakmai életrajz a Chicagói Egyetem honlapján (angolul)