László "Laci" Babai (born July 20, 1950, in

Budapest Budapest (, ; ) is the capital and most populous city of Hungary. It is the ninth-largest city in the European Union by population within city limits and the second-largest city on the Danube river; the city has an estimated population ...

)Curriculum vitae
from Babai's web site, retrieved 2016-01-28. is a Hungarian professor of computer science and mathematics at the

University of Chicago The University of Chicago (UChicago, Chicago, U of C, or UChi) is a private research university in Chicago, Illinois. Its main campus is located in Chicago's Hyde Park neighborhood. The University of Chicago is consistently ranked among the b ...

. His research focuses on

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

, and

finite groups Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...

, with an emphasis on the interactions between these fields.

Life

In 1968, Babai won a gold medal at the

International Mathematical Olympiad The International Mathematical Olympiad (IMO) is a mathematical olympiad for pre-university students, and is the oldest of the International Science Olympiads. The first IMO was held in Romania in 1959. It has since been held annually, except i ...

. Babai studied mathematics at

Faculty of Science Faculty may refer to: * Faculty (academic staff), the academic staff of a university (North American usage) * Faculty (division), a division within a university (usage outside of the United States) * Faculty (instrument), an instrument or warrant ...

of the

Eötvös Loránd University Eötvös Loránd University ( hu, Eötvös Loránd Tudományegyetem, ELTE) is a Hungarian public research university based in Budapest. Founded in 1635, ELTE is one of the largest and most prestigious public higher education institutions in Hung ...

from 1968 to 1973, received a PhD from the

Hungarian Academy of Sciences The Hungarian Academy of Sciences ( hu, Magyar Tudományos Akadémia, MTA) is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest, between Széchenyi rakpart and Akadémia utca. Its ma ...

in 1975, and received a DSc 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 Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...

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

Work

He is the author of over 180 academic papers. His notable accomplishments include the introduction of

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: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order t ...

s, the introduction of the term

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. However, the runtime of a Las Vegas algorithm differs depending on the ...

,. and the introduction of group theoretic methods in

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(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...

testing. In November 2015, he announced a quasipolynomial time algorithm for the

graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational compl ...

. He is editor-in-chief of the refereed online journal ''

Theory of Computing ''Theory of Computing'' is a peer-reviewed open access scientific journal covering theoretical computer science. The journal was established in 2005 and is published by the Department of Computer Science of the University of Chicago. The edit ...

''. Babai was also involved in the creation of the Budapest Semesters in Mathematics program and first coined the name.

Graph isomorphism in quasipolynomial time

After announcing the result in 2015, Babai presented a paper proving that the

can be solved in

quasi-polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

in 2016, at the ACM

Symposium on Theory of Computing The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for ...

. In response to an error discovered by

Harald Helfgott Harald Andrés Helfgott (born 25 November 1977) is a Peruvian mathematician working in number theory. Helfgott is a researcher ('' directeur de recherche'') at the CNRS at the Institut Mathématique de Jussieu, Paris. Early life and education ...

, he posted an update in 2017.

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 Economics The Budapest University of Technology and Economics ( hu, Budapesti Műszaki és Gazdaságtudományi Egyetem or in short ), official abbreviation BME, is the most significant university of technology in Hungary and is considered the world's oldes ...

awarded him an honorary doctorate. In 1993, Babai was awarded the

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

together with

Shafi Goldwasser en, Shafrira Goldwasser , name = Shafi Goldwasser , image = Shafi Goldwasser.JPG , caption = Shafi Goldwasser in 2010 , birth_place = New York City, New York, U.S. , birth_date = , death_date ...

Silvio Micali Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security. In 2012, he received ...

, Shlomo Moran, and

Charles Rackoff Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, he 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 ...

, for their papers on interactive proof systems. In 2015, he was elected

American Academy of Arts and Sciences The American Academy of Arts and Sciences (abbreviation: AAA&S) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and ...

2015 Fellows and Their Affiliations
/ref> a fellow of the

, and won the

Knuth Prize The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth. History The Knuth Prize has been awarded since 1996 and includes an award of US ...

. Babai was an invited speaker at the International Congresses of Mathematicians in

Kyoto Kyoto (; Japanese: , ''Kyōto'' ), officially , is the capital city of Kyoto Prefecture in Japan. Located in the Kansai region on the island of Honshu, Kyoto forms a part of the Keihanshin metropolitan area along with Osaka and Kobe. , the ci ...

(1990),

Zürich Zürich () is the list of cities in Switzerland, largest city in Switzerland and the capital of the canton of Zürich. It is located in north-central Switzerland, at the northwestern tip of Lake Zürich. As of January 2020, the municipality has 43 ...

(1994, plenary talk), and

Rio de Janeiro Rio de Janeiro ( , , ; literally 'River of January'), or simply Rio, is the capital of the state of the same name, Brazil's third-most populous state, and the second-most populous city in Brazil, after São Paulo. Listed by the GaWC as a b ...

(2018).

Sources

Professor László Babai's algorithm is next big step in conquering isomorphism in graphs
// Published on Nov 20, 2015 Division of the Physical Sciences / The University of Chicago
Mathematician claims breakthrough in complexity theory
by Adrian Cho 10 November 2015 17:45 // Posted i
Math
Science AAAS News
A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details
+ Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015, by j2kun
Landmark Algorithm Breaks 30-Year Impasse
Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
A Little More on the Graph Isomorphism Algorithm
// November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
[Ласло
/nowiki>_Бабай_приблизился_к_решению_«проблемы_тысячелетия».html" ;"title="�асло">[Ласло
/nowiki> Бабай приблизился к решению «проблемы тысячелетия»">�асло">[Ласло
/nowiki> Бабай приблизился к решению «проблемы тысячелетия»// Наука Lenta.ru, 14:48, 20 ноября 2015
copy
from Lenta.ru // texnomaniya.ru, 20 ноября 2015
Опубликован быстрый алгоритм для задачи изоморфизма графов
// Анатолий Ализар, Хабрахабр, 16 декабря в 02:12

// Джерело: Хабрахабр, перекладено 16 грудня 2015, 06:30

References

External links

*
Personal website

*[http://dblp.uni-trier.de/db/indices/a-tree/b/Babai:L=aacute=szl=oacute=.html DBLP: László Babai]. {{DEFAULTSORT:Babai, Laszlo 1950 births 20th-century Hungarian mathematicians 21st-century Hungarian mathematicians Hungarian computer scientists Members of the Hungarian Academy of Sciences Eötvös Loránd University faculty Combinatorialists Theoretical computer scientists University of Chicago faculty Gödel Prize laureates Knuth Prize laureates Hungarian emigrants to the United States Living people International Mathematical Olympiad participants Fellows of the American Academy of Arts and Sciences Eötvös Loránd University alumni