Babai László

A Wikipédiából, a szabad enciklopédiából
Babai László
Babai László egy konferencián 2013-ban
Babai László egy konferencián 2013-ban
Született 1950. július 20. (66 éves)
Budapest
Állampolgársága Magyarország
Nemzetisége magyar
Foglalkozása matematikus,
egyetemi tanár
Díjak Gödel Prize (1993)
Kitüntetései MTA-tag, l. 1990, r. 1995
Commons
A Wikimédia Commons tartalmaz Babai László témájú médiaállományokat.

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.

Életpályája[szerkesztés]

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. Ugyanekkor a Chicagói Egyetem Számítástudományi Intézetében kapott professzori állást, előbb félállásban, majd 1994-ben főállásban oktat (1984 és 1986 között vendégprofesszor volt). 1987 és 1989 között a Budapesti Műszaki Egyetem Villamosmérnöki Karán 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.

Munkássága[szerkesztés]

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

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

Gráfizomorfizmus kvázipolinomiális időben[szerkesztés]

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

Absztrakt

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism[9] (under group action) (SI) and Coset Intersection (CI)[10][11] can be solved in quasipolynomial time. The best previous bound for GI was where is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, where 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[szerkesztés]

Főbb publikációi[szerkesztés]

  • 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)

Megjegyzések[szerkesztés]

  1. Egyes iratokban Laci néven szerepel.
  2. László Babai, Paul Erdős, Stanley M. Selkow: Random Graph Isomorphism. SIAM J. Comput. 9(3): 628-635 (1980)
  3. 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
  4. A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
  5. Combinatorics and Theoretical Computer Science 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)
  6. Claimed Breakthrough Slays Classic Computing Problem // MIT Technology Review, by Tom Simonite on November 13, 2015
  7. 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
  8. 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
  9. Definition 2.3. String Isomorphism, in: Transactions on Computational Science V. Special Issue on Cognitive Knowledge Representation. Editors-in-Chief: Marina L. Gavrilova, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan / Lecture Notes in Computer Science / Volume 5540, Springer Verlag, 2009
  10. Coset intersection problem // The Group Properties Wiki (beta)
  11. Complexity of the coset intersection problem // Theoretical Computer Science Stack Exchange, asked Sep 25 2014 at 9:43
  12. Babai László nyerte a Knuth-díjat, a számítástudomány rangos elismerését

Források[szerkesztés]