Zvi Galil

Zvi Galil ( he, צבי גליל; born June 26, 1947) is an Israeli-American computer scientist and mathematician. Galil served as the President of Tel Aviv University from 2007 through 2009. From 2010 to 2019, he was the dean of the Georgia Institute of Technology College of Computing. His research interests include the design and analysis of algorithms, computational complexity and cryptography. He has been credited with coining the terms stringology and sparsification. He has published over 200 scientific papers and is listed as an ISI highly cited researcher.

Early life and education

Zvi Galil was born in Tel Aviv in Mandatory Palestine in 1947. He completed both his B.Sc. (1970) and his M.Sc. (1971) in applied mathematics, both summa cum laude, at Tel Aviv University before earning his Ph.D. in Computer Science at Cornell in 1975 under the supervision of John Hopcroft. He then spent a year working as a post-doctorate researcher at IBM's Thomas J. Watson Research Center in Yorktown Heights, New York.

Career

From 1976 until 1995 he worked in the computer science department of Tel Aviv University, serving as its chair from 1979 to 1982. In 1982 he joined the faculty of Columbia University, serving as the chair of the Computer Science Department from 1989-1994. From 1995-2007, he served as the dean of the Fu Foundation School of Engineering & Applied Science. In this position, he oversaw the naming of the school in honor of Chinese businessman Z. Y. Fu after a large donation was given in his name. At Columbia, he was appointed the Julian Clarence Levi Professor of Mathematical Methods and Computer Science in 1987, and the Morris and Alma A. Schapiro Dean of Engineering in 1995.

Galil served as the President of Tel Aviv University starting in 2007 (following Itamar Rabinovich), but resigned and returned to the faculty in 2009, and was succeeded by Joseph Klafter. He was named as the dean of Georgia Tech's College of Computing on April 9, 2010. At Georgia Tech, together with Udacity founder Sebastian Thrun, Galil conceived of the College of Computing’s Online Master of Science in Computer Science (OMSCS) program, and he led the faculty creation of the program. OMSCS went on to become the largest online master’s program in computer science in the United States. OMSCS has been featured in hundreds of articles including a 2013 front page article in the New York Times and 2021 interviews in the Wall Street Journal and Forbes. Inside Higher Education noted that OMSCS "suggests that institutions can successfully deliver high-quality, low-cost degrees to students at scale". The Chronicle of Higher Education noted that OMSCS "may have the best chance of changing how much students pay for a traditional degree". Galil stepped down as dean and returned to a regular faculty position in June 2019. He now serves as the Frederick G. Storey Chair in Computing and Executive Advisor to Online Programs at Georgia Tech.

Professional service

In 1982, Galil founded the Columbia University Theory Day and organized the event for the first 15 years. It still exists as the New York Area Theory Day. From 1983 to 1987, Galil served as the chairman of ACM SIGACT, an organization that promotes research in theoretical computer science. He served as managing editor of ''SIAM Journal on Computing'' from 1991 to 1997 and editor in chief of ''Journal of Algorithms'' from 1988 to 2003.

Research

Galil's research is in the areas of algorithms, particularly string and graph algorithms, complexity, and cryptography. He also conducted research in experimental design with Jack Kiefer.

Galil developed the fastest possible algorithms for string matching and palindrome recognition. These real-time algorithms apply to strings in the general alphabet, and they work on the most basic computer model of multi-tape Turing machines. Additionally, he invented the predictability condition that allows an online algorithm to be converted to a real-time algorithm if it satisfies the condition. Galil and Joel Seiferas later derived algorithms that have in addition optimal (logarithmic) space complexity.

Galil worked with Dany Breslauer to design a linear-work, ''O(loglogn)'' parallel algorithm for string matching, and they later proved it to have the best possible time complexity among linear work algorithms. With other computer scientists, he designed a constant-time linear-work randomized search algorithm to be used when the pattern preprocessing is given.

With his students, Galil designed more than a dozen currently-fastest algorithms for exact or approximate, sequential or parallel, and one- or multi-dimensional string matching.

Galil worked with other computer scientists to develop several currently-fastest graph algorithms. Examples include: maximum weighted matching; trivalent graph isomorphism; minimum weight spanning trees; and tree matching.

With his students, Galil invented a technique he named sparsification and a method named sparse dynamic programming. Both of these led to an increase in the speed of several dynamic graph algorithms.

In 1979, together with Ofer Gabber, Galil solved an open problem by constructing the first family of expander graphs (used for designing fast graph algorithms) with an explicit expansion ratio.

Awards and honors

In 1995, Galil was inducted as a Fellow of the Association for Computing Machinery for "fundamental contributions to the design and analysis of algorithms and outstanding service to the theoretical computer science community," and in 2004, he was elected to the National Academy of Engineering for "contributions to the design and analysis of algorithms and for leadership in computer science and engineering." In 2005, he was selected as a Fellow of the American Academy of Arts and Sciences. In 2008, Columbia University established the Zvi Galil award for student life. In 2009, the Columbia Society of Graduates awarded him the Great Teacher Award. In 2012, The University of Waterloo awarded Galil with an honorary Doctor of Mathematics degree for his "fundamental contributions in the areas of graph algorithms and string matching." In 2020, Academic Influence included Galil in the list of the 10 most influential computer scientists of the last decade, and the advisory board of the College of Computing at Georgia Tech raised over $2 million from over 130 donors to establish an endowed chair named after Galil.

References

External links

Home page
at Georgia Tech

{{DEFAULTSORT:Galil, Zvi
Columbia University faculty
Cornell University alumni
Fellows of the Association for Computing Machinery
Fellows of the American Association for the Advancement of Science
Israeli computer scientists
Israeli mathematicians
Theoretical computer scientists
1947 births
Living people
People from Tel Aviv
Tel Aviv University alumni
Members of the United States National Academy of Engineering
Georgia Tech faculty
IBM Research computer scientists
Presidents of universities in Israel