Zvi Galil

Zvi Galil
Galil in 2023
Born (1947-06-26) June 26, 1947 (age 77)[2]
Alma mater
Awards
Scientific career
Fields
Institutions
Doctoral advisorJohn Hopcroft[1]
Doctoral students

Zvi Galil (Hebrew: צבי גליל; born June 26, 1947) is an Israeli-American computer scientist and mathematician. He has served as the dean of the Columbia University School of Engineering and as 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.[3]

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.[4][5] He has published over 200 scientific papers[6] and is listed as an ISI highly cited researcher.[7]

Early life and education

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 Cornell computer science professor John Hopcroft.[1] He then spent a year working as a post-doctorate researcher at IBM's Thomas J. Watson Research Center in Yorktown Heights, New York.[8]

Career

Galil at Georgia Tech 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.[2][8] From 1995-2007, he served as the dean of the Columbia University Fu Foundation School of Engineering & Applied Science.[9] 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.[10] 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.[2]

In 2007, Galil succeeded Itamar Rabinovich as president of Tel Aviv University.[11] In 1009, he resigned and returned to the faculty, and was succeeded by Joseph Klafter.[12][13] He was named as the dean of Georgia Tech's college of computing on April 9, 2010.[3] 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.[14] OMSCS went on to become the largest online master’s program in computer science in the United States.[15] 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.[14][16][17] Inside Higher Education noted that OMSCS "suggests that institutions can successfully deliver high-quality, low-cost degrees to students at scale".[18] The Chronicle of Higher Education noted that OMSCS "may have the best chance of changing how much students pay for a traditional degree".[19] 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".[20] Galil stepped down as dean and returned to a regular faculty position in June 2019.[21][22] 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.[23] From 1983 to 1987, Galil served as the chairman of ACM SIGACT, an organization that promotes research in theoretical computer science.[24] 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, 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.[25][26] With Joel Seiferas, Galil improved the time-optimal algorithms to be space optimal (logarithmic space) as well.[27]

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

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;[31] trivalent graph isomorphism;[32] and minimum weight spanning trees.[33]

With his students, Galil devised a technique he called "sparsification"[34] and a method he called "sparse dynamic programming".[35] 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,[36] useful in the design of fast graph algorithms.

Awards and honors

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,"[37] 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."[38][39]

In 2005, he was selected as a Fellow of the American Academy of Arts and Sciences.[40]

In 2008, Columbia University established the Zvi Galil award for student life.[41] In 2009, the Columbia Society of Graduates awarded him the Great Teacher Award.[42]

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."[43] 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.[44][45]

