| dbo:abstract
|
- László BABAI [lAslO], laŭ hungarlingve kutima nomordo Babai László estis hungara matematikisto, profesoro, membro ordinara de Hungara Scienca Akademio (1995). László Babai naskiĝis [1] la 20-an de julio 1950 en Budapeŝto. (eo)
- László Babai, apodado Laci por sus colegas y nacido el 20 de julio de 1950 en Budapest, es catedrático de Matemática y Computación en la Universidad de Chicago. Su investigación se centra en la teoría de la complejidad computacional, algoritmos, combinatoria y los grupos finitos, haciendo hincapié en la interacción de estos campos. Es autor de más de 150 obras académicas. Entre sus logros destacan la introducción de los sistemas de demostración interactivos (vide [1]), el uso del término «algoritmo de Las Vegas» y métodos teóricos de grupo en la comprobación del isomorfismo de grafos (vide [2] para estos dos últimos). Obtuvo su doctorado de la Academia de Ciencias de Hungría en 1975. Es editor jefe de la revista electrónica Theory of Computing. También formó parte del desarrollo del programa de «Semestres de Budapest en Matemáticas», para estudiantes de los EE. UU. en Hungría ([3]). Su número de Erdős es uno. (es)
- László Babai (* 20. Juli 1950 in Budapest) ist ein ungarischer Mathematiker, der sich mit Kombinatorik, Algorithmentheorie und Komplexitätstheorie beschäftigt. Babai promovierte 1975 an der Ungarischen Akademie der Wissenschaften in Budapest bei Pál Turán (und Vera T. Sós, mit der Arbeit Automorphismengruppen von Graphen). Er ist Professor für Mathematik und Informatik an der University of Chicago. Babai ist gleichzeitig mit Shafi Goldwasser, Silvio Micali, Charles Rackoff einer der Erfinder von Interaktiven Beweissystemen. Von ihm stammt der Begriff des Las-Vegas-Algorithmus für einen Zufallszahlen verwendenden Algorithmus, der nachweisbar immer korrekte Lösungen liefert (sowie mit endlichem Erwartungswert der Laufzeit). Er führte diesen Begriff in einem Aufsatz über Algorithmen zum Test der Isomorphie von Graphen 1979 ein. Er untersuchte auch algorithmische Fragen in der Gruppentheorie. Babais nearest-plane-Algorithmus ist ein Verfahren, das im n-dimensionalen euklidischen Raum zu einem vorgegebenen Punkt einen Gitterpunkt eines n-dimensionalen Zahlengitters findet, der den nächstliegenden Gitterpunkt approximiert. 2015 kündigte er eine wesentliche Verbesserung einer vorherigen Abschätzung von ihm und Eugene Luks (1983) an, indem er zeigte, dass das Graph-Isomorphismus-Problem in quasipolynomieller Zeit gelöst werden kann. Harald Helfgott fand, wie Babai Anfang Januar 2017 bekanntgab, einen Fehler im Beweis, der nach Babai aber behoben werden konnte. Das Graph-Isomorphismus-Problem, die Frage welcher Komplexitätsklasse Algorithmen zur Bestimmung der Isomorphie von Graphen angehören, ist eines der großen ungelösten Probleme der Informatik. 1993 erhielt er den Gödel-Preis. 1994 hielt er einen Plenarvortrag auf dem Internationalen Mathematikerkongress (ICM) in Zürich (Transparent Proofs and Limits to Approximation) und 1992 hielt er einen Plenarvortrag auf dem ersten Europäischen Mathematikerkongress in Paris (Transparent Proofs). 1990 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Kyōto (Computational complexity in finite groups) und 2018 in Rio de Janeiro (Groups, Graphs, Algorithms: The Graph Isomorphism Problem). 2015 wurde er in die American Academy of Arts and Sciences gewählt und mit dem Knuth-Preis ausgezeichnet. Babai ist Herausgeber der Online-Zeitschrift Theory of Computing. (de)
- László "Laci" Babai (born July 20, 1950, in Budapest) is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields. (en)
- László Babai ([ˈlaːsloː], [ˈbɒbɒi]), né le 20 juillet 1950 à Budapest, est un professeur de mathématiques et d'informatique hongrois, enseignant actuellement à l'université de Chicago. Il est connu pour les systèmes de preuve interactive, l'introduction du terme « algorithme de Las Vegas » et l'utilisation de méthodes de la théorie des groupes pour le problème de l'isomorphisme de graphes. Il est lauréat du prix Gödel 1993. En décembre 2015 il propose un algorithme quasi-polynomial pour résoudre le problème de l'isomorphisme de graphes, faisant largement descendre la borne de complexité de ce problème qui joue un rôle fondamental en théorie de la complexité NP. Ce résultat émerveille la communauté scientifique de l'algorithmique. (fr)
- László (Laci) Babai (Budapeste, 20 de julho de 1950) é um matemático e cientista da computação húngaro. É professor de matemática e ciência da computação na Universidade de Chicago. Seus focos de pesquisa são complexidade computacional, algoritmos, combinatória e grupos finitos, com ênfase na interação entre estes campos. É autor de mais de 180 artigos científicos. (pt)
- Ласло Бабай (угор. Babai László; 20 липня 1950, Будапешт) — угорський та американський математик, професор математики та інформатики (computer science) в Чиказькому університеті. Його дослідження зосереджені у галузях: теорія складності обчислень, теорія алгоритмів, комбінаторика, та скінченні групи, з наголосом на взаємодію між цими галузями. Автор понад 180 академічних праць. Бабай вивчав математику в Будапештському університеті імені Лоранда Етвеша з 1968 по 1973, отримав Ph.D. в Угорській академії наук у 1975, і отримав D.Sc. в Угорській академії наук у 1984. Автор алгоритму Лас-Вегас (1979), версії методу Монте-Карло. (uk)
- Ласло Бабаи (венг. Babai László; род. 20 июля 1950, Будапешт) — венгерский и американский учёный, профессор математики и информатики (computer science) в Чикагском университете. Его исследования сосредоточены в следующих отраслях: теория сложности вычислений, теория алгоритмов, комбинаторика, и конечные группы с акцентом на взаимодействие между этими отраслями. Автор более 180 научных трудов. (ru)
|
| dbo:academicDiscipline
| |
| dbo:almaMater
| |
| dbo:award
| |
| dbo:birthDate
| |
| dbo:birthPlace
| |
| dbo:doctoralAdvisor
| |
| dbo:doctoralStudent
| |
| dbo:institution
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12205 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:almaMater
| |
| dbp:awards
| |
| dbp:birthDate
| |
| dbp:birthPlace
| |
| dbp:bot
| |
| dbp:caption
|
- Babai at Oberwolfach in 2011 (en)
|
| dbp:content
|
- We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism and Coset Intersection can be solved in quasipolynomial time. The best previous bound for GI was where is the number of vertices ; for the other two problems, the bound was similar, where is the size of the permutation domain . (en)
- The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic «local certificates» and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. (en)
|
| dbp:date
|
- 2017-07-03 (xsd:date)
- January 2018 (en)
|
| dbp:doctoralAdvisor
| |
| dbp:doctoralStudents
| |
| dbp:fields
|
- Computer Science, Mathematics (en)
|
| dbp:fixAttempted
| |
| dbp:header
| |
| dbp:name
| |
| dbp:nationality
| |
| dbp:url
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:workplaces
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- László BABAI [lAslO], laŭ hungarlingve kutima nomordo Babai László estis hungara matematikisto, profesoro, membro ordinara de Hungara Scienca Akademio (1995). László Babai naskiĝis [1] la 20-an de julio 1950 en Budapeŝto. (eo)
- László "Laci" Babai (born July 20, 1950, in Budapest) is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields. (en)
- László (Laci) Babai (Budapeste, 20 de julho de 1950) é um matemático e cientista da computação húngaro. É professor de matemática e ciência da computação na Universidade de Chicago. Seus focos de pesquisa são complexidade computacional, algoritmos, combinatória e grupos finitos, com ênfase na interação entre estes campos. É autor de mais de 180 artigos científicos. (pt)
- Ласло Бабаи (венг. Babai László; род. 20 июля 1950, Будапешт) — венгерский и американский учёный, профессор математики и информатики (computer science) в Чикагском университете. Его исследования сосредоточены в следующих отраслях: теория сложности вычислений, теория алгоритмов, комбинаторика, и конечные группы с акцентом на взаимодействие между этими отраслями. Автор более 180 научных трудов. (ru)
- László Babai (* 20. Juli 1950 in Budapest) ist ein ungarischer Mathematiker, der sich mit Kombinatorik, Algorithmentheorie und Komplexitätstheorie beschäftigt. Babai promovierte 1975 an der Ungarischen Akademie der Wissenschaften in Budapest bei Pál Turán (und Vera T. Sós, mit der Arbeit Automorphismengruppen von Graphen). Er ist Professor für Mathematik und Informatik an der University of Chicago. Babai ist Herausgeber der Online-Zeitschrift Theory of Computing. (de)
- László Babai, apodado Laci por sus colegas y nacido el 20 de julio de 1950 en Budapest, es catedrático de Matemática y Computación en la Universidad de Chicago. Su investigación se centra en la teoría de la complejidad computacional, algoritmos, combinatoria y los grupos finitos, haciendo hincapié en la interacción de estos campos. Es autor de más de 150 obras académicas. Obtuvo su doctorado de la Academia de Ciencias de Hungría en 1975. Es editor jefe de la revista electrónica Theory of Computing. Su número de Erdős es uno. (es)
- László Babai ([ˈlaːsloː], [ˈbɒbɒi]), né le 20 juillet 1950 à Budapest, est un professeur de mathématiques et d'informatique hongrois, enseignant actuellement à l'université de Chicago. Il est connu pour les systèmes de preuve interactive, l'introduction du terme « algorithme de Las Vegas » et l'utilisation de méthodes de la théorie des groupes pour le problème de l'isomorphisme de graphes. Il est lauréat du prix Gödel 1993. (fr)
- Ласло Бабай (угор. Babai László; 20 липня 1950, Будапешт) — угорський та американський математик, професор математики та інформатики (computer science) в Чиказькому університеті. Його дослідження зосереджені у галузях: теорія складності обчислень, теорія алгоритмів, комбінаторика, та скінченні групи, з наголосом на взаємодію між цими галузями. Автор понад 180 академічних праць. Бабай вивчав математику в Будапештському університеті імені Лоранда Етвеша з 1968 по 1973, отримав Ph.D. в Угорській академії наук у 1975, і отримав D.Sc. в Угорській академії наук у 1984. (uk)
|
| rdfs:label
|
- László Babai (de)
- László Babai (eo)
- László Babai (en)
- László Babai (es)
- László Babai (fr)
- László Babai (pt)
- Бабаи, Ласло (ru)
- Ласло Бабай (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| foaf:name
| |
| is dbo:doctoralAdvisor
of | |
| is dbo:doctoralStudent
of | |
| is dbo:editor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:doctoralAdvisor
of | |
| is dbp:doctoralStudents
of | |
| is dbp:editor
of | |
| is foaf:primaryTopic
of | |
