László Babai

László Babai

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 einer der Erfinder Interaktiver Beweissysteme[1] (gleichzeitig mit Shafi Goldwasser, Silvio Micali, Charles Rackoff). 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.[2]

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).

Babai ist Herausgeber der Online-Zeitschrift Theory of Computing.

Weblinks

Einzelnachweise

  1. Babai Trading group theory for randomness, Proc. 17. Annual Symposium Theory of Computing, ACM, 1985, und seine Veröffentlichung mit Shlomo Moran Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, Journal of Computer and System Sciences, Band 36, 1988, Seite 254-276
  2. On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica Bd. 6 (1986), S. 1-13

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • László Babai — (called Laci by friends and colleagues), born July 20 1950 in Budapest, is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics …   Wikipedia

  • László Babai — 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,… …   Wikipedia Español

  • László Babai — (20 juillet 1950, Budapest, Hongrie ) est un professeur de mathématiques et d informatique à l université de Chicago. Il est connu pour les systèmes de preuve interactive, l introduction du terme « algorithme de Las Vegas » et l… …   Wikipédia en Français

  • Babai — may refer to: *Babai the Great, 6th century church leader *László Babai, mathematician *Sona Babai, became American citizen at age 105 *Babai, Madhya Pradesh, a town in India *Babai (tribe), a Pashtun tribe in the Pakistan region *Babai Hotel,… …   Wikipedia

  • Babai — ist der Name folgender Personen: Babai der Große (* um 551; † 628), Theologe innerhalb der Assyrischen Kirche des Ostens Babai, auch Barbea († 104/5 oder 112 in Edessa) , christliche Märtyrerin, siehe Sarbelius und Barbea László Babai (* 1950),… …   Deutsch Wikipedia

  • László Lovász — (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes. Sommaire …   Wikipédia en Français

  • Laszlo Lovasz — László Lovász László Lovász László Lovász (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes . Somm …   Wikipédia en Français

  • Interactive proof system — In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to… …   Wikipedia

  • Interaktives Beweissystem — Ein interaktives Beweissystem ist ein Begriff aus der Komplexitätstheorie. Dabei wird eine abstrakte Maschine, in welcher die Informationsverarbeitung durch den Austausch von Nachrichten realisiert ist, beschrieben. Ein interaktives Beweissystem… …   Deutsch Wikipedia

  • Combinatorica — is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors in chief with Paul Erdős as honorary editor in chief. The… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”