References

  1. ^ a b c Zvi Galil at the Mathematics Genealogy Project
  2. ^ a b c d Eppstein, David; Italiano, Giuseppe F. (March 1999). "PREFACE: Festschrift for Zvi Galil". Journal of Complexity. 15 (1): 1–3. doi:10.1006/jcom.1998.0492.
  3. ^ a b "Institute names next College of Computing Dean" (Press release). Georgia Institute of Technology. 2010-04-09. Retrieved 2010-04-09.
  4. ^ "Introduction to Stringology". The Prague Stringology Club. Czech Technical University in Prague. Retrieved May 14, 2012.
  5. ^ Zvi, Galil; David Eppstein; Giuseppe F. Italiano; Amnon Nissenzweig (September 1997). "Sparsification - a technique for speeding up dynamic graph algorithms". Journal of the ACM. 44 (5): 669–696. doi:10.1145/265910.265914. S2CID 340999.
  6. ^ "Zvi Galil". The DBLP Computer Science Bibliography. Digital Bibliography & Library Project. Retrieved 2016-03-24.
  7. ^ "ISI Highly Cited Researchers Version 1.1: Zvi Galil". ISI Web of Knowledge. Retrieved 2011-06-27.
  8. ^ a b "Zvi Galil Named Dean of Columbia's Engineering School" (Press release). Columbia University. July 14, 1995. Retrieved 2019-06-05.
  9. ^ McCaughey, Robert (2014). A Lever Long Enough: A History of Columbia's School of Engineering and Applied Science since 1864. Columbia University Press. p. 240. ISBN 9780231166881.
  10. ^ Arenson, Karen W. (1997-10-01). "Chinese Tycoon Gives Columbia $26 Million". The New York Times. Retrieved 2010-04-20.
  11. ^ "Computer expert nominated for TAU presidency". The Jerusalem Post. November 5, 2006.
  12. ^ Basch_Interactive (1980-01-01). "Presidents of Tel Aviv University | Tel Aviv University | Tel Aviv University". English.tau.ac.il. Retrieved 2020-02-18.
  13. ^ Ilani, Ofri; Kashti, Or (2009-07-02). "Tel Aviv University president quits / Sources: Galil was forced out of office". Haaretz. Retrieved 2011-06-27.
  14. ^ a b Lewin, Tamar (2013-08-18). "Master's Degree Is New Frontier of Study Online". The New York Times. ISSN 0362-4331. Retrieved 2023-01-02.
  15. ^ Galil, Zvi. "OMSCS: The Revolution Will Be Digitized". cacm.acm.org. Retrieved 2020-07-27.
  16. ^ Varadarajan, Tunku (2021-04-02). "Opinion | The Man Who Made Online College Work". Wall Street Journal. ISSN 0099-9660. Retrieved 2021-11-01.
  17. ^ Nietzel, Michael T. "Georgia Tech's Online MS In Computer Science Continues To Thrive. Why That's Important For The Future of MOOCs". Forbes. Retrieved 2022-03-25.
  18. ^ "Analysis shows Georgia Tech's online master's in computer science expanded access | Inside Higher Ed". www.insidehighered.com. 20 March 2018. Retrieved 2022-03-25.
  19. ^ "What Georgia Tech's Online Degree in Computer Science Means for Low-Cost Programs". www.chronicle.com. 6 November 2014. Retrieved 2022-03-25.
  20. ^ Busteed, Brandon. "The Greatest Degree Program Ever". Forbes. Retrieved 2023-11-17.
  21. ^ "College's Skyrocketing Stature, Global Impact Highlight Galil's Legacy". Georgia Tech College of Computing. April 16, 2019. Retrieved 2019-06-05.
  22. ^ "Georgia Tech Alumni Magazine, Vol. 95 No. 3, Fall 2019". Issuu. 11 October 2019. Retrieved 2020-04-21.
  23. ^ "New York Area Theory Day". www.cs.columbia.edu. Retrieved 2020-06-03.
  24. ^ "Front matter". ACM SIGACT News. 19 (1). Fall 1987.
  25. ^ Galil, Zvi (1981-01-01). "String Matching in Real Time". Journal of the ACM. 28 (1): 134–149. doi:10.1145/322234.322244. ISSN 0004-5411. S2CID 9164969.
  26. ^ Galil, Zvi (1978-04-01). "Palindrome recognition in real time by a multitape turing machine". Journal of Computer and System Sciences. 16 (2): 140–157. doi:10.1016/0022-0000(78)90042-9. ISSN 0022-0000.
  27. ^ Galil, Zvi; Seiferas, Joel (1983-06-01). "Time-space-optimal string matching". Journal of Computer and System Sciences. 26 (3): 280–294. doi:10.1016/0022-0000(83)90002-8. hdl:1802/10578. ISSN 0022-0000.
  28. ^ Breslauer, Dany; Galil, Zvi (1990-12-01). "An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm". SIAM Journal on Computing. 19 (6): 1051–1058. doi:10.1137/0219072. ISSN 0097-5397.
  29. ^ Breslauer, Dany; Galil, Zvi (1992-10-01). "A Lower Bound for Parallel String Matching". SIAM Journal on Computing. 21 (5): 856–862. doi:10.1137/0221050. ISSN 0097-5397.
  30. ^ Crochemore, Maxime; Galil, Zvi; Gasieniec, Leszek; Park, Kunsoo; Rytter, Wojciech (1997-08-01). "Constant-Time Randomized Parallel String Matching". SIAM Journal on Computing. 26 (4): 950–960. doi:10.1137/S009753979528007X. ISSN 0097-5397.
  31. ^ Galil, Zvi; Micali, Silvio; Gabow, Harold (1986-02-01). "An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs". SIAM Journal on Computing. 15 (1): 120–130. doi:10.1137/0215009. ISSN 0097-5397. S2CID 12854446.
  32. ^ Galil, Zvi; Hoffmann, Christoph M.; Luks, Eugene M.; Schnorr, Claus P.; Weber, Andreas (1987-07-01). "An O(n3log n) deterministic and an O(n3) Las Vegs isomorphism test for trivalent graphs". Journal of the ACM. 34 (3): 513–531. doi:10.1145/28869.28870. ISSN 0004-5411. S2CID 18031646.
  33. ^ Gabow, Harold N.; Galil, Zvi; Spencer, Thomas; Tarjan, Robert E. (1986-06-01). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica. 6 (2): 109–122. doi:10.1007/BF02579168. ISSN 1439-6912. S2CID 35618095.
  34. ^ Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon (1997-09-01). "Sparsification—a technique for speeding up dynamic graph algorithms". Journal of the ACM. 44 (5): 669–696. doi:10.1145/265910.265914. ISSN 0004-5411. S2CID 340999.
  35. ^ Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. (1992-07-01). "Sparse dynamic programming I: linear cost functions". Journal of the ACM. 39 (3): 519–545. doi:10.1145/146637.146650. ISSN 0004-5411. S2CID 17060840.
  36. ^ Gabber, Ofer; Galil, Zvi (1981-06-01). "Explicit constructions of linear-sized superconcentrators". Journal of Computer and System Sciences. 22 (3): 407–420. doi:10.1016/0022-0000(81)90040-4. ISSN 0022-0000.
  37. ^ ACM Fellow Award / Zvi Galil
  38. ^ "Dr. Zvi Galil". NAE Members. National Academy of Engineering. Retrieved May 11, 2012.
  39. ^ "Zvi Galil Elected to National Academy of Engineering". Columbia News. Columbia University. Retrieved May 11, 2012.
  40. ^ Academy Elects 225th Class of Fellows and Foreign Honorary Members, American Association for the Advancement of Science, April 26, 2005
  41. ^ "Zvi Galil Award". Columbia College. Retrieved 2019-06-05.
  42. ^ "Quigley, Galil To Receive Great Teacher Awards". Columbia College Today. September 2009. Retrieved 2019-06-05.
  43. ^ Smyth, Pamela. "University of Waterloo to award eight honorary degrees at spring convocation". Waterloo Communications. University of Waterloo. Retrieved May 11, 2012.
  44. ^ Larson, Erik J.; PhD (19 March 2020). "Top Influential Computer Scientists Today". academicinfluence.com. Retrieved 2021-05-05.
  45. ^ "New Endowed Chair Honors Inclusion and Diversity". College of Computing. 2021-06-02. Retrieved 2021-06-09.

