Honoring the Ties Between Computer Science and Mathematics

When the Norwegian Academy of Science and Letters in March named László Lovász and Avi Wigderson as recipients of the 2021 Abel Prize, it turned a spotlight on interactions between computer science and mathematics that have shaped both fields over the past half-century.

The prizewinners' work "is a celebration of the tight connection between discrete mathematics and theoretical computer science and the spectacular development of these two areas," said Noga Alon, a professor of mathematics at Princeton University and a Baumritter Professor Emeritus of mathematics and computer Science at Tel Aviv University noted for his contributions to combinatorics and theoretical computer science.

First awarded in 2003 and carrying a cash prize of 7.5 million Norwegian kroner (about US$890,000), the Abel Prize has become one of the world's top honors in mathematics. Wigderson, Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study (IAS) at Princeton, is the first Abel recipient with a doctorate in computer science. Lovász, of Hungary's Eötvös Loránd University, holds a doctorate in mathematics but, like the other Hungarian to have received an Abel, Endre Szemerédi, Lovász has had a major influence on theoretical computer science.

An early influence in the careers of both laureates was the P versus NP question, which Wigderson called "one of the deepest intellectual questions ever asked." Over time, he said, "it became clearer and clearer that [P versus NP] is really about whether we can know everything we want to know, whether creativity can be automated, and whether anything scientists and mathematicians do can be done automatically."

More technically, P versus NP asks: Does the ability to verify a solution in polynomial time imply one can also produce one in polynomial time? The question launched the field of computational complexity theory and forms the context for much of the work of the two laureates. 

Born in 1948, Lovász is an exemplar of the illustrious tradition of Hungarian mathematics. His early encounters with Hungarian mathematician Paul Erdös were a major inspiration, and led Lovász to discrete mathematics. In the 1960s and 1970s, "This somewhat obscure branch of mathematics became extremely important," Lovász said. Its merging with computer science "led to concretely new ways of looking at complexity and algorithms and the structure of mathematics."

His own work was crucial in those advances. "Lovász obtained ground breaking results in discrete mathematics that had highly significant applications in theoretical computer science," Alon said. "He solved several outstanding problems, developing new techniques that revolutionized combinatorics, transforming it into a modern area with tight connections to other mathematical disciplines."

One example is Lovász's solution of a classic problem in information theory, the calculation of the Shannon capacity of a pentagon. "The tools Lovász developed for this particular problem were quite revolutionary," said Gil Kalai, the Henry and Manya Noskwith Professor Emeritus of Mathematics at the Hebrew University of Jerusalem. One of those tools, now known as the Lovász theta function, "lives between two parameters that are NP-complete to find, but is itself accessible to computers. And this is something that was not initially motivated by computer science but has become very important in computer science."

Leonid Khachiyan's 1979 invention of the ellipsoid method, which provides a polynomial-time algorithm for linear programming, was a breakthrough in the theory of algorithms. Lovász, together with Alexander Schrijver and Martin Grötschel, used the ellipsoid method to create polynomial-time algorithms for a host of other optimization problems, leading to a revolution in algorithm design.

Another major advance was the LLL algorithm, invented in 1982 by Lovász together with the Dutch brothers Arjen and Hendrik Lenstra. While its original aim was to solve problems in the geometry of numbers, the LLL algorithm immediately found widespread use because of its simplicity and applicability to a variety of problems. It stands at the foundation of lattice-based cryptographic systems, which to date are the only systems that can withstand an attack by a quantum computer. The now-classic book Geometric Algorithms and Combinatorial Optimization (Springer, second edition 1993), by Lovász, Grötschel, and Schrijver, treats both the ellipsoid-based algorithms and the LLL algorithm in a unified fashion.

Wigderson, born in 1956, is a computer scientist with unusually broad and deep knowledge of mathematics. "I think Avi has been responsible for more 'importing and exporting' between computer science and mathematics than any other researcher," said Boaz Barak, Gordon McKay Professor of Computer Science in the John A. Paulson School of Engineering and Applied Sciences of Harvard University. "He both used deep mathematical results to solve computer science challenges, and developed computer-science techniques that were later used to solve open problems in mathematics."

