Noga Alon

Noga Alon

Affiliation at the time of the award:

Princeton University, USA

Award citation:

“for his fundamental contributions to Combinatorics and Theoretical Computer Science”.

Prize share:

Noga Alon

Adi Shamir 

“for their pioneering contributions to mathematical cryptography, combinatorics, and the theory of computer science”.

Noga Alon (born in Israel, 1956) is a Professor of Mathematics at Princeton University, a Baumritter Professor Emeritus of Mathematics and Computer Science at Tel Aviv University, and one of the most influential mathematicians worldwide. His research and developments changed the face of the field, created new concepts and original methods, and contributed greatly to the development of theoretical research and their applications in discrete mathematics, information theory, graph theory, and their uses in the theory of computer science. He is one of the most prolific mathematicians in the world, published hundreds of articles, and trained many research students in mathematics and computer science.

Alon showed a profound interest in mathematics from an early age, drawn to its objectivity and pursuit of absolute truth. Encouraged by his parents and his math teacher to follow his passions, Alon delved into mathematics and participated in math competitions. After graduating in mathematics at the Technion, he continued to earn his master’s and doctoral degrees at the Hebrew University of Jerusalem in 1983 and held visiting positions in various research institutes, including MIT, Harvard, the Institute for Advanced Study in Princeton, IBM Almaden Research Center, Bell Laboratories, Bellcore and Microsoft Research (Redmond and Israel). He joined Tel Aviv University in 1985, served as the head of the School of Mathematical Sciences in 1999-2000, retired from Tel Aviv, and moved to Princeton in 2018, where he works until today, and supervised many PhD students. He serves on the editorial boards of more than a dozen international professional journals and has given invited lectures at many conferences. He was the head of the scientific committee of the World Congress of Mathematics (Madrid, 2006) and a member of various prestigious prize committees worldwide. He published more than six hundred research papers and one book.

Alon’s contributions to mathematics are broad and have influenced many related areas in the theoretical and applied sciences. With his collaborators he established the tight connection between the expansion properties of a graph and its spectral properties and found numerous applications of expanders in Combinatorics and Theoretical Computer Science. His results stimulated a great amount of further work and are cited in essentially all subsequent extensive work in the area. In related work, he pioneered the application of spectral methods in the study of algorithmic problems. Alon proved the Combinatorial Nullstellensatz (1995), a powerful algebraic technique that yielded highly significant applications in Graph Theory, Combinatorics, and Additive Number Theory, including an extension of the Four-Color Theorem. With Nathanson and Ruzsa (1996) he obtained generalizations of the Cauchy-Davenport Theorem. In joint work with Kleitman (1992), he settled a problem of Hadwiger and Debrunner in Combinatorial Geometry raised in 1957, proving a far-reaching generalization of Helly’s Theorem. The method has proven to be highly influential and is described in most recent books and survey articles on the subject. Alon (1998) disproved a conjecture of Shannon, raised in 1956, proving the surprising fact that the Shannon capacity of a disjoint union of two channels can be much bigger than the sum of their capacities or even than any fixed power of this sum.

Alon played a major role in the development of probabilistic methods in Combinatorics, and his book with Spencer on the subject (first edition in 1992, fourth edition in 2016) is the undisputed leading text in this central area. His Color-Coding method, developed with Yuster and Zwick (1995), found applications in several other fields including the theory of Fixed Parameter Tractability and Bioinformatics. His joint work with Matias and Szegedy (1999) initiated the study of streaming algorithms investigating which statistical properties of a stream of data can be sampled and estimated on the fly. This has literally created a new active area of streaming and sketching algorithms and has numerous theoretical and applied applications.

Alon with his collaborators (1994) developed an algorithmic version of Szemerédi’s Regularity Lemma, discovered its connection to a classical inequality of Grothendieck, and used it to settle essentially all major open problems in the theory of Property Testing for dense graphs. This generated extensive research and played an important role in the subsequent development of Lovasz and his collaborators’ theory of convergent graph sequences.

Some of Noga Alon’s most influential works deal with “expander graphs”. These are sparse networks with strong connectivity properties. They were originally conceived as a way to build economical, robust networks (phone or computer) and have found extensive applications in computer science, in designing algorithms, error-correcting codes, pseudorandom generators, and more. Alon, in part with Milman, established a tight connection between the expansion properties of a graph and its “spectral” properties, reminiscent of a relation between classical and quantum mechanics, and found numerous applications of expanders in combinatorics and in theoretical computer science. Alon’s results stimulated a great amount of further work and are cited in essentially all subsequent extensive work in the area.
Noga Alon is being awarded the 2024 Wolf Prize for his profound impact on Discrete Mathematics and related areas. His seminal contributions include the development of ingenious techniques in Combinatorics, Graph Theory, and Theoretical Computer Science, and the solution of long-standing problems in these fields as well as in Analytical Number Theory, Combinatorial Geometry, and Information Theory.