Read other articles:

Bunda dari MedjugorjeBunda dari MedjugorjeTempatMedjugorje, Bosnia dan HerzegovinaSaksi mataMirjana DragicevicIvanka IvankovićMarija PavlovićJakov ColoVicka IvankovićIvan DragicevicJenisPenampakan MariaPersetujuan Tahta SuciPersetujuan tertunda oleh Tahta SuciBiaraMedjugorje Bunda dari Medjugorje (juga disebut Ratu Perdamaian) adalah gelar yang diberikan kepada Bunda Maria oleh orang-orang yang meyakini bahwa ia muncul pada 1981 di hadapan enam anak-anak Herzegovina di Medjugorje, Bosnia d...

 

Dewan Perwakilan Rakyat Daerah Kabupaten Belitung TimurDewan Perwakilan RakyatKabupaten Belitung Timur2019-2024JenisJenisUnikameral SejarahSesi baru dimulai25 September 2019PimpinanKetuaFezzi Uktolseja, S.E., M.M. (PDI-P) sejak 8 Oktober 2019 Wakil Ketua IRohalba, S.Pt. (PKS) sejak 8 Oktober 2019 Wakil Ketua IISuladi, S.E. (Gerindra) sejak 8 Oktober 2019 KomposisiAnggota25Partai & kursi  PDI-P (4)   NasDem (3)   Hanura (3)   Demokrat (1)...

 

