„Babai László” változatai közötti eltérés

Kutatási területe a [[kombinatorika]], a [[csoportelmélet]] és a [[komplexitáselmélet]]{{wd|Q205084}}. Még diákkorában foglalkozott [[gráf]]ok 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]]{{wd|Q1412905}} rendje legfeljebb

<center><math> e^{(4\sqrt n\log^2n)}.</math></center> Megalkotta az [[interaktív bizonyítás]]{{wd|Q1665886}} fogalmát.

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ó.<ref>Laszlo Babai (University of Chicago): [https://calendar.google.com/calendar/render?eid=czNzOXNtZ2tydG00OG5obDJlZ3I3c21uY2cgYzU3c2hpY2k0NW0xN3FsMGdodmw1NmVrMzhAZw&ctz=America/Chicago&pli=1&t=AKUaPmbNo4fEHI_fQA5RP4AEOVRvY_38tKCShSSp7z2RGnSSoAFNkqX7djaXeyZLSyiagv-Jnb0pK6iajFFbAnvp8q5SsF0K4g&sf=true&output=xml#eventpage_6 Graph Isomorphism in Quasipolynomial Time I]: The "Local Certificates Algorithm" // Combinatorics and Theoretical Computer Science seminar, 10 November 2015, 15:00 – 16:00</ref><ref>[https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ A Big Result On Graph Isomorphism] // November 4, 2015, [https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ A Fast Graph Isomorphism Algorithm] // November 11, 2015</ref><ref>[http://www.math.uchicago.edu/calendar?calendar=Combinatorics%20and%20Theoretical%20Computer%20Science Combinatorics and Theoretical Computer Science] calendar // [http://theory.cs.uchicago.edu/index.php 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)</ref><ref>[http://www.technologyreview.com/news/543511/claimed-breakthrough-slays-classic-computing-problem-encryption-could-be-next/ Claimed Breakthrough Slays Classic Computing Problem] // MIT Technology Review, by Tom Simonite on November 13, 2015</ref> Az előadás videofelvételét 2015. december 10-én tették közzé,<ref>[https://www.youtube.com/watch?v=qYIhA3O9Nz0 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</ref> majd egy előzetes változata a cikknek másnap felkerült az [[arXiv.org]]{{wd|Q118398}} oldalra.<ref name=arXiv>László Babai. [http://arxiv.org/pdf/1512.03547v1 Graph Isomorphism in Quasipolynomial Time], 84 pages / [http://arxiv.org/abs/1512.03547v1 abstract] // [[arXiv.org]] > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT</ref>

*[[Gödel-díj]]{{wd|Q1417143}} (1993)

*[[Knuth-díj]]{{wd|Q1165991}} (2015)<ref>[http://mta.hu/mta_hirei/babai-laszlo-nyerte-a-knuth-dijat-a-szamitastudomany-rangos-elismereset-136410/ Babai László nyerte a Knuth-díjat, a számítástudomány rangos elismerését]</ref>

== MegjegyzésekJegyzetek ==

* MTI Ki Kicsoda 2009, Magyar Távirati Iroda Zrt., Budapest, 2008, 41. old., {{ISSN|1787-288X}}

* [http://www.mta.hu/index.php?id=421&TID=24 Adatlap a Magyar Tudományos Akadémia honlapján]

* [http://people.cs.uchicago.edu/~laci/CV.pdf Szakmai életrajz a Chicagói Egyetem honlapján] {{hivnyelv|angolul}}