László Babai
Encyclopedia
László Babai (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
, and finite groups, with an emphasis on the interactions between these fields. He is the author of over 180 academic papers.
His notable accomplishments include the introduction of interactive proof system
s, the introduction of the term Las Vegas algorithm
, and the introduction of group theoretic
methods in graph isomorphism
testing.
Babai studied mathematics at Eötvös Loránd University from 1968 to 1973, received a Ph.D. from the Hungarian Academy of Sciences
in 1975, and received a D.Sc. from the Hungarian Academy of Sciences in 1984. He held a teaching position at Eötvös Loránd University since 1971; in 1987 he took joint positions as a professor in algebra Eötvös Loránd and in computer science at the University of Chicago. In 1995 he began a joint appointment in the mathematics department at Chicago and gave up his position at Eötvös Loránd.
He is editor-in-chief of the refereed online journal Theory of Computing
. Babai was also involved in the creation of the Budapest Semesters in Mathematics
program and first coined the name.
awarded him an honorary doctorate.
In 1993, Babai was awarded the Gödel Prize
together with Shafi Goldwasser
, Silvio Micali
, Shlomo Moran
, and Charles Rackoff
, for their seminal papers on interactive proof systems.
In 2005, the University of Chicago gave him the Llewellyn John and Harriet Manchester Quantrell Award for Excellence in Undergraduate Teaching.
Budapest
Budapest is the capital of Hungary. As the largest city of Hungary, it is the country's principal political, cultural, commercial, industrial, and transportation centre. In 2011, Budapest had 1,733,685 inhabitants, down from its 1989 peak of 2,113,645 due to suburbanization. The Budapest Commuter...
) is a Hungarian
Hungary
Hungary , officially the Republic of Hungary , is a landlocked country in Central Europe. It is situated in the Carpathian Basin and is bordered by Slovakia to the north, Ukraine and Romania to the east, Serbia and Croatia to the south, Slovenia to the southwest and Austria to the west. The...
professor of mathematics and computer science at the University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
. His research focuses on computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, algorithms, combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, and finite groups, with an emphasis on the interactions between these fields. He is the author of over 180 academic papers.
His notable accomplishments include the introduction of interactive proof system
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 ascertain whether a given string belongs to a...
s, the introduction of the term Las Vegas algorithm
Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the verity of the result; it gambles only with the resources...
, and the introduction of group theoretic
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
methods in graph isomorphism
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
testing.
Babai studied mathematics at Eötvös Loránd University from 1968 to 1973, received a Ph.D. from the Hungarian Academy of Sciences
Hungarian Academy of Sciences
The Hungarian Academy of Sciences is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest.-History:...
in 1975, and received a D.Sc. from the Hungarian Academy of Sciences in 1984. He held a teaching position at Eötvös Loránd University since 1971; in 1987 he took joint positions as a professor in algebra Eötvös Loránd and in computer science at the University of Chicago. In 1995 he began a joint appointment in the mathematics department at Chicago and gave up his position at Eötvös Loránd.
He is editor-in-chief of the refereed online journal Theory of Computing
Theory of Computing (journal)
Theory of Computing is an online open access journal dedicated to theoretical computer science. The journal was founded in 2005 amidst growing concerns about the financial difficulties of university libraries around the world faced with rising costs in subscriptions to scientific journals owned by...
. Babai was also involved in the creation of the Budapest Semesters in Mathematics
Budapest Semesters in Mathematics
The Budapest Semesters in Mathematics program is a study abroad opportunity for North American undergraduate students in Budapest, Hungary. The coursework is primarily mathematical and conducted in English by Hungarian professors, drawn primarily from Eötvös Loránd University and the Mathematics...
program and first coined the name.
Honors
In 1988, Babai won the Hungarian State Prize, in 1990 he was elected as a corresponding member of the Hungarian Academy of Sciences, and in 1994 he became a full member. In 1999 the Budapest University of Technology and EconomicsBudapest University of Technology and Economics
The Budapest University of Technology and Economics , in hungarian abbreviated as BME, English official abbreviation BUTE, is the most significant University of Technology in Hungary and is also one of the oldest Institutes of Technology in the world, having been founded in 1782.-History:BME is...
awarded him an honorary doctorate.
In 1993, Babai was awarded the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
together with Shafi Goldwasser
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
, Silvio Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
, Shlomo Moran
Shlomo Moran
Shlomo Moran is an Israeli computer scientist, the Bernard Elkin Chair in Computer Science at the Technion – Israel Institute of Technology in Haifa, Israel.Moran received his Ph.D...
, and Charles Rackoff
Charles Rackoff
Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, Rackoff attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar at INRIA in France.He currently works at the...
, for their seminal papers on interactive proof systems.
In 2005, the University of Chicago gave him the Llewellyn John and Harriet Manchester Quantrell Award for Excellence in Undergraduate Teaching.