The Norwegian Academy of Science and Letters has awarded the 2021 Abel Prize to László Lovász and Avi Wigderson “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”. László Lovász is an emeritus professor of Eötvös Loránd University (Budapest, Hungary). Currently he is leading the research group DYNASNET at the ELKH Rényi Institute, supported by a Synergy grant of the European Research Council.
The theory of ‘computational complexity’ – which concerns itself with the speed and efficiency of algorithms – was in its infancy in the 1970s, and is now an established field of both mathematics and theoretical computer science. Computational complexity has become important, providing the theoretical basis for internet security. Also in the 1970s a new generation of mathematicians realised that discrete mathematics had, in computer science, a new area of application. Today algorithms and internet security aspects are an integral part of everyday life for all of us. The work of László Lovász and Avi Wigderson has played an important part of this development.
“Lovász and Wigderson have been leading forces in this development over the last decades. Their work interlaces in many ways, and, in particular, they have both made fundamental contributions to understanding randomness in computation and in exploring the boundaries of efficient computation,” says Hans Munthe-Kaas, chair of the Abel committee.
He continues: “Thanks to the leadership of these two, discrete mathematics and the relatively young field of theoretical computer science are now established as central areas 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).
In the 1970s graph theory became one of the first areas of pure mathematics able to illuminate the new field of computational complexity. One of the major impacts of Lovasz’s work has been to establish ways in which discrete mathematics can address fundamental theoretical questions in computer science. He later said that he was very lucky to experience one of those periods when mathematics was developing completely together with an application area.
In addition to his work on the foundational underpinning of computer science, Lovász has also devised powerful algorithms with wide-ranging applications. One of these, the LLL algorithm, named after Lovász and the brothers Arjen and Hendrik Lenstra, represented a conceptual breakthrough in the understanding of lattices, and which has had remarkable applications in areas including number theory, cryptography and mobile computing. Currently, the only known encryption systems that can withstand an attack by a quantum computer are based on the LLL algorithm.
Lovász has won many awards including the 1999 Wolf Prize, the 1999 Knuth Prize, the 2001 Gödel Prize and the 2010 Kyoto Prize.
Wigderson is known for his ability to see links between apparently unrelated areas. He has deepened the connections between mathematics and computer science. He was born in Haifa, Israel, in 1956. His contribution to enlarging and deepening the field of ‘complexity theory’ – which concerns itself with the speed and efficiency of algorithms – is arguably greater than that of any single other person.
Wigderson has conducted research into every major open problem in complexity theory. In many ways, the field has grown around him. He has co-authored papers with more than 100 people. He has deepened the connections between mathematics and computer science.
The most important present-day application of complexity theory is internet cryptography. Early in his career Wigderson made fundamental contributions in this area, including the zero-knowledge proof, which today is being used in cryptocurrency technology.
In 1994, Wigderson won the Rolf Nevanlinna Prize for computer science. Among his many other prizes is the 2009 Gôdel Prize and the 2019 Knuth Prize.
About the Abel Prize
- The honoring of the Abel Prize laureates will be announced later.
- The Abel Prize is funded by the Norwegian Government and consists of MNOK 7.5.
- The prize is awarded by the Norwegian Academy of Science and Letters.
- The choice of the Abel laureates is based on the recommendation of the Abel Committee, which is composed of five internationally recognized mathematicians.
For more information, please visit www.abelprize.no
More information about the outstanding work of László Lovász
Mathematicians are usually characterized either as problem-solvers or theory-builders. László Lovász is both. He has solved several hard problems in combinatorics that had been open 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 for determining 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 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 on 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.
As the citation from the Norwegian Academy emphasized, Lovász had a leading role in elevating the field of discrete mathematics from an isolated, sometimes even disregarded area to one of the central branches of modern mathematics. When he started research in graph theory, this area was considered by many leading mathematicians as a collection of problems, some of which perhaps interesting and difficult, but which lack significance for the really important parts 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.
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. Lovász is not only an outstanding mathematician, but he did a great job at serving the scientific community as the president of the International Mathematical Union (2007-2010) and the president of the Hungarian Academy of Sciences (2014-2020).