A major theme in the work of Wigderson (as well as in that of Lovász) is randomness. Computer scientists initially thought of randomness as noise or a source of errors, Barak explained. "But starting with the introduction of the Markov Chain Monte Carlo method, it became clear that randomness can also be a powerful tool for computation."

In some algorithms, randomness seemed to be indispensable, but then a deterministic algorithm was found; a celebrated example is the Agrawal-Kayal-Saxena algorithm for primality testing. So is randomness ever really essential?

In a sequence of papers with varying collaborators, including László Babai, a professor of computer science and mathematics at the University of Chicago; Lance Fortnow, now dean of the College of Computing at the Illinois Institute of Technology; Noam Nisan, now dean of the School of Computer Science and Engineering of the Hebrew University of Jerusalem, and Russell Impagliazzo, now a professor of computer science at the University of California, San Diego specializing in computational complexity theory, Wigderson proved a result about the relation between hardness and randomness. If truly hard problems exist—and the consensus is that they do—then any randomized algorithm can be transformed into a deterministic algorithm having comparable efficiency. The process of "derandomization" is generic and does not depend on the internal details of the randomized algorithm.

Later Wigderson, together with Impagliazzo and Valentine Kabanets, now a professor in the School of Computing Science at Simon Fraser University in British Columbia, Canada, obtained a result going in the opposite direction. They showed that, if efficient deterministic algorithms exist for problems for which randomized algorithms are known, then there must exist a truly hard problem.

"Eliminating randomness from computation can often be important for both theoretical and practical reasons," Barak said. Wigderson "has published some of the central papers in this area, and showed its deep connections with longstanding questions in computational complexity."

In the late 1980s, Wigderson's work provided stunning new insights into the counterintuitive notion of a zero-knowledge proof. This is a protocol that allows you to convince another person that your proof is correct, while revealing zero information about exactly what is in the proof. With Oded Goldreich, now a professor of computer science on the Faculty of Mathematics and Computer Science of Israel's Weizmann Institute of Science, and Silvio Micali, ACM A.M. Turing Award recipient and Ford Professor of Engineering in the Computer Sciences and Artificial Intelligence Laboratory of the Massachusetts Institute of Technology, Wigderson showed that such a zero-knowledge proof can be constructed for any mathematical proof. While the impact of zero-knowledge proofs was initially thought to be only theoretical, today the concept is used in blockchain technology and digital currencies.

Lovász and Wigderson each have received a host of other honors for their accomplishments, including the ACM Knuth Prize, presented to Lovász in 1999 and to Wigderson in 2019. Both researchers are enormously prolific and have collaborated widely. Lovász has written 300 papers and Wigderson 200; each has close to 150 co-authors.

While on the faculty of the Hebrew University in Jerusalem from 1986 until 1999, Wigderson contributed to making Israel the powerhouse in theoretical computer science that it is today. He had perhaps an even greater impact after moving to Princeton's Institute for Advanced Study in 1999. "The school he built up at the IAS is incredible," said Hans Munthe-Kaas of the University of Bergen in Norway, who chairs the Abel Prize selection committee. "Essentially everybody in the field [of theoretical computer science] has at some time been affiliated with his group there." Wigderson's book Mathematics and Computation: A Theory Revolutionizing Technology and Science (Princeton University Press, 2019) brings his wide-ranging knowledge and insights to a broad audience.

Lovász "has been a huge inspiration to many people within the areas of discrete mathematics, combinatorics, and graph theory," Munthe-Kaas said. Lovász was on the faculty at Yale University before leaving academia in 1999 to take a position in the then newly established Theory Group at Microsoft Research, a move that raised the profile of that enterprise. After seven years there, he returned to academia as a professor at Eötvös Loránd University. In 2018, while Lovász was serving his second term as president of the Hungarian Academy of Sciences, the government of Viktor Orbán laid plans to shift a large part of the academy's budget to the Ministry of Innovation and Technology. Although Lovász's efforts to prevent the move were unsuccessful, he proved a principled and steadfast advocate for the independence of science.

Both men are beloved figures, friendly and approachable, with Lovász soft-spoken and modest, and Wigderson charming and ebullient. Kalai, who knows both well, said, "Their generosity and friendliness, and their sincerity and integrity, are all part of their own success, but also the success of the field and the pleasant atmosphere in these areas of mathematics."

 

Allyn Jackson is a journalist specializing in science and mathematics, who is based in Germany.