Zvi Galil

Zvi Galil
Born	(1947-06-26) June 26, 1947 Tel Aviv, Mandatory Palestine
Occupation(s)	Computer scientist, academic administrator
Years active	1976–present
Known for	Stringology, sparsification, online Master of Science in Computer Science (OMSCS) program

Zvi Galil (; born June 26, 1947) is a distinguished Israeli-American computer scientist. He has held prominent leadership roles including dean of the Columbia University School of Engineering and president of Tel Aviv University from 2007 until 2009. Subsequently, from 2010 through 2019, he served as dean of the Georgia Institute of Technology College of Computing.

His scholarly work centers on the creation and analysis of algorithms, computational complexity, and cryptography. He is recognized for introducing the concepts of stringology and sparsification.

Early life and education

Born in Tel Aviv during the era of Mandatory Palestine in 1947, Galil completed his undergraduate and master's degrees in applied mathematics at Tel Aviv University, graduating both with highest honors (summa cum laude) in 1970 and 1971, respectively. He earned his Ph.D. in computer science from Cornell University in 1975 under the guidance of John Hopcroft. Following his doctorate, he spent a year conducting postdoctoral research at the Thomas J. Watson Research Center of IBM in New York.

Career

Galil’s academic career began at the computer science department of Tel Aviv University, where he worked from 1976 to 1995 and served as department chair between 1979 and 1982. In 1982, he transitioned to Columbia University, leading its computer science department as chair from 1989 to 1994. From 1995 to 2007, he was dean of Columbia’s Fu Foundation School of Engineering & Applied Science, overseeing its renaming following a significant endowment by Chinese entrepreneur Z. Y. Fu. At Columbia, he held the Julian Clarence Levi Professorship and was appointed Morris and Alma A. Schapiro Dean of Engineering.

In 2007, Galil assumed the presidency of Tel Aviv University but stepped down in 2009 to return to faculty responsibilities; his successor was Joseph Klafter. On April 9, 2010, he became dean of the College of Computing at Georgia Tech. During his tenure there, Galil collaborated with Udacity founder Sebastian Thrun to create the groundbreaking online Master of Science in Computer Science (OMSCS) program, leading its faculty development efforts. The OMSCS program expanded into the largest online master's degree in computer science across the United States and gained acclaim for providing affordable, high-quality education at scale.

This initiative garnered significant media exposure, including front-page coverage in The New York Times and features in The Wall Street Journal and Forbes. Industry experts have praised OMSCS as a pioneering model for broadening educational access while lowering costs. A 2023 article in Forbes described it as "the most successful degree program in history." Galil concluded his deanship in June 2019 and currently holds the Frederick G. Storey Chair in Computing while serving as Executive Advisor to Online Programs at Georgia Tech.

Professional service

In 1982, Galil established Columbia University Theory Day and managed it for fifteen years; this event continues today as the New York Area Theory Day. Between 1983 and 1987, he chaired ACM SIGACT, fostering research in theoretical computer science. Additionally, he was managing editor of SIAM Journal on Computing from 1991 to 1997 and served as editor-in-chief of Journal of Algorithms between 1988 and 2003.

Research

Galil's scholarly work primarily revolves around algorithms, with a particular emphasis on string algorithms and graph-related algorithms, as well as computational complexity and cryptography. He has also partnered with Jack Kiefer on studies in experimental design.

His development of real-time algorithms for string matching and palindrome detection achieves optimal performance on fundamental multi-tape Turing machine frameworks. Galil introduced a "predictability" criterion that allows online algorithms to be transformed into real-time versions. In collaboration with Joel Seiferas, he further refined these algorithms to operate within logarithmic space constraints.

Working alongside Dany Breslauer, Galil engineered a parallel string matching algorithm with linear work and an O(loglogn) time complexity, which has been demonstrated to be optimal among algorithms with linear work. Additionally, he co-developed, with other researchers, a randomized search algorithm that operates in constant time and linear work for patterns that have undergone preprocessing.

Together with his students, Galil has produced more than a dozen of the fastest-known algorithms addressing exact or approximate string matching problems, applicable in both sequential and parallel processing environments, and spanning one- and multi-dimensional cases.

In the domain of graph algorithms, his contributions include efficient solutions such as trivalent graph isomorphism and minimum weight spanning tree computations. Alongside his students, he introduced the concept of "sparsification" to speed up dynamic graph algorithms and developed "sparse dynamic programming" techniques to improve calculations related to edit distance.

In 1979, partnering with Ofer Gabber, Galil resolved a longstanding challenge by constructing expander graphs with explicitly defined expansion ratios, which has facilitated the creation of faster graph algorithms.

Awards and honors

Galil was named a fellow of the Association for Computing Machinery in 1995 in recognition of his "fundamental contributions to the design and analysis of algorithms and outstanding service to the theoretical computer science community." In 2004, he was inducted into the National Academy of Engineering for his "contributions to the design and analysis of algorithms and leadership in computer science and engineering."

He was honored as a Fellow of the American Academy of Arts and Sciences in 2005.

In 2008, Columbia University established the Zvi Galil award dedicated to student life initiatives. The following year, in 2009, he received the Great Teacher Award from the Columbia Society of Graduates.

The University of Waterloo conferred upon Galil an honorary Doctor of Mathematics degree in 2012, acknowledging his "fundamental contributions in graph algorithms and string matching." In 2020, Academic Influence recognized him as one of the ten most impactful computer scientists over the previous decade. That same year, Georgia Tech’s College of Computing secured over $2 million from more than 130 donors to create an endowed chair bearing his name.

Columbia University bestowed an honorary doctorate on Galil in 2024. Subsequently, in 2025, the Columbia Engineering Alumni Association awarded him the Michael Pupin Medal for distinguished service to science, technology, or engineering.

External links

• Official homepage at Georgia Tech