Lecture Notes in Computer Science

Supported by



IBM Research
IBM Research

Old and New in Stringology

Zvi Galil
Tel Aviv University


Twenty six years ago in a paper titled "Open Problems in Stringology" I listed thirteen open problems in a field I called Stringology. The first part of the talk will revisit the list. Some problems were solved, others were partially solved and some resisted any progress.

The second part of the talk will review some recent results in Stringology, namely algorithms in the streaming model. In this model, the algorithms cannot store the entire input string(s) and can use only very limited space. Surprisingly, efficient algorithms were discovered for a number of string problems.

The talk will conclude with new open problems that are raised by these new results.


Zvi Galil was born in Tel-Aviv, Israel. He earned a BS and MS degrees in Applied Mathematics from Tel Aviv University, both summa cum laude. He then obtained a PhD in Computer Science from Cornell University. After a post-doctorate in IBM's Thomas J. Watson research center, he returned to Israel and joined the faculty of Tel-Aviv University. He served as the chair of the Computer Science department in 1979-1982.

In 1982 he joined the faculty of Columbia University. He served as the chair of the Computer Science Department in 1989-1994 and as dean of The Fu Foundation School of Engineering & Applied Science in 1995-2007. Galil was appointed Julian Clarence Levi Professor of Mathematical Methods and Computer Science in 1987, and Morris and Alma A. Schapiro Dean of Engineering in 1995.

In 2007 Galil returned to Tel Aviv University and served as president. In 2009 he resigned as president and returned to the faculty as a professor of Computer Science. In the summer of 2010 Galil will start serving as dean of the College of Computing at the Georgia Institute of Technology.

Dr. Galil's research areas have been the design and analysis of algorithms, complexity, cryptography and experimental design. In 1983-1987 he served as chairman of ACM SIGACT, the Special Interest Group of Algorithms and Computation Theory. He has written over 200 scientific papers, edited 5 books, and has given more than 150 lectures in 20 countries. Galil has served as editor in chief of two journals and as the chief computer science adviser in the United States to the Oxford University Press. He is a fellow of the ACM and of the American Academy of Arts and Sciences and a member of the National Academy of Engineering. In 2009 the Columbia Society of Graduates awarded him the Great Teacher Award.

Zvi Galil is married to Dr. Bella S. Galil, a marine biologist. They have one son, Yair, a corporate lawyer in New York.