László Babai

László Babai ( born July 20, 1950 in Budapest) is a Hungarian mathematician who deals with combinatorics, algorithm theory and complexity theory.

Babai received his doctorate in 1975 at the Hungarian Academy of Sciences in Budapest in Pál Turán ( and Vera T. Sós, with the work of automorphism groups of graphs ). He is a professor of mathematics and computer science at the University of Chicago.

Babai is one of the inventors Interactive Proof Systems (simultaneously with Shafi Goldwasser, Silvio Micali, Charles Rackoff ). From him the concept of the Las Vegas algorithm for a random number comes used algorithm that delivers demonstrable always correct solutions (as well as having a finite expectation value of the term). He introduced this term in an essay on algorithms for testing isomorphism of graphs 1979. He also studied algorithmic questions in group theory.

Babai nearest -plane algorithm is a process which takes place in N- dimensional Euclidean space to a predetermined point in a lattice point of an n -dimensional grid number approximating the nearest grid point.

In 1993 he was awarded the Gödel Prize. In 1994 he gave a plenary lecture at the International Congress of Mathematicians (ICM ) in Zurich (Transparent proofs and limits to approximation) and 1992 he held a plenary lecture at the first European Congress of Mathematicians in Paris (Transparent proofs ). In 1990 he was invited speaker at the International Congress of Mathematicians in Kyoto (Computational complexity in finite groups)

Babai is the editor of the online journal Theory of Computing.

499997
de