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

Budapest Budapest is the Capital city, capital and List of cities and towns of Hungary, most populous city of Hungary. It is the List of cities in the European Union by population within city limits, tenth-largest city in the European Union by popul ...

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

University of Chicago The University of Chicago (UChicago, Chicago, or UChi) is a Private university, private research university in Chicago, Illinois, United States. Its main campus is in the Hyde Park, Chicago, Hyde Park neighborhood on Chicago's South Side, Chic ...

. 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 explores the relationships between these classifications. A computational problem ...

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

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

, and

finite groups In abstract algebra, a finite group is a group (mathematics), group whose underlying set is finite set, finite. Finite groups often arise when considering symmetry of Symmetry in mathematics, mathematical or Symmetry (physics), physical objects, ...

, 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. It is widely regarded as the most prestigious mathematical competition in the wor ...

. Babai studied mathematics at Faculty of Science of the Eötvös Loránd University from 1968 to 1973, received a PhD from the Hungarian Academy of Sciences 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 a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...

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 systems, the introduction of the term

Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives Correctness (computer science), correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas alg ...

,. 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 c ...

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

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 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, 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 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 Shafrira Goldwasser (; born 1959) is an Israeli-American computer scientist. A winner of the Turing Award in 2012, she is the RSA Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology; a professor o ...

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, a proof-of-stake blockchain cryptocurrency protocol. Micali's research at the MIT Compu ...

, Shlomo Moran, and Charles Rackoff, 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 (The Academy) 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 other ...

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

, and won the Knuth Prize. Babai was an invited speaker at the International Congresses of Mathematicians in

Kyoto Kyoto ( or ; Japanese language, Japanese: , ''Kyōto'' ), officially , is the capital city of Kyoto Prefecture in the Kansai region of Japan's largest and most populous island of Honshu. , the city had a population of 1.46 million, making it t ...

(1990),

Zürich Zurich (; ) is the list of cities in Switzerland, largest city in Switzerland and the capital of the canton of Zurich. It is in north-central Switzerland, at the northwestern tip of Lake Zurich. , the municipality had 448,664 inhabitants. The ...

(1994, plenary talk), and

Rio de Janeiro Rio de Janeiro, or simply Rio, is the capital of the Rio de Janeiro (state), state of Rio de Janeiro. It is the List of cities in Brazil by population, second-most-populous city in Brazil (after São Paulo) and the Largest cities in the America ...

(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
A Little More on the Graph Isomorphism Algorithm
// November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
copy
from Lenta.ru // texnomaniya.ru, 20 ноября 2015
Опубликован быстрый алгоритм для задачи изоморфизма графов
// Анатолий Ализар, Хабрахабр, 16 декабря в 02:12

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

References

External links

Personal website

{{DEFAULTSORT:Babai, Laszlo 1950 births 20th-century Hungarian mathematicians 21st-century Hungarian mathematicians Hungarian computer scientists Members of the Hungarian Academy of Sciences Academic staff of Eötvös Loránd University 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