Zvi Galil

Professor Zvi Galil is an Israeli-American computer scientist whose work has advanced the design and analysis of algorithms, particularly in string processing, graph algorithms, computational complexity, and cryptography. The author of more than 200 scientific papers, he has also led major academic institutions at Tel Aviv University, Columbia University, and the Georgia Institute of Technology. His influence extends well beyond theoretical research: he built departments and schools, cultivated scientific communities, trained generations of researchers, and helped create a pioneering online degree that substantially widened access to graduate education in computer science.

From Tel Aviv to the frontiers of computer science

Galil was born in Tel Aviv on June 26, 1947, during the final year of Mandatory Palestine. His father, botanist Jacob Galil, later became one of the founders of Tel Aviv University. Zvi Galil pursued his own academic training there, earning a bachelor's degree in applied mathematics in 1970 and a master's degree in 1971, both summa cum laude.

He completed his doctorate in computer science at Cornell University in 1975 under John Hopcroft, a foundational figure in algorithmic theory. Galil then spent a year as a postdoctoral researcher at IBM's Thomas J. Watson Research Center in Yorktown Heights, New York. That combination of mathematics, industrial research, and theoretical computer science shaped a career concerned not only with whether a problem could be solved, but with how efficiently it could be solved.

Faster algorithms and deeper models of computation

String matching in real time

A major part of Galil's research concerns string algorithms: the methods computers use to find a pattern in a text, recognize palindromes, or compare sequences. Such problems underlie search systems, language processing, biological sequence analysis, data compression, and information security. Galil developed real-time algorithms for string matching and palindrome recognition that achieved optimal speed even on the basic computational model of a multi-tape Turing machine.

He also formulated a general predictability condition under which an online algorithm can be converted into a real-time algorithm. With Joel Seiferas, he improved time-optimal algorithms so that they also required only logarithmic space. Working with Dany Breslauer, Galil designed a parallel string-matching algorithm that performs linear total work in O(log log n) time; they subsequently showed that this running time was optimal among algorithms limited to linear work. With his students and collaborators, he developed more than a dozen leading algorithms for exact and approximate string matching, covering sequential and parallel computation as well as one- and multidimensional problems.

Galil is also credited with introducing the term stringology for the study of algorithms and mathematical structures involving strings. The term helped give a shared identity to a research community whose seemingly different applications rest on a common theoretical foundation.

Graphs, sparsification, and dynamic programming

Galil made important contributions to graph algorithms as well. In 1979, with Ofer Gabber, he solved an open problem by explicitly constructing a family of expander graphs with a specified expansion ratio. Expander graphs combine relatively few edges with strong connectivity, properties that have made them valuable in algorithm design, communications networks, coding theory, and computational complexity.

With his students, Galil developed a technique he called sparsification. By representing graph problems through sparser structures, the method accelerated dynamic graph algorithms that must respond as a graph changes. He also helped devise sparse dynamic programming, a method for speeding calculations of edit distances between strings. These contributions offered more than solutions to isolated problems: they provided general ways to identify which information a computation truly needs and which information can be omitted without compromising correctness.

His research also encompassed trivalent graph isomorphism, minimum-weight spanning trees, complexity, cryptography, and experimental design in collaboration with statistician Jack Kiefer. Across these subjects, the consistent question was the boundary of the possible: the least time, work, or memory required to obtain a correct result.

Building institutions and scientific communities

Galil served on the computer science faculty of Tel Aviv University from 1976 to 1995 and chaired its department in the early 1980s. He became a full professor in 1981. In 1982 he also joined Columbia University, where he chaired the Department of Computer Science from 1989 to 1994 and served as dean of the engineering school from 1995 to 2007. During his deanship, the school was named the Fu Foundation School of Engineering and Applied Science after a major gift honoring Chinese businessman Z. Y. Fu.

In 1982, Galil founded Columbia's Theory Day and organized the gathering for its first 15 years. The event continued as New York Area Theory Day, providing an enduring forum where researchers and students in theoretical computer science could exchange ideas. From 1983 to 1987, he chaired ACM SIGACT, the Association for Computing Machinery's special-interest group devoted to algorithms and computation theory.

