“I have a prize problem,” says Prof. Avi Wigderson, a theoretical computer science researcher at the Institute for Advanced Study (IAS) in Princeton, at the very beginning of our conversation. “People focus on these awards more than my work and that of many others who have done wonderful work as well, and don’t receive them,” he explains in response to my surprised face. Nevertheless, this is the only person in the world who won both the Abel Prize, which is defined as the “Nobel of Mathematics”, and the Turing Prize, its equivalent in the field of computer science, earlier this year. “Of course I’m happy to receive the recognition, but it’s not what drives me, but the desire to understand things that I don’t understand. I’m interested in intellectual problems, so if I solve them or if others solve them before me, and I learn the solution from them – that’s more than enough.”
It is difficult to exaggerate the importance of Wigderson’s work. Yannis Ioannidis, president of ACM, the association that awards the Turing Award, described him as a “towering intellectual force in theoretical computer science.” Jeff Dean, Senior Vice President at Google, which sponsors the $1 million financial grant accompanying the award, said. “Wigderson’s work… has set the agenda in theoretical computer science for the past three decades.” Both of them also emphasized in their reasoning that he was a mentor and research partner of more than 100 people – a matter that is not taken for granted in a field that is perceived as very isolated, a domain of eccentric geniuses.
Wigderson entered the field at the crucial moment of the rise of the personal computer in the seventies, and played a significant role in the theoretical developments that enabled the growth of today’s Internet. In a series of articles he published with other researchers from the 1980s onwards, he reshaped the understanding of the role of randomness in computation, when he proved that for every fast algorithm that can solve a difficult problem by flipping a coin, there is an almost as fast algorithm that does not use coin flipping, provided that certain conditions are met. In other words, he showed that randomness can actually be dispensed with in any efficient algorithm.
Wigderson’s groundbreaking research was critical to the development of cryptography, which is used to secure information on the Internet, such as credit card numbers and passwords. Without cryptography we would not be able to shop online, receive banking services, open an email box and perform a long list of actions based on private information that must remain confidential.
At the base of computer science in general, and cryptography in particular, stands one of the “Seven Millennium Problems” defined by the Clay Mathematics Institute in 2000: Is P, which represents a set of problems that can be solved in a reasonable time, equal or not equal to NP, which represents a set of problems that are easy to check if the solution for them is right. Wigderson likes to give the example of losing keys — you know you’ve lost them, and it’s hard for you to find them, but it’s easy to verify someone found them.
“These are problems for which if we find a solution, at least we will know that we have done so,” says Wigderson. “There are many problems that we get stuck on, for example proving a mathematical theorem or planning a schedule without conflicts, and if someone shows us the solution, it’s easy for us to be convinced that it works. This is what the question of P versus NP deals with – when it is always easy to verify a solution is there also an easy way to find it. If this were true, then it would be easy for a computer program to solve Sudoku problems, optimization problems, etc. That’s why we don’t believe it. We know from experience that searching is more difficult than making sure we found a solution.”
In other words, the issue of P versus NP actually asks: do hard problems really exist, or will what seem to us now to be hard problems later turn out to be easy problems? “With a lot of problems, you can simply try all the options for a solution: do you want a cure for cancer? We will try all the chemicals, mix them in all possible forms. But this is not practical because the number of options is huge, which means that testing them will require an exponential running time.”
And this is where Internet security systems come into play. “Difficult problems are also a blessing, and the world uses them all the time,” explains Wigderson. “The existing encryptions used for electronic commerce are based on the assumption that a certain problem in NP, the problem of factoring numbers, is a hard problem.” That is, whoever writes security code assumes that deciphering it is a task that will take millions of years for computers to crack. “Therefore, the problem I would most like to solve, or have someone solve for me, is to show that there are difficult problems, even a little difficult,” he says. “Otherwise the entire foundation of the Internet will collapse.”
That is, the way to the scam of the century goes through proving that a problem, like factoring into prime numbers, is actually easy.
“That’s right. Security systems currently rely on factorization or the discrete logarithm. Today, people are switching to cryptographic systems that rely on the difficulty of other problems because of the fear of quantum computers, which know how to solve factorization problems – as soon as they exist. But regarding this problem of P versus NP in general, we are in a similar place to where we were 50 years ago – we have no ways to prove the difficulty of problems. Therefore, computational difficulty must be assumed, until someone proves that P is different from NP or discovers a way to prove difficulty at all.”
You’re not sure that P is different from NP?
“Like most of my colleagues in the field, I believe they are different, but this thinking relies mainly on the fact that we have failed to find efficient algorithms for all these problems.”
You can also look at it as a kind of expression of trust in human creativity, which cannot be mechanized, or as a psychological bias – we are unable to recognize that it can be mechanized.
“It’s true, and the psychological issue has often caused humanity to get stuck in some corner for hundreds of years, because of all kinds of beliefs about our abilities or our meaning. And yet, they found solutions to many problems that at first seemed very difficult, and people built sophisticated algorithms.”
“AI is a machine, like humans”
Wigderson (67) was born in Haifa to an electrical engineer father and a nurse mother, both Holocaust survivors who met in Israel. He got his passion for mathematics from his father. “He loved riddles for all of us, and I was more interested in them than my brothers,” says Wigderson. In 1977, he enrolled in computer science studies at the Technion – not mathematics, because his parents thought it would be better for him to also have a profession. In 1983 he had already completed his doctorate at Princeton, and three years later he returned to Israel to serve as a lecturer at the Hebrew University in Jerusalem. Since 1999 he has been a professor at the School of Mathematics of the Institute for Advanced Study in Princeton. He is married to Edna, whom he met at the Technion, and they have three children.
“I consider myself very lucky to have fallen into this field,” says Wigderson. “The combination between mathematics and computing is magical. It is such a rich field, which is expressed not only in computer calculations, but also in nature, in the brain and everywhere, and therefore creates a lot of different questions about what can and cannot be done with certain resources. It is extraordinarily rich, and I am surrounded by a community that surprises me and teaches me great things on a regular basis.”
Describe to me what a eureka moment in research looks like.
“It’s really exciting. It’s very hard to explain in words how you didn’t know something, and a minute later it was in your head.”
How do you even do research on theoretical issues jointly?
“It is quite magical. Two (or more) people can tell each other what they are trying to do, and sometimes, this helps the others see more or differently what they had in mind (even if none of this solves what they wanted to – experience and understanding grow anyway). To me, the fun of thinking together sometimes exceeds the fun of solving a problem. This is lucky, as the first happens much more often.”
One of the key concepts in the field of cryptography, to which Wigderson contributed, is “zero-knowledge proof”: a situation in which a person wants to convince another person of a certain claim without giving him any information beyond the claim. Imagine, for example, a mathematician who wants to convince a colleague that he has proved a mathematical theorem, without revealing how. Wigderson, together with Oded Goldreich and Silvio Micali, found that for every claim that has a proof, there is also a proof in zero knowledge. This idea forms the basis for network safety in general, and blockchain technology in particular.
“Cryptography is full of situations where you interact with others who don’t trust you, and rightly so,” he says with a smile. “To be a good cryptographer, you have to be a bit paranoid. So you have to perform some action that, among other things, depends on your secrets. For example, make people believe that you have chosen an encryption key that is difficult to break into prime numbers. The suitability of a communication protocol for buying on the network, for example, its secrecy and safety depend on the fact you did it. In short, you have to convince me of something you know, and do it in such a way that I won’t learn anything – really nothing – except for the fact that what you say is true. It was amazing and satisfying to find out that everything that has proof, also has proof in zero knowledge.”
As someone who dedicates his life to proving that there are problems that cannot be solved, are you bothered by the advances in artificial intelligence? Can Artificial Super Intelligence find the answer to NP problems?
“I am sure that the new AI tools will help us in many things. They may help us discover the proof that problems are hard, or on the other hand, they may help us find an efficient algorithm for problems in NP and prove that P is equal to NP. Artificial Intelligence is another powerful tool that humanity has invented, which can help us in many things, including solving scientific and mathematical problems. But the speed of these systems alone will not help to turn an exponential algorithm – that is, one that tries all possibilities – into an efficient algorithm, even if the chip reaches the size of an electron and the communication between the values of this supercomputer will be the speed of light and you will use all the material in the universe. AI tools, like us, are just calculation systems.”
Explain to me this statement, “AI tools, like us, are just calculation systems”. Are humans machines?
“I see no reason to think that we are not machines. No one has ever given us a reason to think that we are superior to anything else—animals, machines, or whatever. We use the laws of nature every time we do anything: when we get into the car after listening to weather forecasts and when we choose not to leave the office on the tenth floor through the window. Medicine also recognizes the fact that we are made of atoms and cells, and all these systems work according to chemistry and physics, only a part of which we understand. So why should we think that there is something more in the brain or the heart of ours that doesn’t behave according to the same laws of nature?”
Maybe because we have the ability to talk about it.
“Our ability to talk about these issues is really very interesting. But the fact that GPT is able to have such a conversation can perhaps help us to be more accepting of the fact that machines can do many more things that people thought they could not do. I am personally amazed by the capabilities of ChatGPT. Indeed it disappoints sometimes, but the very fact that it can hold an intelligent conversation on any topic, with knowledge that none of us have, and in a pleasant way – is amazing.”
One can argue about the “pleasant” part. Last year, for example, a man committed suicide in Belgium after a correspondence with the bot Chai, during which he was convinced to sacrifice his life so that the system would save humanity from the climate crisis.
“And don’t humans create such an effect? Don’t people react to all kinds of things in a way that changes others’ opinions or affects their feelings to the point of actual harm? Think, for example, of children boycotting other children, or of social pressure. So I don’t understand what the debate is about. As everyone knows, the source of the information that GPT and other systems draw is humans, and they can introduce racism, pornography, and more. We created these dangers, and you can find them even without GPT.”
“Israel is a great knowledge powerhouse”
Wigderson is the sixth Israeli Turing Prize laureate, and only the United States and the United Kingdom have more winners. In terms of the ratio between the number of winners and the size of the population, Israel is at the top. “My country has been blessed,” Wigderson says with a smile, “we are a great power in this field.”
Naftali Bennett put up a post about your winning the Turing and wrote in it, “We must find a way to ensure that great Israeli scientists stay in Israel”. What do you think about it? Is there anything that can be done to prevent the brain drain?
“Science is currently in trouble all over the world, not only in Israel. It had a period of glory, but in many countries, especially in democracies, budgets are being cut more and more. The situation in Israel is a catastrophe. The governments completely disregard education and education and allow huge sectors of the population to not learn even basic core studies. This is terrible in my eyes. We are heading for a catastrophe in Israel from a scientific point of view as well, but not only.
Countries should want to have good science taking place in them because it obviously adds to the country’s intellectual and perhaps also material wealth – so it is clear that they should invest in it, and it is clear that creating an atmosphere that makes people run away is not helpful.”
What are your feelings regarding the pro-Palestinian demonstrations on campuses in the United States?
“I’m not worried, and I don’t think that these demonstrations will do to us what the Nazis did to us in Europe. Not at all. In fact, I sympathize with many of these demonstrations, at least those that concern the situation of the Palestinians in Gaza. Of course, I wouldn’t want to see violence against Israelis or Jews, but I don’t want there to be violence anywhere. In any case, we don’t experience it at all here. It’s a peaceful town and we’re in a super-peaceful corner of it, so it didn’t reach us in any direct way.”
This is not antisemitism in your eyes?
“I’m not saying it’s not anti-Semitism, but it’s clear where it comes from. It comes from the actions of the current government, and I’m pessimistic about the running of the state under it.”
Daisy Hips is a science communicator who brings the wonders of the natural world to readers. Her articles explore breakthroughs in various scientific disciplines, from space exploration to environmental conservation. Daisy is also an advocate for science education and enjoys stargazing in her spare time.
