A Life of Complexity

Back in the mid-1970s, Avi Wigderson had completed his service in the Israeli army and was preparing to head to Technion–Israel Institute of Technology, where he thought he would study mathematics. His parents, though, argued that computer science, then a young field, might be more practical. They were not an academic family, Wigderson said—his father was an engineer and his mother was a nurse—and the concept of a career in research was foreign to him. “They said, maybe you will have an easier time finding a job after you graduate,” he recalled. “And anyway, there’ll be lots of math there.”

Following their advice put Wigderson on a path that led to his being named to receive the 2023 ACM A.M. Turing Award for fundamental contributions to the theory of computation, in particular by expanding our understanding of the role that randomness plays. Wigderson, now the Herbert H. Maass Professor at the School of Mathematics of the Institute for Advanced Study (IAS) in Princeton, NJ, has made a career of studying computational complexity theory. He also advanced our understanding of interactive zero-knowledge proofs, which allow someone to show they know some information while keeping that information secret.

Scientists had believed that making random choices carried an advantage when figuring out certain complex problems; for example, a deterministic algorithm that looked for a large prime number, divisible only by itself and 1, by testing every possibility would take a very long time. On the other hand, randomly picking a large integer and testing it for primality could provide an answer much more quickly, as long as the searcher was willing to accept a small amount of uncertainty about the answer.

Wigderson, however, showed that under natural, widely believed assumptions, any such fast probabilistic algorithm could be replaced with a fast deterministic algorithm. “Of course, the deterministic algorithm will be slower than the probabilistic one, but only moderately slower,” he said.

He also helped develop, along with other researchers, so-called randomness extractors. Many sources, from weather to the stock market to quantum phenomena, generate outputs that seem random but may have some underlying correlations and biases. An extractor is a deterministic algorithm that takes a sample from such a source, then “purifies it” into something almost perfectly random. Such an extractor can be used, for example, to generate keys for cryptographic systems.

Wigderson has spent much of his career tackling computational complexity theory, a broad area that includes pseudorandomness, cryptography, learning theory, algorithms, and modeling computational phenomena. It attempts to understand what can be computed, what resources are needed to do that computation, and what cannot be computed. In other words, it tries to develop efficient algorithms, or to prove that none exists.

That second part, trying to show that something cannot be solved efficiently, has not seen much progress, and that is the question that interests him more. Some problems are labeled P, for polynomial time, and can be solved relatively quickly by a computer. Others, such as factoring large primes, are labeled NP, for non-deterministic polynomial time. The solutions to NP problems can be verified quickly (you can easily check that a number is a product of two smaller ones), but the problem itself seems hard to solve fast. Whether there is a P version of every NP problem remains an open question. “It’s one of the most important intellectual problems—also practical, I guess—ever posed, and 50 years later we don’t know how to handle it,” Wigderson said.

In fact, while much of his work led to practical advances in computing, Wigderson has always been driven by curiosity more than attempts to design applications. “Definitely the intellectual issues are what excite me,” he said.

Expanding understanding

Wigderson also contributed to the understanding of zero-knowledge proofs. Such proofs, defined by 2012 A.M. Turing Award laureates Silvio Micali and Shafi Goldwasser, along with University of Toronto computer scientist and cryptology, security, and security protocols specialist Charles Rackoff, allow someone to demonstrate that they know the solution to a problem without actually sharing that solution. They asked which statements have such proofs. Wigderson, Micali, and Oded Goldreich, a professor of computer science at Israel’s Weizmann Institute of Science, showed that any mathematical proof could be converted into a zero-knowledge proof.

To picture a zero-knowledge proof, imagine that you draw a map of several countries of various shapes and sizes. You want to highlight the different countries by adding colors, so any two that border each other cannot have the same color. For some, but not all maps, this can be done using just three colors. You could prove to an inquisitor that a given map is three-colorable by giving them the complete coloring. In their zero-knowledge proof, the colors are encrypted, and the inquisitor is allowed to request opening the encryptions of only two adjacent countries. Repeating this many times (with the names of colors refreshed each time randomly) ensured the inquisitor will catch you if you did not actually have a three-coloring. But if you did so, the inquisitor will learn nothing except that the map was three-colorable.

Scientists long ago showed that any statement could be converted into such a map. If the statement were true, it could be filled in with three colors; if false, it could not be. Interactive zero-knowledge proofs allow for the demonstration of the truth of a statement, while concealing its proof. This technique can help keep cryptographic protocols like cryptocurrency exchange or online voting secure and private, even in the presence of faulty or malicious participants.

Wigderson also has found new ways to construct expander graphs, which are networks with few edges but strong connectivity. Expanders have many applications, including error-correcting codes, fault-tolerant networks, algorithms, and pseudorandom number generators.

After graduating summa cum laude from the Technion in 1980, Wigderson attended Princeton University, where he earned a Ph.D. in 1983. He did his post-doctoral work at the University of California, Berkeley. That was followed by a year spent as a visiting professor at IBM Research, then another year as a fellow at the Mathematical Sciences Research Institute in Berkeley. In 1986, he and his wife, Edna, also a computer scientist, returned to Israel, where he became a professor at Hebrew University, Jerusalem. In 1999, they returned to New Jersey with appointments at the IAS. Their younger son, Yuval, followed in his parents’ footsteps and is now a post-doc in mathematics. Their older son, Eyal, is a winemaker, and their daughter Einat is a psychologist.

In 2021, Wigderson shared the Abel Prize, which recognizes achievements in mathematics, with László Lovász of Eötvös Loránd University in Budapest, Hungary, in part for bringing the two fields together. That makes the Turing Award the second award Wigderson has won that is often described as the Nobel Prize of its field. “I’m waiting for the chemists to realize I exist,” he joked.

He credited the people he has collaborated with for teaching him a lot, from his Ph.D. advisor Richard Lipton and his post-doctoral supervisor Richard Karp to his own post-docs, who he said help dictate what he focuses on each year. “I’m learning a lot, continuously. I’m definitely interested in many more things than I actually manage to work on,” he said.

Some of what Wigderson has learned is available in his book, “Mathematics and Computation,” which is freely available on his website at https://www.math.ias.edu/avi/book and is meant to be intelligible to non-experts. He’s also working on a second book. He observed, “My field of computer science, the theory of computation and complexity theory, is one of the most exciting intellectual fields in existence. It’s very diverse, and it’s connected to lots of other sciences and math, and offers great questions that we cannot answer yet.”

Wigderson tells people that academia is a great life. “Nobody tells you what to do. You have to find what to do,” he said.

On the other hand, academics have to be comfortable with failure, he contended. “This is a life of constant failure. It’s rare that you manage to solve the problem that you’re working on,” he said, but then qualified his statement: “It’s not really failure because you learn from these failures, and the process of trying is enjoyable. And when you do succeed, it’s a triumph.”