Painting by Jean-Paul Laurens The HostagesArtistJean-Paul Laurens[1]Year1896[2]Mediumoil on canvasDimensions140 cm × 146 cm (55 in × 57 in)LocationMuseum of Fine Arts of Lyon, Lyon The Hostages is an 1896 oil on canvas painting created by French painter and sculptor Jean-Paul Laurens, the last in a series of historical works by him. He does not give a specific historical setting, although he evokes the Princes in the Tower and Richar...

Football match2015 AFC Champions League FinalEvent2015 AFC Champions League Al-Ahli Guangzhou Evergrande 0 1 on aggregateFirst leg Al-Ahli Guangzhou Evergrande 0 0 Date7 November 2015VenueAl-Rashid Stadium, DubaiAFC Man of the MatchZheng Zhi (Guangzhou Evergrande)[1]RefereeKim Jong-hyeok (South Korea)Attendance9,480WeatherClear and warm25 °C (77 °F)62% humidity[1]Second leg Guangzhou Evergrande Al-Ahli 1 0 Date21 November 2015VenueTianhe Stadium, GuangzhouAFC ...

 

American lawyer and politician (1927–1991) Dean BurchCounselor to the PresidentIn officeMarch 8, 1974 – December 31, 1974PresidentRichard NixonGerald FordPreceded byAnne ArmstrongSucceeded byRobert T. HartmannJohn MarshChairman of the Federal Communications CommissionIn officeOctober 31, 1969 – March 8, 1974PresidentRichard NixonPreceded byRosel H. HydeSucceeded byRichard E. WileyChairman of the Republican National CommitteeIn officeJuly 16, 1964 – April 1, ...

 

2008 2015 Élections cantonales de 2011 en Corse-du-Sud 11 des 22 cantons de la Corse-du-Sud 20 et 27 mars 2011 Type d’élection Élections cantonales Majorité départementale – Jean-Jacques Panunzi Liste UMPDVDNCPRVFeC Sièges obtenus 13  2 Opposition départementale Liste DVGPNCPRG Sièges obtenus 9  2 PCF : 1 siège PS : 16 sièges DVD : 15 sièges UMP : 6 sièges Président du Conseil général Sortant Élu Jean-Jacques Panunzi UMP J...

Historic house in Connecticut, United States United States historic placeJames Dwight Dana HouseU.S. National Register of Historic PlacesU.S. National Historic LandmarkU.S. Historic districtContributing property James Dwight Dana house in 2009Show map of ConnecticutShow map of the United StatesLocation24 Hillhouse Avenue, New Haven, ConnecticutCoordinates41°18′48.24″N 72°55′26.76″W / 41.3134000°N 72.9241000°W / 41.3134000; -72.9241000Built1849ArchitectHenry...

 

Finland at the Games of the XXXII Olympiad in Tokyo Sporting event delegationFinland at the2020 Summer OlympicsIOC codeFINNOCFinnish Olympic CommitteeWebsiteolympiakomitea.fi (in Finnish and Swedish)in Tokyo, JapanJuly 23, 2021 (2021-07-23) – August 8, 2021 (2021-08-08)Competitors45 in 11 sportsFlag bearers (opening)Satu Mäkelä-NummelaAri-Pekka LiukkonenFlag bearer (closing)Mira PotkonenMedalsRanked 85th Gold 0 Silver 0 Bronze 2 Total 2 Su...

 

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (25 марта 2021)Советская МолдавияМолдова Советикэ ...

Gol Terbaik Liga Utama InggrisPremier League Goal of the SeasonEmre Can, pemenang perdanaDiberikan kepadaGol terbaik dalam satu musim Liga Utama InggrisDisponsoriBudweiserNegaraInggrisDipersembahkan olehLiga Utama InggrisDiberikan perdana2017Pemegang gelar saat iniJulio Enciso (gelar ke-1)IkhtisarPenghargaan terbanyakTujuh pemain (masing-masing 1)Paling banyak per timLiverpoolTottenham Hotspur(masing-masing 2)Situs webhttps://www.premierleague.com/awards?at=2&aw=24&se=-1  Gol Ter...

 

