Mathematicians who unravelled computational complexity win Abel prize

One of the biggest prizes in maths has been awarded to two people for their “foundational contributions to theoretical computer science and discrete mathematics”. László Lovász at the Alfréd Rényi Institute of Mathematics in Budapest, Hungary, and Avi Wigderson at the Institute for Advanced Study in Princeton, New Jersey share this year’s Abel prize, which is sometimes called the Nobel prize of mathematics.

The pair helped kick-start the field of computational complexity – the study of the speed and efficiency of algorithms.

Algorithms are lists of instructions, essentially a recipe to follow to complete a task. This could include solving an equation, sorting a list of words into alphabetical order or determining the fastest route between two places. Some algorithms are better than others, meaning they consistently require fewer steps to complete a task, but working out which is which isn’t always easy. Hence the need for a whole field of research to make sense of it, which sits at the overlap between mathematics and computer science.

Wigderson, who has a reputation for seeing links between seemingly unrelated disciplines, has worked on every major open problem in the field of computational complexity. “There are no more important problems anywhere in science,” he says. “Any process is an algorithm – neurons in the brain or planets in the solar system or crises in the financial markets, all of these have some fixed rules. What can be applied to computers can be applied to basically everything.”

He says he was happy and surprised to hear he had won the Abel prize, adding he felt “very honoured for myself and for the field”.

Lovász has also worked across disciplines, applying the techniques of a branch of mathematics called graph theory to the study of computational complexity. One of his most famous contributions is being one of the “L”s in the LLL algorithm. This algorithm, developed by Lovász and brothers Arjen and Hendrik Lenstra (at the Swiss Federal Institute of Technology in Lausanne and Leiden University, respectively), forms the basis of a method for encrypting data that can withstand attacks from quantum computers.

The pair will share the prize money of NOK 7.5 million (£640,000).