László Babai

László Babai
Laszlo Babai.jpg
László Babai at Oberwolfach in 2011
Geboren 20. Juli 1950 (Alter 72)
Budapest
Staatsangehörigkeit ungarisch
Alma Mater Ungarische Akademie der Wissenschaften
Auszeichnungen Gödel -Preis (1993)
Knuth -Preis (2015)
Dijkstra -Preis (2016)
Wissenschaftliche Karriere
Felder Informatik, Mathematik
Institutionen Universität von Chicago
Doktorand Pál Turán
Vera T. Sós
Doktorand Mario Szegedy
Gábor Tardos

László "Laci" Babai (Geboren am 20. Juli 1950 in, in Budapest)[1] ist ein ungarisch Professor für Informatik und Mathematik bei der Universität von Chicago. Seine Forschung konzentriert sich auf Computerkomplexitätstheorie, Algorithmen, Kombinatorik, und Finite -Gruppenmit Schwerpunkt auf den Wechselwirkungen zwischen diesen Feldern.

Leben

1968 gewann Babai eine Goldmedaille am Internationale mathematische Olympiade. Babai studierte Mathematik bei Fakultät für Naturwissenschaften des Eötvös Loránd Universität Von 1968 bis 1973 erhielt er einen Ph.D. von dem Ungarische Akademie der Wissenschaften 1975 und erhielt einen D.Sc. von der ungarischen Akademie der Wissenschaften im Jahr 1984.[1][2] Seit 1971 hatte er eine Lehrposition an der Eötvös Loránd University inne; 1987 nahm er gemeinsame Positionen als Professor in ein Algebra in Eötvös Loránd und in Informatik an der Universität von Chicago. 1995 begann er eine gemeinsame Ernennung in der Mathematikabteilung in Chicago und gab seine Position bei Eötvös Loránd auf.[1]

Arbeit

Er ist Autor von über 180 akademischen Papieren.[1] Zu seinen bemerkenswerten Errungenschaften gehört die Einführung von Interaktive Proof -Systeme,[3] die Einführung des Begriffs Las Vegas Algorithmus,[4] und die Einführung von Gruppentheoretik Methoden in Graph Isomorphismus testen.[4] Im November 2015 kündigte er a an Quasipolynomzeit Algorithmus für die Graph Isomorphismus Problem.[5][6]

Er ist Chefredakteurin des Schiedsrichters Online-Journal Theorie des Computers.[7] Babai war auch an der Schaffung der beteiligt Budapest Semester in Mathematik Programm und zuerst den Namen geprägt.

Graph -Isomorphismus in der Quasipolynomzeit

Nach der Ankündigung des Ergebnisses im Jahr 2015,[6][8][9] Babai stellte ein Papier vor, das beweist, dass die Graph Isomorphismus Problem kann gelöst werden Quasi-Polynomzeit 2016 bei der ACM Symposium über die Computertheorie.[10] Als Reaktion auf einen Fehler, der von entdeckt wurde Harald HelfgottEr hat 2017 ein Update veröffentlicht.[11]

abstrakt

Wir zeigen, dass die Graph Isomorphism (GI) Problem und die damit verbundenen Probleme des String -Isomorphismus[12] (unter Gruppenaktion) (SI) und Coset Intersection (CI)[13][14] kann in Quasipolynom gelöst werden Zeit. Die beste vorherige Grenze für GI war wo ist die Anzahl der Eckpunkte (Luks1983); Für die beiden anderen Probleme war die gebundene ähnlich, ähnlich, wo ist die Größe der Permutationsdomäne (Babai, 1983).
Der Algorithmus baut auf dem SI -Framework von Luks auf und greift die Barrierekonfigurationen für Luks 'Algorithmus nach Gruppen -theoretischer «lokaler Zertifikate» und kombinatorische kanonische Partitionierungstechniken an. Wir zeigen das in einem gut definierten Sinne, Johnson -Grafiken sind die einzigen Hindernisse für eine wirksame kanonische Partitionierung.

Ehrungen

