The Abel Prize
The 2021 Abel Prize, arguably the closest equivalent in mathematics to the Nobel prize, has been awarded jointly to Avi Widgerson of the Institute for Advanced Study in Princeton, and László Lovász of the Eötvös Loránd University in Budapest, for their research linking discrete mathematics and computer science. The recipients will split the award, which is approximately USD$880,000.
According to Hanz Munthe-Kaas of the University of Bergen in Norway, who chaired the Abel Prize committee, Widgerson and Lovász “really opened up the landscape and shown the fruitful interactions between computer science and mathematics.” He added, “This prize is on the applied side, toward computer science. But it’s deep mathematics.”
Russell Impagliazzo of the University of California, San Diego, who has collaborated with both of the recipients, observes, “In many ways their work is complementary. Avi is on the computer science side and Lovász is on the mathematics side, but a lot of the issues they work on are related.”
Avi Widgerson (courtesy IAS, Princeton, NJ, USA)
Avi Widgerson
Avi Widgerson, a native of Haifa, Israel, began his career at a time when researchers in computer science began investigating complexity theory, namely fundamental assessments of how difficult certain computational problems are. One prominent problem in the field is the P = NP conjecture, namely the question of whether all problems that can be solved in a number of operations that scales at most as $n^c$, for some constant $c$, are also of the class of problems that can be quickly verified by a classical computer once a solution is given. Almost all computer scientists believe the answer is “no,” although no proof is yet known.
Widgerson and his collaborators have researched the computational complexity of the “perfect matching problem” — if one has a set of $N$ computers, each one of which is capable of performing some but not all of a set of $N$ problems, is it possible to assign tasks to these $N$ computers such that all tasks are covered, and each system performs just one task?
Widgerson and collaborators have also investigated how randomness conveys an advantage in many computational problems. In particular, they proved that under certain conditions it is always possible to convert a fast random algorithm into a fast deterministic algorithm. Their result established that the class of computational problems known as “BPP” is exactly equal to the complexity class P, under the assumption that any problem in a related class “E” has a property known as “subexponential circuitry.”
According to Kevin Hartnett, “It tied decades of work on randomized algorithms neatly into the main body of complexity theory and changed the way computer scientists looked at random algorithms.”
László Lovász (courtesy St. Andrews University, UK)
László Lovász
László Lovász, a native of Budapest, Hungary, was a precocious mathematician from an early age, earning not just one but three gold medals at the International Math Olympiad. Early on, Lovász met Paul Erdos, the famous Hungarian mathematician whose publication record of 1500 mathematical papers still remains unsurpassed. Erdos introduced Lovász to graph theory and discrete mathematics. Lovász recalls, that at the time, “graph theory was not mainstream mathematics because many of the problems or results arose from puzzles or sort of recreational mathematics.”
That changed with his co-discovery, with Arjen and Hendrik Lenstra, of what is now known as the Lenstra-Lenstra-Lovasz algorithm, or “LLL algorithm” for short. This algorithm addresses a problem about lattices, namely geometric objects whose sets of spatial points have coordinates with integer values, and which are closed under linear combinations — in other words, if $A$ and $B$ are in the lattice, then $mA + nB$ is also in the lattice, for every integer $m$ and $n$.
The LLL algorithm addresses a basic computational problem: What is the shortest vector in the lattice, or, in other words, which point in the lattice is closest to the origin. The problem is particularly difficult to solve in very high dimensions. The LLL algorithm finds a “good approximation” to this shortest point, together with a guarantee that there is no other point much closer to the origin.
Since its discovery, the LLL has been applied in numerous settings, ranging from integer factorization and analysis of public-key cryptosystems to the disproof of the Mertens conjecture. It is one of the most fundamental and widely applicable algorithms of modern computational mathematics.
As a single example, the LLL algorithm can be applied to the problem of integer relation detection, namely the problem of determining, given an $n$-long vector $X = \{x_1, x_2, \ldots, x_n\}$ of real numbers, typically computed to high numeric precision, whether there exist integers $\{a_i\}$ such that $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = 0$ (to within a comparable numerical precision). One algorithm for this purpose is the PSLQ algorithm (see also here). But the LLL algorithm can also be applied, often producing a faster solution.
One application is the following: If one suspects that a real number $\alpha$ is an algebraic number, namely the root of a polynomial of some degree $n$ with integer coefficients, what are the integer coefficients of the minimal polynomial? One approach is simply to calculate the vector $X = \{1, \alpha, \alpha^2, \ldots, \alpha^n\}$ to an appropriately high level of numeric precision, and then apply an integer relation algorithm such as PSLQ or LLL to $X$, in order to find the integer coefficients $\{a_i\}$, if any exist, such that $a_0 + a_1 \alpha + a_2 \alpha^2 + \cdots + a_n \alpha^n = 0$ (to a corresponding level of precision).
Lovász has published numerous other important results in graph theory. One of these is a proof of the Kneser conjecture, an assertion about whether a certain type of graph is colorable. He has also proposed some conjectures of his own, including the KLS conjecture, which has generated some significant research results just in the past few weeks.
For additional details and background, see this Quanta Magazine article (from which some of the above text was summarized), this New York Times report, and this New Scientist article.