Galil also played a sustained role in the stewardship of scientific publishing. He was editor in chief of the Journal of Algorithms from 1988 to 2003 and managing editor of the SIAM Journal on Computing from 1991 to 1997. These positions placed him at a critical point in the life of the field, where new ideas are evaluated, standards of rigor are maintained, and emerging areas of research gain definition.

President of Tel Aviv University

Galil returned to Israel in June 2007 to become the seventh president of Tel Aviv University. He served until 2009 and then returned to the faculty. Although his presidential tenure was brief, his appointment reflected his standing as both a scientist and an experienced international academic leader. It also reconnected the university where he had been educated with the institutional expertise he had acquired in the United States.

An online degree that changed the scale of access

In 2010, Galil became dean of the College of Computing at the Georgia Institute of Technology, commonly known as Georgia Tech, and served in that position until June 2019. The undertaking most closely associated with his deanship is the Online Master of Science in Computer Science, or OMSCS. Galil conceived the program with Udacity founder Sebastian Thrun and led the faculty effort that created its curriculum.

The innovation was not simply the use of online lectures. OMSCS combined large-scale enrollment, comparatively low cost, a complete academic curriculum, and a full Georgia Tech master's degree. Rather than offering non-degree enrichment alone, it allowed students in different locations to pursue a recognized graduate qualification without leaving their jobs, families, or home countries. The program grew into the largest online master's program in computer science in the United States and demonstrated that a leading research university could deliver demanding graduate education at scale.

Its effect reached beyond Georgia Tech. OMSCS became a major case study in the worldwide discussion of tuition costs, remote learning, and the use of technology to broaden professional opportunity. It encouraged other universities to reconsider assumptions about the relationship between selectivity, quality, affordability, and scale. After stepping down as dean, Galil returned to the faculty as the Frederick G. Storey Chair in Computing and served as an executive advisor to online programs.

Professional recognition, teaching, and giving

Galil was elected an ACM Fellow in 1995 for fundamental contributions to algorithm design and analysis and for outstanding service to theoretical computer science. He was elected to the United States National Academy of Engineering in 2004 and became a Fellow of the American Academy of Arts and Sciences in 2005. The University of Waterloo awarded him an honorary Doctor of Mathematics degree in 2012 in recognition of his work on graph algorithms and string matching. Columbia University awarded him an honorary doctorate in 2024, and in 2025 the Columbia Engineering Alumni Association presented him with the Michael Pupin Medal for service in science, technology, or engineering.

Recognition from students and colleagues also reflects Galil's influence as an educator and community builder. Columbia established the Zvi Galil Award for student life in 2008, and the Columbia Society of Graduates gave him its Great Teacher Award in 2009. In 2020, the Georgia Tech College of Computing's advisory board raised more than $2 million from over 130 donors to create an endowed chair bearing his name.

Galil supervised numerous computer scientists who went on to substantial careers in research and industry, among them Moti Yung, David Eppstein, Giuseppe Italiano, Matthew Franklin, Jonathan Katz, and Stuart Haber. His intellectual legacy therefore continues through later generations working in cryptography, algorithms, cybersecurity, and computational geometry.

His commitment to Israeli science has also taken philanthropic form. In 2022, Galil and his wife, marine biologist Professor Bella Galil, donated $1.5 million to the Steinhardt Museum of Natural History at Tel Aviv University. The gift supported a research and educational institution at the university where he had studied and later served as a researcher, department chair, and president.

Why this legacy belongs in Moreshet

Zvi Galil belongs in Moreshet because his life connects Israeli scientific achievement with enduring international influence. Educated at the young Tel Aviv University, he became a central figure in algorithm research, returned to lead his alma mater, and helped build major centers of research and teaching in the United States. His career embodies a Jewish and Israeli tradition of learning, analytical inquiry, movement between cultures, and the conversion of knowledge into a resource that serves others.

His significance rests on more than publications, academic titles, or academy memberships. His algorithms and techniques strengthened the ability of computer science to process texts, graphs, and complex information; his professional service sustained communities of researchers; and OMSCS created a practical route to graduate education for people unable to attend a conventional campus program. His support for the Steinhardt Museum adds an intergenerational commitment to Israeli science. Moreshet.com therefore records his legacy not only as the biography of an accomplished scientist, but as an example of how research, educational leadership, teaching, and philanthropy can work together to expand both human knowledge and access to it.