Babai, Laszlo

Laszlo Babai
hængt. Babai Laszlo
Fødselsdato 20. juli 1950( 1950-07-20 ) (72 år)
Fødselssted
Land
Videnskabelig sfære kombinatorik
Arbejdsplads
Alma Mater
videnskabelig rådgiver Turan, Pal og Shosh, Vera [2]
Priser og præmier Gödel-prisen ( 1993 ) Knuth-prisen ( 2015 )
Internet side people.cs.uchicago.edu/~…
 Mediefiler på Wikimedia Commons

Laszlo Babai ( ungarsk Babai László ; født 20. juli 1950 , Budapest ) [3]  er en ungarsk og amerikansk videnskabsmand, professor i matematik og datalogi ved University of Chicago . Hans forskning fokuserer på følgende grene: beregningskompleksitetsteori , algoritmeteori , kombinatorik og endelige grupper med vægt på interaktioner mellem disse grene. Forfatter til mere end 180 videnskabelige artikler. [3]

Biografi

Babai studerede matematik ved Eötvös Loránd Universitetet i Budapest fra 1968 til 1973 og modtog en ph.d. ved det ungarske videnskabsakademi i 1975, og modtog en D.Sc. i det ungarske videnskabsakademi i 1984. [3] [4] Han har arbejdet i USA siden 1987.

Forfatter af Las Vegas-algoritmen (1979), en version af Monte Carlo-metoden . [5]

Grafisk isomorfi i kvasipolynomisk tid

Fra 10. november til 1. december 2015, på seminaret "Combinatorics and Theoretical Computer Science" ved University of Chicago, lavede han tre rapporter "Graph Isomorphism in Quasipolynomial Time ", hvori han skitserede en algoritme, der løser problemet af grafisomorfi i en kvasi -polynomisk tidsperiode, hvor antal hjørner, polynomium i . [6] [7] [8] [9]

10. december 2015 offentliggjorde en video af den første rapport [10] .

December 11, 2015 i arXiv.org publicerede en artikel af samme navn "Graph Isomorphism in Quasipolynomial Time" [11] .

abstrakt

Vi viser, at Graph Isomorphism (GI) problemet og de relaterede problemer med String Isomorphism [12] (under handlingsgruppe) (SI) og Coset Intersection (CI) [13] [14] kan løses i kvasipolynomium

tid. Den bedste tidligere bundet til GI var

hvor er antallet af hjørner (

Luks , 1983); for de to andre problemer var grænsen den samme,

hvor er størrelsen af ​​permutationsdomænet (Babai, 1983).


Algoritmen bygger på Luks' SI-ramme og angriber barrierekonfigurationerne for Luks' algoritmegruppe ved hjælp af teoretiske "lokale certifikater og kombinatoriske kanoniske partitioneringsteknikker. Vi viser, at Johnson-grafer i en veldefineret forstand er de eneste hindringer for effektiv kanonisk opdeling.

Se også

  • Liste over uløste problemer i datalogi

Noter

  1. ↑ http://news.uchicago.edu/profile/laszlo-babai
  2. ↑ 1 2 Matematisk genealogi  (engelsk) - 1997.
  3. ↑ 1 2 3 Curriculum vitae Arkiveret 11. februar 2014. // Babais websted Arkiveret 7. november 2017 på Wayback Machine
  4. ↑ Babai, Laszlo  (eng.) i Mathematical Genealogy Project
  5. ↑ "'Laszlo Babai'", Monte-Carlo-algoritmer i grafisomorfi-testning Arkiveret 8. december 2017 på Wayback Machine , Université de Montréal, DMS nr. 79-10 .
  6. ↑ 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
  7. ↑ A Big Result on Graph Isomorphism Arkiveret 10. juli 2017 på Wayback Machine // 4. november 2015, A Fast Graph Isomorphism Algorithm Arkiveret 29. juli 2017 på Wayback Machine // 11. november 2015
  8. ↑ Combinatorics and Theoretical Computer Science Arkiveret 22. december 2015. kalender // Teoretisk datalogi ved University of Chicago Arkiveret 22. oktober 2017 på Wayback Machine . 24. november 2015, Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time II: The Split-or-Johnson rutine" (Kombinatorik og TCS seminar)
  9. ↑ Påstået Breakthrough Slays Classic Computing Problem Arkiveret 22. januar 2016 på Wayback Machine // MIT Technology Review, af Tom Simonite den 13. november 2015
  10. ↑ Graph Isomorphism in Quasipolynomial Time I Archived September 12, 2018 at the Wayback Machine , forelæsningsseminar ved László Babai den 10. november 2015. The University of Chicago // youtube, 1 time. 40 min. Udgivet den 10. december 2015
  11. ↑ Laszlo Babai. Graph Isomorphism in Quasipolynomial Time , 84 sider / abstrakt Arkiveret 22. november 2017 på Wayback Machine // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fre, 11. december 2015 08:04:26 GMT
  12. ↑ "'Definition 2.3."' String Isomorphism Archived 28 March 2018 at the Wayback Machine // Google Books, in: Transactions on Computational Science V Archived 29 March 2018 at the Wayback Machine . Specialnummer om kognitiv videnrepræsentation. Chefredaktører: Marina L. Gavrilova, CJ Kenneth Tan. Redaktører: Yingxu Wang, Keith Chan Arkiveret 28. marts 2018 på Wayback Machine / Lecture Notes in Computer Science / bind 5540, Springer Verlag , 2009
  13. ↑ Coset intersection problem Arkiveret 29. marts 2018 på Wayback Machine // The Group Properties Wiki Arkiveret 22. oktober 2017 på Wayback Machine (beta)
  14. ↑ Complexity of the coset intersection problem Arkiveret 24. december 2015 på Wayback Machine // Teoretisk Computer Science Stack Exchange
    Graph Isomorphism Problem Arkiveret 29. marts 2018 på Wayback Machine // ibid.
    Complexity of simple undirected graph isomorphism problem Arkiveret 29. marts 2018 på Wayback Machine // ibid.

Links

kopi Arkivkopi dateret 4. marts 2016 på Wayback Machine fra Lenta.ru // texnomaniya.ru, 20. november 2015 En hurtig algoritme for grafisomorfiproblemet er blevet offentliggjort Arkiveret 3. juli 2017 på Wayback Machine
  Gå til Wikidata-elementet  Tematiske steder
I bibliografiske kataloger
 Vindere af Knuth-prisen