French filmmakers and inventors Auguste and Louis LumièreAuguste (left) and LouisResting placeNew Guillotière CemeteryAlma materLa Martiniere LyonOccupationsFilmmakersinventorsAwardsElliott Cresson Medal (1909)Auguste Lumière BornAuguste Marie Louis Nicolas Lumière(1862-10-19)19 October 1862Besançon, FranceDied10 April 1954(1954-04-10) (aged 91)Lyon, France Louis Lumière BornLouis Francis Patrick Jean Lumière(1864-10-05)5 October 1864Besançon, FranceDied6 June 1948(1948-06-0...

 

Location of Schoharie County in New York Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) List of the National Register of Historic Places listings in Schoharie County, New York This is intended to be a complete list of properties and districts listed on the National Register of Historic Places in Schoharie County, New York. The locations of National Register properties and districts (at least for...

2006 compilation album by MinaTi amo...Compilation album by MinaReleased16 June 2006Recordedat PDU studios in LuganoLength67 min : 16 s LabelPDUProducerMassimiliano Pani Ti amo... is a compilation album released in 2006 by the Italian singer Mina.[1] The album contains previously released songs between 1994 and 2005. The cover is inspired by the pop art artist Roy Lichtenstein.[2] Track listing No.TitleWriter(s)Length1.Fragile from Bula Bula (2005)Gennaro Parlato,...

 

ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Раннее христианство Гностическое христианство Вселенские соборы Н...

 

此條目可参照英語維基百科相應條目来扩充。 (2023年12月1日)若您熟悉来源语言和主题,请协助参考外语维基百科扩充条目。请勿直接提交机械翻译,也不要翻译不可靠、低品质内容。依版权协议,译文需在编辑摘要注明来源,或于讨论页顶部标记{{Translated page}}标签。 此條目需要补充更多来源。 (2021年4月4日)请协助補充多方面可靠来源以改善这篇条目,无法查证的内容可能�...

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article may contain unverified or indiscriminate information in embedded lists. Please help clean up the lists by removing items or incorporating them into the text of the article. (May 2013) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced mate...

 

Борис Миколайович Лятошинський Борис Миколайович ЛятошинськийІм'я при народженні Борис Миколайович ЛятошинськийНародився 22 листопада (4 грудня) 1894[4][5]Житомир, Російська імперія[1]Помер 15 квітня 1968(1968-04-15)[1][2][…] (73 роки)Київ, Українська РСР, СРСР[1]...

 

Pour les articles homonymes, voir Vingt-Trois-Mars. Éphémérides Mars 1er 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31         23 février 23 avril Chronologies thématiques Croisades Ferroviaires Sports Disney Anarchisme Catholicisme Abréviations / Voir aussi (° 1852) = né en 1852 († 1885) = mort en 1885 a.s. = calendrier julien n.s. = calendrier grégorien Calendrier Calendrier perpétuel Liste de calendriers Naissances du jou...

Professional didgeridoo player Stephen Kent performing in 2008 Stephen Kent is a professional didgeridoo performer, percussionist, composer and recording artist. He lives in the San Francisco Bay Area. Musical career Forming the band Lights in a Fat City (with percussionist Eddy Sayer & producer/sound engineer Simon Tassano), he made the first contemporary releases of didjeridu music in the northern hemisphere (the landmark LP/CDs Somewhere and Sound Column on These Records, since reissue...

 

從香港海防博物館望向鯉魚門及三家村 三家村避風塘近攝(漁港及避風塘) 三家村(即鯉魚門海鮮街)的酒家 三家村(英語:Sam Ka Tsuen)是位於香港觀塘區東南部鯉魚門的鄉村,有150年歷史,為九龍十三鄉之一[註 1],位於油塘及鯉魚門附近。 歷史 根據當時香港政府1898年後繪製的地圖,鯉魚門一帶的土地由幾個氏族擁有,現今油塘工廠區一帶土地由張氏擁有、現今�...