I was born in Haifa, Israel in 1956 and studied, together with my older brother Zvika, at the Reali School there. I participated in competitive sports during high school, reaching some regional competitions in high jump, long jump and shot put with modest success, never reaching a national level. I have been more successful in Mathematics. In elementary school, I had already been interested in mathematical puzzles, and I was fascinated by the beauty and elegance of the subject. Reali has been one of the leading schools in the country, and we had an unusual teacher of mathematics in my final years there. His name was Yakov Kaplan, and he came as an immigrant from Ukraine where he had written several textbooks for high school students. Kaplan gave extra classes covering advanced material for interested students, and I participated enthusiastically. This surely helped me win first place in the two main mathematics competitions for high school students we had in Israel at that time: the Mathematics Youth Olympics at the Weizmann Institute and the Grossman Contest in Mathematics at the Technion. During my last year in high school I met Paul Erdös, the legendary Hungarian mathematician who used to visit Israel often, and a question in extremal graph theory he suggested to me in one of these meetings, together with its natural extensions, later became the subject of my first paper and of my Master thesis.
In 1974 I started my compulsory military service. After a year of service I joined the academic reserve and started my BSc studies in Mathematics at the Technion, graduating in 1979. Returning to the army, I served in Intelligence as a research officer. During service I completed my MSc in Mathematics at Tel Aviv University, and my PhD focusing on discrete mathematics at the Hebrew University of Jerusalem under the supervision of Micha Perles. After graduation I spent two years at MIT, hosted by Daniel Kleitman who later became one of my close collaborators. At MIT I kept working in combinatorics but also spent considerable efforts in applications of tools and techniques from the area to theoretical computer science. In 1985 I returned to Israel and joined the School of Mathematical Sciences at Tel Aviv University. During 1989–1990 I spent a sabbatical at IBM Almaden, and in 1993 I accepted an offer from Bombieri to become a long term visitor at the Institute for Advanced Study in Princeton and help organize there a programme in Discrete Mathematics and Theoretical Computer Science. As part of this programme, which is now led by my long-time friend and collaborator Avi Wigderson, I kept visiting the Institute multiple times as a visiting professor until 2016. Additional universities and research institutes in which I have spent extended periods of time include: Harvard, Bell Laboratories, Bellcore and Microsoft Research (Redmond and Israel). I also served as the head of the School of Mathematical Sciences in Tel Aviv University between 1999 and 2001. In 2018 I moved to Princeton University as a Professor of Mathematics and a member of the programme of Computational and Applied Mathematics.
The main topics I investigated over the years are the following.
- The development of spectral techniques in the study of expander graphs and their applications, establishing discrete analogues of results in differential geometry.
- The foundation, with Matias and Szegedy, of the now active area of streaming algorithms, trying to characterize the properties of a stream of data that can be measured efficiently under space constraints.
- The proof of a discrete variant of Hilbert’s Nullstellensatz and its applications in the study of problems in Additive Number Theory, Graph Theory and Combinatorics.
- The solution, with Kleitman, of the Hadwiger Debrunner (p, q) problem raised in 1957, which extends the classical theorem of Helly.
- The solution of a problem of Shannon raised in 1956 about the zero-error capacity of a disjoint union of independent channels.
- The application of probabilistic methods in the study of extremal problems in combinatorics, graph theory and Ramsey theory and in the design of randomized algorithms and the investigation of questions in property testing.
I have been lucky to collaborate with a large number of excellent researchers including many of my superb graduate students, and I wish to thank all of them. I owe much of my success to my students and collaborators and hope to continue collaborating and working on the fascinating aspects of discrete mathematics and its applications for many years to come.
I am married to Nurit, whom I first met in kindergarten when I was 5 years old, and we have three daughters: Nilli, Natalie and Narkis. It is a special pleasure to thank them for their love and support.
29 September 2022 Hong Kong