László Babai

from Wikipedia, the free encyclopedia
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 from the Hungarian Academy of Sciences in Budapest under Pál Turán (and Vera T. Sós , with the work automorphism groups of graphs ). He is a professor of math and computer science at the University of Chicago .

Babai is one of the inventors of interactive evidence systems at the same time as Shafi Goldwasser , Silvio Micali and Charles Rackoff . From him comes the term Las Vegas algorithm for an algorithm using random numbers, which verifiably always delivers correct solutions (as well as with a finite expected value of the running time). He introduced this term in a 1979 paper on algorithms for testing the isomorphism of graphs. He also explored algorithmic issues in group theory.

Babai's nearest-plane algorithm is a method that finds a grid point of an n-dimensional number grid for a given point in n-dimensional Euclidean space , which approximates the closest grid point.

In 2015 he announced a major improvement on a previous estimate by himself and Eugene Luks (1983) by showing that the graph isomorphism problem can be solved in quasi-polynomial time. As Babai announced at the beginning of January 2017, Harald Helfgott found an error in the proof, which after Babai could be corrected. The graph isomorphism problem, the question of which complexity class algorithms for determining the isomorphism of graphs belong to, is one of the great unsolved problems in computer science.

In 1993 he received 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 in 1992 he gave 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 Kyōto ( Computational complexity in finite groups ). In 2015 he was elected to the American Academy of Arts and Sciences and was awarded the Knuth Prize .

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

See also

Web links

Individual evidence

  1. ^ Babai Trading group theory for randomness , Proc. 17th Annual Symposium Theory of Computing, ACM, 1985, and its publication with Shlomo Moran Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes , Journal of Computer and System Sciences, Volume 36, 1988, page 254– 276, doi: 10.1016 / 0022-0000 (88) 90028-1 .
  2. ↑ L. Babai: On Lovász 'lattice reduction and the nearest lattice point problem . In: Combinatorica . tape 6 , no. 1 , 1986, pp. 1–13 , doi : 10.1007 / BF02579403 ( PDF ). On Lovász 'lattice reduction and the nearest lattice point problem ( Memento of the original dated August 29, 2017 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  @1@ 2Template: Webachiv / IABot / www.csie.nuk.edu.tw
  3. ^ Babai, Graph Isomorphism in Quasipolynomial Time, 2015
  4. ^ Adrian Cho: Mathematician claims breakthrough in complexity theory, Science, November 20, 2015
  5. ↑ Babai homepage, January 9, 2017
personal data
SURNAME Babai, László
BRIEF DESCRIPTION Hungarian mathematician
DATE OF BIRTH July 20, 1950
PLACE OF BIRTH Budapest