László Babai - László Babai

László Babai
Laszlo Babai.jpg
László Babai ve společnosti Oberwolfach v roce 2011
narozený (1950-07-20) 20. července 1950 (věk 70)
Budapešť
Národnostmaďarský
Alma materMaďarská akademie věd
OceněníGödelova cena (1993)
Knuth Prize (2015)
Dijkstra cena (2016)
Vědecká kariéra
PolePočítačová věda, Matematika
InstituceUniversity of Chicago
Doktorský poradcePál Turán
Vera T. Sós
DoktorandiMario Szegedy
Gábor Tardos

László "Laci" Babai (narozen 20. července 1950 v Budapešť )[1] je maďarský profesor výpočetní techniky a matematiky na University of Chicago. Jeho výzkum se zaměřuje na teorie výpočetní složitosti, algoritmy, kombinatorika, a konečné skupiny, s důrazem na interakce mezi těmito poli.

Život

V roce 1968 získal Babai zlatou medaili na turnaji Mezinárodní matematická olympiáda. Babai studoval matematiku na Univerzita Eötvöse Loránda v letech 1968 až 1973 získal titul Ph.D. z Maďarská akademie věd v roce 1975 a získal titul D.Sc. z Maďarské akademie věd v roce 1984.[1][2] Od roku 1971 působil jako pedagog na univerzitě Eötvös Loránd; v roce 1987 nastoupil na společné pozice jako profesor algebry na Eötvös Loránd a na informatice na Chicagské univerzitě. V roce 1995 zahájil společné jmenování na katedře matematiky v Chicagu a vzdal se své pozice v Eötvös Loránd.[1]

Práce

Je autorem více než 180 akademických prací.[1]Mezi jeho pozoruhodné úspěchy patří zavedení interaktivní kontrolní systémy,[3] zavedení pojmu Algoritmus Las Vegas,[4] a zavedení skupinový teoretik metody v izomorfismus grafu testování.[4] V listopadu 2015 oznámil kvazipolynomický čas algoritmus pro problém grafového izomorfismu.[5][6]

Je šéfredaktorem online časopisu s recenzemi Teorie výpočtu.[7] Babai se také podílel na tvorbě Semestry z matematiky v Budapešti program a nejprve vytvořil jméno.

Graf izomorfismu v kvazipolynomiálním čase

Po oznámení výsledku v roce 2015[6][8][9]Babai předložila dokument dokazující, že Problém grafového izomorfismu lze vyřešit v kvazi-polynomiální čas v roce 2016 na ACM Symposium on Theory of Computing.[10] V reakci na chybu objevenou uživatelem Harald Helfgott, zveřejnil aktualizaci v roce 2017.[11]

abstraktní

Ukazujeme, že Problém grafového izomorfismu (GI) a související problémy izomorfismu strun[12] (v rámci skupinové akce) (SI) a Coset Intersection (CI)[13][14] lze vyřešit v kvazipolynomu čas. Nejlepší předchozí směřující k GI byl kde je počet vrcholů (Luky, 1983); u ostatních dvou problémů byla vázanost podobná, kde je velikost permutační domény (Babai, 1983).
Algoritmus vychází z Luksova rámce SI a útočí na bariérovou konfiguraci Luksova algoritmu pomocí skupinových teoretických „místních certifikátů“ a kombinačních kanonických technik dělení. Ukazujeme, že v přesně definovaném smyslu Johnsonovy grafy jsou jedinou překážkou účinného kanonického dělení.

Vyznamenání

V roce 1988 získal Babai maďarskou státní cenu, v roce 1990 byl zvolen za příslušného člena Maďarské akademie věd a v roce 1994 se stal jejím řádným členem.[1] V roce 1999 Budapešťská technická a ekonomická univerzita udělil mu čestný doktorát.[1]

V roce 1993 byl Babai oceněn Gödelova cena dohromady s Shafi Goldwasser, Silvio Micali, Shlomo Moran, a Charles Rackoff, za jejich články o interaktivních zkušebních systémech.[15]

V roce 2015 byl zvolen[16] kolega z Americká akademie umění a věd, a vyhrál Knuth Prize.

Zdroje

kopírovat from Lenta.ru // texnomaniya.ru, 20 ноября 2015
Опубліковано швидкий алгоритм для задачі ізоморфізму графів // Джерело: Хабрахабр, перекладено 16 грудня 2015, 06:30

Reference

  1. ^ A b C d E F Životopis z webu Babai, vyvoláno 2016-01-28.
  2. ^ László Babai na Matematický genealogický projekt
  3. ^ Babai, László; Moran, Shlomo (1988), „Hry Arthur-Merlin: randomizovaný kontrolní systém a hierarchie třídy složitosti“, J. Comput. Syst. Sci., 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1.
  4. ^ A b Babai, László (1979), Algoritmy Monte-Carlo v testování izomorfismu grafů (PDF), Tech. Zpráva, Université de Montréal.
  5. ^ Cho, Adrian (10. listopadu 2015), „Matematik tvrdí průlom v teorii složitosti“, Věda, doi:10.1126 / science.aad7416
  6. ^ A b Klarreich, Erica. „Landmark Algorithm Breakes 30-Year Impasse“. quantamagazine.org. Časopis Quanta.
  7. ^ Teorie výpočtu redaktoři, vyvoláno 2010-07-30.
  8. ^ Velký výsledek izomorfismu grafů // 4. listopadu 2015, Algoritmus rychlého grafu izomorfismu // 11. listopadu 2015
  9. ^ Požadovaný průlom Slays Classic Computing Problem // MIT Technology Review, autor Tom Simonite, 13. listopadu 2015
  10. ^ Babai, László (2016), „Graph Isomorphism in Quasipolynomial Time [Extended Abstract]“, Sborník z osmdesátého osmého výročního sympozia ACM o teorii práce s počítači (STOC '16), New York, NY, USA: ACM, s. 684–697, arXiv:1512.03547, doi:10.1145/2897518.2897542, ISBN  978-1-4503-4132-5
  11. ^ László Babai: Oprava případu UPCC společnosti Split-or-Johnson, zveřejněno 14. ledna 2017
  12. ^ Definice 2.3. Řetězcový izomorfismus, v: Transakce na výpočetní vědě V. Zvláštní vydání o kognitivních znalostech. Hlavní redaktoři: Marina L. Gavrilova, C. J. Kenneth Tan. Redakce: Yingxu Wang, Keith Chan / Přednášky z informatiky / Svazek 5540, Springer Verlag, 2009
  13. ^ Problém křižovatky Coset // Wiki Vlastnosti skupiny (beta)
  14. ^ Složitost problému křižovatky coset // Theoretical Computer Science Stack Exchange, položeno 25. září 2014 v 9:43
  15. ^ Gödelova cena z roku 1993 Archivováno 08.12.2015 na Wayback Machine, ACM SIGACT, vyvoláno 2010-08-14.
  16. ^ Americká akademie umění a věd. Fellows 2015 a jejich přidružení

externí odkazy