Zvi Galil

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. In 1975, he earned his Ph.D. in computer science at Cornell University under the supervision of John Hopcroft.{{mathgenealogy|name=Zvi Galil|id=67227}} He then spent a year working as a post-doctorate researcher at IBM's Thomas J. Watson Research Center in Yorktown Heights, New York.{{cite press release|url=http://www.columbia.edu/cu/pr/95/18691.html|title=Zvi Galil Named Dean of Columbia's Engineering School|publisher=Columbia University|date=July 14, 1995|access-date=2019-06-05}}

File:Zvi Galil Dec 2016.jpg in December 2016]]

From 1976 until 1995, he worked in the computer science department at 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 to 1994. From 1995-2007, he served as the dean of the Columbia University Fu Foundation School of Engineering & Applied Science.{{cite book|last=McCaughey|first=Robert|url=https://books.google.com/books?id=CkYZBQAAQBAJ&pg=PA240|title=A Lever Long Enough: A History of Columbia's School of Engineering and Applied Science since 1864|date=2014|publisher=Columbia University Press|isbn=9780231166881|page=240}} 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.{{cite news|url=https://query.nytimes.com/gst/fullpage.html?res=9904E2D9113AF932A35753C1A961958260|title= Chinese Tycoon Gives Columbia $26 Million|date=1997-10-01|work=The New York Times|first=Karen W.|last=Arenson|access-date=2010-04-20}} 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.

In 2007, Galil succeeded Itamar Rabinovich as president of Tel Aviv University.{{cite news|title=Computer expert nominated for TAU presidency|url=https://www.jpost.com/Israel/Computer-expert-nominated-for-TAU-presidency|date=November 5, 2006|work=The Jerusalem Post}} In 2009, he resigned and returned to the faculty, and was succeeded by Joseph Klafter.{{cite web|author=Basch_Interactive |url=https://english.tau.ac.il/list_of_presidents |title=Presidents of Tel Aviv University | Tel Aviv University | Tel Aviv University |publisher=English.tau.ac.il |date=1980-01-01 |access-date=2020-02-18}}{{cite news|title=Tel Aviv University president quits / Sources: Galil was forced out of office|work=Haaretz|first1=Ofri|last1=Ilani|first2=Or|last2=Kashti|url=http://www.haaretz.com/print-edition/news/tel-aviv-university-president-quits-sources-galil-was-forced-out-of-office-1.279148|date=2009-07-02|access-date=2011-06-27}} 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.{{Cite news |last=Lewin |first=Tamar |date=2013-08-18 |title=Master's Degree Is New Frontier of Study Online |language=en-US |work=The New York Times |url=https://www.nytimes.com/2013/08/18/education/masters-degree-is-new-frontier-of-study-online.html |access-date=2023-01-02 |issn=0362-4331}} OMSCS went on to become the largest online master’s program in computer science in the United States.{{Cite web|last=Galil|first=Zvi|title=OMSCS: The Revolution Will Be Digitized|url=https://cacm.acm.org/magazines/2020/8/246362-omscs/fulltext|access-date=2020-07-27|website=cacm.acm.org|language=en}} 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.{{Cite news|last=Varadarajan|first=Tunku|date=2021-04-02|title=Opinion {{!}} The Man Who Made Online College Work|language=en-US|work=Wall Street Journal|url=https://www.wsj.com/articles/the-man-who-made-online-college-work-11617387464|access-date=2021-11-01|issn=0099-9660}}{{Cite news |last=Nietzel |first=Michael T. |title=Georgia Tech's Online MS In Computer Science Continues To Thrive. Why That's Important For The Future of MOOCs |url=https://www.forbes.com/sites/michaeltnietzel/2021/07/01/georgia-techs-online-ms-in-computer-science-continues-to-thrive-what-that-could-mean-for-the-future-of-moocs/ |access-date=2022-03-25 |website=Forbes |language=en}} Inside Higher Education noted that OMSCS "suggests that institutions can successfully deliver high-quality, low-cost degrees to students at scale".{{Cite web |title=Analysis shows Georgia Tech's online master's in computer science expanded access {{!}} Inside Higher Ed |url=https://www.insidehighered.com/digital-learning/article/2018/03/20/analysis-shows-georgia-techs-online-masters-computer-science |access-date=2022-03-25 |website=www.insidehighered.com |date=20 March 2018 |language=en}} The Chronicle of Higher Education noted that OMSCS "may have the best chance of changing how much students pay for a traditional degree".{{Cite web |title=What Georgia Tech's Online Degree in Computer Science Means for Low-Cost Programs |url=https://www.chronicle.com/article/what-georgia-techs-online-degree-in-computer-science-means-for-low-cost-programs/ |access-date=2022-03-25 |website=www.chronicle.com|date=6 November 2014 }} A 2023 Forbes article, titled "The Greatest Degree Program Ever", stated that OMSCS "is - by nearly any measure - the most successful degree program in history".{{Cite web |last=Busteed |first=Brandon |title=The Greatest Degree Program Ever |url=https://www.forbes.com/sites/brandonbusteed/2023/11/10/the-greatest-degree-program-ever/ |access-date=2023-11-17 |website=Forbes |language=en}} Galil stepped down as dean and returned to a regular faculty position in June 2019.{{cite web|url=https://www.cc.gatech.edu/news/620459/colleges-skyrocketing-stature-global-impact-highlight-galils-legacy|title=College's Skyrocketing Stature, Global Impact Highlight Galil's Legacy|publisher=Georgia Tech College of Computing|date=April 16, 2019|access-date=2019-06-05}}{{Cite web|url=https://issuu.com/gtalumni/docs/vol95_no3_low_res/56|title=Georgia Tech Alumni Magazine, Vol. 95 No. 3, Fall 2019|website=Issuu|date=11 October 2019 |language=en|access-date=2020-04-21}} He now serves as the Frederick G. Storey Chair in Computing and Executive Advisor to Online Programs at Georgia Tech.

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.{{Cite web|title=New York Area Theory Day|url=http://www.cs.columbia.edu/theory/thday.htm|access-date=2020-06-03|website=www.cs.columbia.edu}} From 1983 to 1987, Galil served as the chairman of ACM SIGACT, an organization that promotes research in theoretical computer science.{{cite journal|date=Fall 1987|title=Front matter|url=http://portal.acm.org/citation.cfm?id=38309|journal=ACM SIGACT News|volume=19|issue=1}} 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.

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

Galil's real-time algorithms are the fastest possible for string matching and palindrome recognition, and they work even on the most basic computer model, the multi-tape Turing machine. More generally, he formulated a "predictability" condition that allows any complying online algorithm to be converted to a real-time algorithm.{{Cite journal |last=Galil |first=Zvi |date=1981-01-01 |title=String Matching in Real Time |journal=Journal of the ACM |volume=28 |issue=1 |pages=134–149 |doi=10.1145/322234.322244 |s2cid=9164969 |issn=0004-5411|doi-access=free }}{{Cite journal |last=Galil |first=Zvi |date=1978-04-01 |title=Palindrome recognition in real time by a multitape turing machine |journal=Journal of Computer and System Sciences |language=en |volume=16 |issue=2 |pages=140–157 |doi=10.1016/0022-0000(78)90042-9 |issn=0022-0000|doi-access=free }} With Joel Seiferas, Galil improved the time-optimal algorithms to be space optimal (logarithmic space) as well.{{Cite journal |last1=Galil |first1=Zvi |last2=Seiferas |first2=Joel |date=1983-06-01 |title=Time-space-optimal string matching |journal=Journal of Computer and System Sciences |language=en |volume=26 |issue=3 |pages=280–294 |doi=10.1016/0022-0000(83)90002-8 |issn=0022-0000|doi-access=free |hdl=1802/10578 |hdl-access=free }}

Galil worked with Dany Breslauer to design a linear-work, O(loglogn) parallel algorithm for string matching,{{Cite journal |last1=Breslauer |first1=Dany |last2=Galil |first2=Zvi |date=1990-12-01 |title=An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm |url=https://epubs.siam.org/doi/10.1137/0219072 |journal=SIAM Journal on Computing |volume=19 |issue=6 |pages=1051–1058 |doi=10.1137/0219072 |issn=0097-5397}} and they later proved it to have the best possible time complexity among linear work algorithms.{{Cite journal |last1=Breslauer |first1=Dany |last2=Galil |first2=Zvi |date=1992-10-01 |title=A Lower Bound for Parallel String Matching |url=https://epubs.siam.org/doi/10.1137/0221050 |journal=SIAM Journal on Computing |volume=21 |issue=5 |pages=856–862 |doi=10.1137/0221050 |issn=0097-5397}} With other computer scientists, he designed a constant-time linear-work randomized search algorithm to be used when the pattern preprocessing is given.{{Cite journal |last1=Crochemore |first1=Maxime |last2=Galil |first2=Zvi |last3=Gasieniec |first3=Leszek |last4=Park |first4=Kunsoo |last5=Rytter |first5=Wojciech |date=1997-08-01 |title=Constant-Time Randomized Parallel String Matching |url=https://epubs.siam.org/doi/10.1137/S009753979528007X |journal=SIAM Journal on Computing |volume=26 |issue=4 |pages=950–960 |doi=10.1137/S009753979528007X |issn=0097-5397}}

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 trivalent graph isomorphism{{Cite journal |last1=Galil |first1=Zvi |last2=Hoffmann |first2=Christoph M. |last3=Luks |first3=Eugene M. |last4=Schnorr |first4=Claus P. |last5=Weber |first5=Andreas |date=1987-07-01 |title=An O(n3log n) deterministic and an O(n3) Las Vegs isomorphism test for trivalent graphs |journal=Journal of the ACM |volume=34 |issue=3 |pages=513–531 |doi=10.1145/28869.28870 |s2cid=18031646 |issn=0004-5411|doi-access=free }} and minimum weight spanning trees.{{Cite journal |last1=Gabow |first1=Harold N. |last2=Galil |first2=Zvi |last3=Spencer |first3=Thomas |last4=Tarjan |first4=Robert E. |date=1986-06-01 |title=Efficient algorithms for finding minimum spanning trees in undirected and directed graphs |url=https://doi.org/10.1007/BF02579168 |journal=Combinatorica |language=en |volume=6 |issue=2 |pages=109–122 |doi=10.1007/BF02579168 |s2cid=35618095 |issn=1439-6912}}

With his students, Galil devised a technique he called "sparsification"{{Cite journal |last1=Eppstein |first1=David |last2=Galil |first2=Zvi |last3=Italiano |first3=Giuseppe F. |last4=Nissenzweig |first4=Amnon |date=1997-09-01 |title=Sparsification—a technique for speeding up dynamic graph algorithms |journal=Journal of the ACM |volume=44 |issue=5 |pages=669–696 |doi=10.1145/265910.265914 |s2cid=340999 |issn=0004-5411|doi-access=free }} and a method he called "sparse dynamic programming".{{Cite journal |last1=Eppstein |first1=David |last2=Galil |first2=Zvi |last3=Giancarlo |first3=Raffaele |last4=Italiano |first4=Giuseppe F. |date=1992-07-01 |title=Sparse dynamic programming I: linear cost functions |journal=Journal of the ACM |volume=39 |issue=3 |pages=519–545 |doi=10.1145/146637.146650 |s2cid=17060840 |issn=0004-5411|doi-access=free }} The first was used to speed up dynamic graph algorithms. The second was used to speed up the computations of various edit distances between strings.

In 1979, together with Ofer Gabber, Galil solved the previously open problem of constructing a family of expander graphs with an explicit expansion ratio,{{Cite journal |last1=Gabber |first1=Ofer |last2=Galil |first2=Zvi |date=1981-06-01 |title=Explicit constructions of linear-sized superconcentrators |journal=Journal of Computer and System Sciences |language=en |volume=22 |issue=3 |pages=407–420 |doi=10.1016/0022-0000(81)90040-4 |issn=0022-0000|doi-access=free }} useful in the design of fast graph algorithms.

In 1995, Galil was inducted as a fellow at the Association for Computing Machinery for "fundamental contributions to the design and analysis of algorithms and outstanding service to the theoretical computer science community,"[http://fellows.acm.org/fellow_citation.cfm?id=1401728&srt=all ACM Fellow Award / Zvi Galil] 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."{{cite web|title=Dr. Zvi Galil|url=http://www.nae.edu/MembersSection/Directory20412/30814.aspx|work=NAE Members|publisher=National Academy of Engineering|access-date=May 11, 2012}}{{cite web|title=Zvi Galil Elected to National Academy of Engineering|url=http://www.columbia.edu/cu/news/04/02/zvi_nae.html|work=Columbia News|publisher=Columbia University|access-date=May 11, 2012}}

In 2005, he was selected as a Fellow of the American Academy of Arts and Sciences.{{citation|url=http://www.amacad.org/news/new2005.aspx|title=Academy Elects 225th Class of Fellows and Foreign Honorary Members|publisher=American Association for the Advancement of Science|date=April 26, 2005}}

In 2008, Columbia University established the Zvi Galil award for student life.{{cite web|url=https://www.cc-seas.columbia.edu/awards/descriptions/ZviGalilAward|title=Zvi Galil Award|publisher=Columbia College|access-date=2019-06-05}} In 2009, the Columbia Society of Graduates awarded him the Great Teacher Award.{{cite magazine|url=https://www.college.columbia.edu/cct/archive/sep_oct09/around_the_quads_0|title=Quigley, Galil To Receive Great Teacher Awards|newspaper=Columbia College Today|date=September 2009|access-date=2019-06-05}}

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."{{cite web|last=Smyth|first=Pamela|title=University of Waterloo to award eight honorary degrees at spring convocation|url=http://newsrelease.uwaterloo.ca/news.php?id=5385|work=Waterloo Communications|publisher=University of Waterloo|access-date=May 11, 2012}} 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.{{Cite web|last1=Larson|first1=Erik J.|last2=PhD|title=Top Influential Computer Scientists Today|url=https://academicinfluence.com/rankings/people/most-influential-computer-scientists-today|access-date=2021-05-05|website=academicinfluence.com|date=19 March 2020 |language=en}}{{Cite web|date=2021-06-02|title=New Endowed Chair Honors Inclusion and Diversity|url=https://www.cc.gatech.edu/news/647877/new-endowed-chair-honors-inclusion-and-diversity|access-date=2021-06-09|website=College of Computing|language=en}} In 2024, Columbia University awarded Galil an honorary doctorate.{{Cite web |date=2024-04-10 |title=Columbia Announces 2024 Commencement Honorary Degree Recipients - Bwog |url=https://bwog.com/2024/04/columbia-announces-2024-commencement-honorary-degree-recipients/ |access-date=2025-01-29 |website=Bwog - Columbia Student News |language=en}}

{{Reflist|2}}

• [https://www.cc.gatech.edu/people/zvi-galil Home page] at Georgia Tech

{{Authority control}}

{{DEFAULTSORT:Galil, Zvi}}

Category:Columbia University faculty

Category:Cornell University alumni

Category:1995 fellows of the Association for Computing Machinery

Category:Fellows of the American Association for the Advancement of Science

Category:Israeli mathematicians

Category:Israeli theoretical computer scientists

Category:1947 births

Category:Living people

Category:Academics from Tel Aviv

Category:Tel Aviv University alumni

Category:Members of the United States National Academy of Engineering

Category:Georgia Tech faculty

Category:IBM Research computer scientists

Category:Presidents of universities in Israel