Babai, Laszlo

Laszlo Babai
spânzurat. Babai Laszlo
Data nașterii 20 iulie 1950( 20.07.1950 ) (72 de ani)
Locul nașterii
Țară
Sfera științifică combinatorică
Loc de munca
Alma Mater
consilier științific Turan, Pal și Shosh, Vera [2]
Premii și premii Premiul Gödel ( 1993 ) Premiul Knuth ( 2015 )
Site-ul web people.cs.uchicago.edu/~…
 Fișiere media la Wikimedia Commons

Laszlo Babai ( în maghiară Babai László ; născut la 20 iulie 1950 , Budapesta ) [3]  este un om de știință maghiar și american, profesor de matematică și informatică la Universitatea din Chicago . Cercetarea sa se concentrează pe următoarele ramuri: teoria complexității computaționale , teoria algoritmilor , combinatorie și grupuri finite, cu accent pe interacțiunile dintre aceste ramuri. Autor a peste 180 de lucrări științifice. [3]

Biografie

Babai a studiat matematica la Universitatea Eötvös Loránd din Budapesta din 1968 până în 1973, primind un doctorat. la Academia Maghiară de Științe în 1975 și a primit un D.Sc. la Academia Maghiară de Științe în 1984. [3] [4] Lucrează în SUA din 1987.

Autor al algoritmului Las Vegas (1979), o versiune a metodei Monte Carlo . [5]

Izomorfism grafic în timp cvasipolinomial

În perioada 10 noiembrie - 1 decembrie 2015, la seminarul „Combinatorics and Theoretical Computer Science” de la Universitatea din Chicago, a realizat trei rapoarte „Graph Isomorphism in Quasipolynomial Time ”, în care a conturat un algoritm care rezolvă problema de izomorfism grafic într-o perioadă de timp cvasi -polinomială , unde numărul de vârfuri, polinom în . [6] [7] [8] [9]

10 decembrie 2015 a publicat un videoclip al primului raport [10] .

11 decembrie 2015 în arXiv.org a publicat un articol cu ​​același nume „Graph Isomorphism in Quasipolynomial Time” [11] .

abstract

Arătăm că problema Graph Isomorphism (GI) și problemele conexe ale String Isomorphism [12] (sub grup de acțiuni) (SI) și Coset Intersection (CI) [13] [14] pot fi rezolvate în cvasipolinom.

timp. Cea mai bună legătură anterioară pentru GI a fost

unde este numărul de vârfuri (

Luks , 1983); pentru celelalte două probleme, limita a fost similară,

unde este dimensiunea domeniului de permutare (Babai, 1983).


Algoritmul se bazează pe cadrul SI al lui Luks și atacă configurațiile barierelor pentru grupul de algoritmi al lui Luks prin „certificate locale teoretice și tehnici combinatorii de partiționare canonică. Arătăm că, într-un sens bine definit, graficele Johnson sunt singurele obstacole în calea partiționării canonice eficiente.

Vezi și

  • Lista problemelor nerezolvate în informatică

Note

  1. ↑ http://news.uchicago.edu/profile/laszlo-babai
  2. ↑ 1 2 Genealogie matematică  (engleză) - 1997.
  3. ↑ 1 2 3 Curriculum vitae Arhivat 11 februarie 2014. // Site-ul web al lui Babai Arhivat 7 noiembrie 2017 la Wayback Machine
  4. ↑ Babai, Laszlo  (ing.) în proiectul de genealogie matematică
  5. ↑ „‘Laszlo Babai’”, Algoritmi Monte-Carlo în testarea izomorfismului grafic Arhivat 8 decembrie 2017 la Wayback Machine , Université de Montréal, DMS nr. 79-10 .
  6. ↑ Laszlo Babai (Universitatea din Chicago): Graph Isomorphism in Quasipolynomial Time I : The "Local Certificates Algorithm" // Seminarul Combinatorică și Teoretică Informatică, 10 noiembrie 2015, 15:00 - 16:00
  7. ↑ A Big Result On Graph Isomorphism Arhivat 10 iulie 2017 la Wayback Machine // 4 noiembrie 2015, A Fast Graph Isomorphism Algorithm Arhivat 29 iulie 2017 la Wayback Machine // 11 noiembrie 2015
  8. ↑ Combinatorică și informatică teoretică Arhivat 22 decembrie 2015. calendar // Teoretică Informatică la Universitatea din Chicago Arhivat 22 octombrie 2017 la Wayback Machine . 24 noiembrie 2015, Laszlo Babai (Universitatea din Chicago): Graph Isomorphism in Quasipolynomial Time II: The Split-or-Johnson routine” (Combinatorică și seminar TCS)
  9. ↑ Claimed Breakthrough Slays Classic Computing Problem Arhivat 22 ianuarie 2016 la Wayback Machine // MIT Technology Review, de Tom Simonite pe 13 noiembrie 2015
  10. ↑ Graph Isomorphism in Quasipolynomial Time I Archived 12 septembrie 2018 la Wayback Machine , seminar de prelegeri susținut de László Babai pe 10 noiembrie 2015. Universitatea din Chicago // youtube, 1 oră. 40 min. Postat pe 10 decembrie 2015
  11. ↑ Laszlo Babai. Graph Isomorphism in Quasipolynomial Time , 84 pagini / rezumat Arhivat 22 noiembrie 2017 la Wayback Machine // arXiv.org > cs > arXiv:1512.03547 / versiunea 1 [v1] Vineri, 11 decembrie 2015 08:04:26 GMT
  12. ↑ „‘Definition 2.3.”’ String Isomorphism Arhivat la 28 martie 2018 la Wayback Machine // Google Books, în: Transactions on Computational Science V Arhivat la 29 martie 2018 la Wayback Machine . Număr special privind reprezentarea cunoștințelor cognitive. Redactori-șefi: Marina L. Gavrilova, CJ Kenneth Tan. Editori: Yingxu Wang, Keith Chan Arhivat 28 martie 2018 la Wayback Machine / Lecture Notes in Computer Science / Volumul 5540, Springer Verlag , 2009
  13. ↑ Problemă de intersecție Coset Arhivat la 29 martie 2018 la Wayback Machine // The Group Properties Wiki Arhivat la 22 octombrie 2017 la Wayback Machine (beta)
  14. ↑ Complexitatea problemei de intersecție a claselor Arhivat la 24 decembrie 2015 la Wayback Machine // Theoretical Computer Science Stack Exchange
    Graph Isomorphism Problem Arhivat la 29 martie 2018 la Wayback Machine // ibid.
    Complexitatea problemei izomorfismului de graf nedirecționat simplu Arhivat 29 martie 2018 la Wayback Machine // ibid.

Link -uri

copie Copie de arhivă din 4 martie 2016 pe Wayback Machine de pe Lenta.ru // texnomaniya.ru, 20 noiembrie 2015 Un algoritm rapid pentru problema izomorfismului grafic a fost publicat Arhivat 3 iulie 2017 la Wayback Machine
  Accesați articolul Wikidata  Site-uri tematice
În cataloagele bibliografice
 Câștigătorii premiului Knuth