Skip to main content

Lovász and Wigderson to share the Abel Prize

News

The Norwegian Academy of Science and Letters has decided to award the Abel Prize for 2021 to László Lovász of Eötvös Loránd University in Budapest, Hungary, and Avi Wigderson of the Institute for Advanced Study, Princeton, USA, “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading roles in shaping them into central fields of modern mathematics”.

A brilliant mathematician since he was a teenager, László Lovász more than delivered on his early promise. His work has established connections between discrete mathematics and computer science. Born in 1948 in Budapest, Hungary, he has also served his community as a writer of books noted for their clarity and accessibility, as an inspirational lecturer, and as a leader, spending a term as president of the International Mathematical Union (2007-2010).

Lovász László
László Lovász, Photo credit: László Mudra/MTA

He has solved several tough problems in combinatorics that had been unresolved for a long time: the perfect graph conjecture in 1972, the chromatic number of Kneser graphs in 1978, the Shannon capacity of graphs in 1979 – just to name a few. His ingenious solutions were often based on ideas inspired by seemingly unrelated mathematical areas. For example, in the case of the Kneser graphs, he used topological methods, thereby laying the foundations of topological combinatorics, a novel area of research.

Similarly, the ideas he used to determine the Shannon capacity of graphs led to the theory of semidefinite programming. Furthermore, the Lovász local lemma, which relaxes the independence condition in the application of probabilistic methods in combinatorics, has been used extensively since its invention in 1973.

Lovász was an early champion of the mathematical theory of algorithms. He published a book on this subject with Péter Gács in 1978 in Hungarian. Together with the Lenstra brothers Arjen and Hendrik, he invented the LLL lattice base reduction algorithm, which has been used for a great variety of purposes: for factoring polynomials, for disproving the Mertens conjecture, and more recently in cryptography.

To demonstrate his theory-building accomplishments, it is enough to present the long list of books written by him: Combinatorial Problems and Exercises (1979), Matching Theory (with M. Plummer, 1986), An Algorithmic Theory of Numbers, Graphs, and Convexity (1986), Geometric Algorithms and Combinatorial Optimization (with M. Grötschel and A. Schrijver, 1988), Greedoids (with B. Korte and R. Schrader, 1991), Discrete Mathematics: Elementary and Beyond (with J. Pelikán and K. Vesztergombi, 2003), Large Networks and Graph Limits (2012), Graphs and Geometry (2019).

The theory of graph limits, which he developed in collaboration with C. Borgs, J. Chayes, B. Szegedy, V.T. Sós, and K. Vesztergombi, also serves as the mathematical foundation for his current research into the dynamics of networks. The investigations of his research group have relevance for mathematical modelling of disease propagation that can be used in controlling the recent pandemic.

For most of his career, László Lovász was a professor at Eötvös University in Budapest, but he has spent considerable time at other institutions: at the University of Szeged, at Yale University and at Microsoft Research. Currently, he is leading the DYNASNET research group at the ELKH Rényi Institute, supported by a Synergy grant from the European Research Council.

As the citation from the Norwegian Academy emphasized, Lovász has played a leading role in elevating the field of discrete mathematics from an isolated, sometimes and even disregarded area to one of the central branches of modern mathematics. When he started his research into graph theory, the area was considered by many leading mathematicians to be a collection of problems, some of which were perhaps interesting and difficult, but which lacked significance with regard to the really important areas of mathematics. Now, as the laudation of this year’s Abel Prize winners aptly formulated, discrete mathematics has taken its deserved place as one of the fundamental branches of mathematics.