Abel Prize celebrates union of mathematics and computer science

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 announced on 17 March.

Wigderson, who is at the Institute for Advanced Study (IAS) in Princeton, New Jersey, told Nature that the prize validates the theory of computation, not just his own work. “I think it’s extremely significant for the field,” he says.

“Today it’s more and more difficult — and I think it’s a good development — to distinguish pure mathematics and applied mathematics,” says Lovász, who is at Eötvös Loránd University in Budapest.

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 and Wigderson played a central part in these developments, says Peter Sarnak, a number theorist at the IAS. “The theory of complexity of algorithms and the study of the speed of solving problems was developed in the ’60s and ’70s, and both of these fellows proved to be absolute leaders.”

From maths to computation

Lovász was born in 1948 in Budapest, and grew up in an environment that encouraged talented children to compete at solving hard problems. Much of his early inspiration came from Paul Erdős, the most prolific mathematician of the modern era. Erdős’s work focused on the mathematics of discrete objects and their relationships — such as the nodes in a network — rather than on the continuous variables that are typical in areas such as geometry, says mathematician Péter Pál Pálfy at the Alfréd Rényi Institute of Mathematics in Budapest.

Lovász started his career at a time when topics in discrete mathematics such as the theory of networks — once looked down upon by ‘pure’ mathematicians — were becoming crucially important both to other areas of maths and to applications such as the analysis of ‘big data’. He was interested in basic research as well as in its applications, and worked as a full-time researcher at Microsoft for seven years in between academic positions. He solved major problems in the mathematical theory of networks, such as calculating the number of possible ways there are to colour nodes while ensuring that any two neighbouring nodes are always different colours¹.

One of Lovász’s most celebrated results is an algorithm he devised together with two Dutch number theorists, the brothers Arjen and Hendrik Lenstra². The algorithm, known as LLL, breaks down a large vector made of integer numbers into a sum of the shortest possible vectors of this type. It has applications in various areas of pure mathematics, and has become crucial to the study of data encryption. Cryptography keys based on integer vectors are seen as a promising for future Internet security, because, unlike the keys commonly used in today’s communications, it is thought they will not be vulnerable to being cracked by future quantum computers.

Lovász was president of the International Mathematical Union from 2007 to 2010. He also headed the Hungarian Academy of Sciences from 2014 to 2020, and during those years led a daring but ultimately unsuccessful effort to stop the Hungarian government taking over the academy’s research institutes. He and many others argued that the move would reduce researchers’ independence.

From computation to maths

Wigderson was born in Haifa, Israel, in 1956. He studied in Israel and the United States and held various academic positions before moving to the IAS in 1999, where he has been ever since. His Abel Prize citation recognizes his contributions to practically all areas of computer science, in which he attacked any problem with whatever mathematical tools he could find, even from distant fields of study. Wigderson’s enthusiasm for his field of research is “infectious”, Sarnak says. “When he talks to you, you almost feel like ‘Jesus, I better put down what I’m doing and start working on this’.”

One of Wigderson’s most renowned achievements is in clarifying the role of randomness in computation. In many situations, such as looking for the way out of a maze, figurative coin-flipping allows algorithms to find a solution quickly, but for reasons that are not immediately obvious. “A lot of programs practically run much faster if you allow them to do this random choice,” Sarnak says.

Working with collaborators in the 1990s, Wigderson 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.

Another major piece of Wigderson’s work is becoming increasingly relevant in the information economy. It involves ‘zero-knowledge proofs’, a way of allowing somebody to verify the correctness of a statement without revealing any information about what the statement says.

Zero-knowledge proofs are crucial to certifying digital currencies such as Bitcoin, and can also help to verify a person’s identity. By answering a verifier’s questions, someone could give a zero-knowledge proof of having a correct password, for example, without revealing the password itself. Wigderson and his collaborators showed in 1991⁴ that essentially all mathematical statements can be translated in a way that allows a zero-knowledge proof — “probably the most surprising, the most paradoxical” of his results, Wigderson says.

Since the Abel Prize was inaugurated in 2003, Lovász is the third Hungarian-born winner, and Wigderson is the second Israeli. With the exception of Karen Keskulla Uhlenbeck in 2019, all winners so far have been men.