László Lovász (left) and Avi Wigderson were jointly awarded the 2021 Abel Prize.Credits: left, Hungarian Academy of Sciences/Laszlo Mudra/AbelPrize; right, Cliff Moore/Institute for Advanced Study, Princeton/AbelPrize
Abel prize celebrates union of maths and computer science
Table of Contents
Two pioneers of the theory of computation have won the 2021 Abel Prize, one of the most prestigious honours in mathematics.
Hungarian mathematician László Lovász and Israeli computer scientist Avi Wigderson will share the prize, worth 7.5 million Norwegian kroner (US$886,000), “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”, the Norwegian Academy of Science and Letters in Oslo announced on 17 March.
Algorithms — which include simple procedures children learn at school, such as long division — have been central to mathematics since at least the time of ancient Greece. But since the advent of computers in the twentieth century, the emphasis in research has changed from ‘can an algorithm solve this problem?’ to ‘can an algorithm, at least in principle, solve this problem on an actual computer and in a reasonable time?’.
Lovász (pictured left), now at Eötvös Loránd University in Budapest, and Wigderson (pictured right), who is at the Institute for Advanced Study in Princeton, New Jersey, both played a central part in these developments, making important contributions to the theory of complexity of algorithms.
Lovász solved major problems in the mathematical theory of networks, and helped to devise an algorithm known as LLL, which breaks down a large vector made of integer numbers into a sum of the shortest possible vectors of this type. The algorithm has applications in various areas of pure mathematics, and has become crucial to the study of data encryption.
One of Wigderson’s most renowned achievements is in clarifying the role of randomness in computation. In the 1990s, he showed that if an algorithm using randomness seems to run efficiently, then another, non-random algorithm must exist that is almost as efficient. This gave a theoretical reassurance that random algorithms really do find the correct solutions.
A photograph of the artwork (left), and an illustration showing the kangaroo superimposed on it (right).Credit: D. Finch et al./Nature Hum. Behav.
Cave kangaroo
A 17,000-year-old depiction of a kangaroo is Australia’s oldest-known rock painting. The 2-metre-high drawing in red ochre was found on the ceiling of a rock shelter in the Kimberley region, which is known for Indigenous rock art.
Geoscientist Damien Finch at the University of Melbourne, Australia, and his colleagues calculated the radiocarbon dates of ancient mud-wasp nests surrounding the painting, which showed that the kangaroo was between 17,100 and 17,500 years old (D. Finch et al. Nature Hum. Behav. 5, 310–318; 2021).