Abel Prize: Avi Wigderson, László Lovász Win for Work That Bridged Math and Computer Science
Avi Wigderson and László Lovász will share the annual prize that aims to be something like the Nobel for mathematics.
Two mathematicians will share this year’s Abel Prize — regarded as the field’s equivalent of the Nobel — for advances in understanding the foundations of what can and cannot be solved with computers.
The work of the winners — László Lovász, 73, of Eötvös Loránd University in Budapest, and Avi Wigderson, 64, of the Institute for Advanced Study in Princeton, N.J. — involves proving theorems and developing methods in pure mathematics, but the research has found practical use in computer science, particularly in cryptography.
Dr. Lovász and Dr. Wigderson will split the award money of 7.5 million Norwegian kroner, or about $880,000.
The two mathematicians have “really opened up the landscape and shown the fruitful interactions between computer science and mathematics,” said Hans Z. Munthe-Kaas, a mathematician at the University of Bergen in Norway who was the chairman of the Abel Prize committee.
“This prize is on the applied side, toward computer science,” Dr. Munthe-Kaas said. “But it’s deep mathematics.”
Many of the early pioneers of computer science like Alan Turing and John von Neumann were mathematicians, and Dr. Lovász said he was “interested in this borderline between computer science and mathematics.”
Within his body of work, one of the most influential findings is what is known as the LLL algorithm (the three Ls standing for the surnames of the three mathematicians who created it: Dr. Lovász and two brothers: Arjen and Hendrik Lenstra).
The algorithm involves a basic geometric object: a lattice. An example of a simple lattice in two dimensions is the squares of a sheet of graph paper. That pattern can be generated by two line segments — one short vertical line, the side of one of the squares, and one horizontal line of the same length. Through combinations of these two line segments, one can get to any point on the lattice.
In higher dimensions, with more complicated lattices, finding the generators that are the equivalent of the two line segments for a two-dimensional square lattice is a difficult problem to solve. But the LLL algorithm shows how to find a simple but very good approximation.
With the algorithm made by Dr. Lovász and his colleagues, other researchers were able to expose the weaknesses of some cryptographic systems, showing how they could be simplified and then readily cracked.
The algorithm may also point the way toward new encryption techniques that will be needed if, as expected, technology enters an age of quantum computing.
Current encryption relies on the products of large prime numbers. (A prime number is a positive integer that is divisible only by 1 and itself. Thus, 3, 5 and 7 are prime numbers, but 9, which is divisible by 3, is not.) Computers now in use cannot factor large numbers quickly, ensuring that encryption is secure, but quantum-based computers could.
That would require a wholesale shift away from prime number-based encryption systems. The only available alternative is lattice-based schemes based on the LLL algorithm; no one has yet devised strategies, even using quantum computers, that would be able to crack them.
Russell Impagliazzo, a professor of computer science at the University of California, San Diego, said the LLL algorithm has also led to what is known as homomorphic encryption, which allows calculations to be performed on encrypted data without ever decrypting it.
Dr. Impagliazzo said homomorphic encryption could allow you to provide encrypted financial information to a credit bureau, and the credit bureau to, in turn, calculate your credit score without ever learning anything about you.
The algorithms, he said, were already “almost fast enough” to be practical.
One of Dr. Wigderson’s key advances involves what are known as zero-knowledge proofs. It is often important to show that you possess something — for cryptocurrency, that you actually have the money — without divulging any information about what you know.
“You should really think of two parties that don’t trust each other,” Dr. Wigderson said.
A fanciful example is that someone has a “Where’s Waldo?” puzzle where the small character Waldo (outside of North America, Waldo is usually known as Wally) is hidden within a complex drawing and this person has not found Waldo. You, on the other hand, have found Waldo and are willing to sell the solution. How could you convince the other person you actually have found Waldo without giving away the answer for free?
What you could do is ask the other person to turn around as you place a large piece of cardboard over the image with a small window cut that allows Waldo to be seen without revealing his exact location.
What Dr. Wigderson, working with other mathematicians, showed was that any mathematical proof could be cast as a zero-knowledge proof. “It’s amazing to me,” he said.
Dr. Lovász was born in Budapest in 1948. As a teenager, he won gold medals at the International Mathematical Olympiads in 1964, 1965 and 1966. Following the path of Paul Erdös, perhaps the most famous Hungarian mathematician of the 20th century, Dr. Lovász focused on the field of combinatorics, which studies patterns in selecting, arranging and counting objects. That area became important for many problems in computer science like the design of computer networks.
Dr. Wigderson was born in Haifa, Israel, in 1956. He received his mathematics doctorate from Princeton University in 1983. In 1986, he returned to Israel to become a faculty member at the Hebrew University in Jerusalem. He joined the Institute for Advanced Study in 1999.
Unlike with Nobel Prizes, where laureates are informed by phone just before the public announcements are made, Abel winners receive word days ahead of time. Some of their colleagues are told even earlier and the process of informing the Abel recipient becomes something like planning a surprise birthday party.
For Dr. Lovász, some of his colleagues arranged a Zoom videoconferencing call, telling him that the Hungarian Academy of Sciences wanted to post an article about his research on its website.
But then he saw many more people than he expected on the Zoom call. “Of course, I was overwhelmed,” Dr. Lovász said. “My first thought was, when can I tell it to my wife?”
Dr. Lovász was allowed to immediately share the news with her, who was in the next room.
For Dr. Wigderson, there was less subterfuge. Robbert Dijkgraaf, the director of the Institute for Advanced Study, told him on Monday morning to await a phone call from the Norwegian Academy, and he suspected he had received an Abel.
“I was not absolutely sure,” Dr. Wigderson said, “but at least I could guess.”
Category: Technology
Source: New York Times