1988 gewann Babai den ungarischen Staatspreis, 1990 wurde er zum korrespondierenden Mitglied der ungarischen Akademie der Wissenschaften gewählt und wurde 1994 ein volles Mitglied.[1] 1999 die Budapest Universität für Technologie und Ökonomie verlieh ihm eine Ehrendoktorate.[1]

1993 wurde Babai mit dem ausgezeichnet Gödel -Preis zusammen mit SHAFI GOLDSER, Silvio Micali, Shlomo Moran, und Charles Rackofffür ihre Papiere zu interaktiven Proofsystemen.[15]

2015 wurde er gewählt[16] ein Stipendiat der Amerikanische Akademie für Kunst und Wissenschaftenund gewann die Knuth -Preis.

Babai war ein eingeladener Redner in der Internationale Kongresse von Mathematikern in Kyoto (1990), Zürich (1994, Plenargespräch) und Rio de Janeiro (2018).

Quellen

Kopieren von lenta.ru // texnomaniya.ru, 20.00 Uhr 2015
Опблfolge Archiviert 2017-07-03 bei der Wayback -Maschine // джерелfolgen: хабрахабр, перекладено 16 грудня 2015, 06:30

Verweise

  1. ^ a b c d e f Lebenslauf Von der Website von Babai wurde 2016-01-28 abgerufen.
  2. ^ László Babai Bei der Mathematik Genealogie -Projekt
  3. ^ Babai, László; Moran, Shlomo (1988), "Arthur-Merlin Games: Ein randomisiertes Proof-System und eine Hierarchie der Komplexitätsklasse", J. Comput. System. Sci., 36 (2): 254–276, doi:10.1016/0022-0000 (88) 90028-1.
  4. ^ a b Babai, László (1979), Monte-Carlo-Algorithmen im Graph-Isomorphismus-Test (PDF), Technik. Bericht, Université de Montréal.
  5. ^ Cho, Adrian (10. November 2015), "Mathematiker behauptet Durchbruch in der Komplexitätstheorie", Wissenschaft, doi:10.1126/science.aad7416
  6. ^ a b Klarreich, Erica (14. Dezember 2015). "Landmarkalgorithmus bricht die 30-jährige Sackgasse". mantamagazine.org. Quantenmagazin.
  7. ^ Theorie des Computers Redakteure, abgerufen 2010-07-30.
  8. ^ Ein großes Ergebnis im Graph -Isomorphismus // 4. November 2015, Ein Schnellgrafik -Isomorphismus -Algorithmus // 11. November 2015
  9. ^ Behauptete Durchbruchslays klassisches Computerproblem // MIT Technology Review von Tom Simonite am 13. November 2015
  10. ^ Babai, László (2016), "Graph -Isomorphismus in der Quasipolynomzeit [erweitertes Abstract]", " Proceedings des achtundvierzigsten jährlichen ACM-Symposiums über die Computertheorie (STOC '16), New York, NY, USA: ACM, S. 684–697, Arxiv:1512.03547, doi:10.1145/2897518.2897542, ISBN 978-1-4503-4132-5, S2CID 17118954
  11. ^ László Babai: Reparatur des UPCC-Falles von Split-or-Johnson, veröffentlicht am 14. Januar 2017
  12. ^ Definition 2.3. String -Isomorphismus, in: Transaktionen zur Computerwissenschaft v. Sonderausgabe zur kognitiven Wissensrepräsentation. Chefredakteure: Marina L. Gavrilova, C. J. Kenneth Tan. Herausgeber: Yingxu Wang, Keith Chan / Vorlesungsnotizen in Informatik / Volume 5540, Springer Verlag, 2009
  13. ^ Coset -Intersektionsproblem // Die Gruppeneigenschaften Wiki (Beta)
  14. ^ Komplexität des Coset -Intersektionsproblems // theoretischer Informatik -Stack -Austausch, am 25. September 2014 um 9:43 Uhr gefragt
  15. ^ 1993 Gödel Prize Archiviert 2015-12-08 bei der Wayback -Maschine, ACM Sigact, abgerufen 2010-08-14.
  16. ^ Amerikanische Akademie für Kunst und Wissenschaften. 2015 Fellows und ihre Zugehörigkeiten

Externe Links