• Home
• Newsletters
• People of ACM
• Zvi Galil

People of ACM - Zvi Galil

May 7, 2024

How did you initially become interested in algorithms and theoretical computer science?

My BS and MS degrees at Tel Aviv University were in Applied Mathematics. I did my MS thesis with Robert Aumann. I was attracted to Computer Science (CS) because it was a very young and open field—even though I had hardly any background in it and there were no computer science departments in Israel at the time. I hoped that my mathematical background would be useful to CS research. As part of an internship with Amir Pnueli at the Weizmann Institute during my sophomore year, I taught one of the first computers in Israel to play a “sheep against wolves” game using Fortran. I even demonstrated this on an Israeli TV program. Later, I audited an Amir Pnueli’s course on Formal Languages. All of these experiences convinced me that I wanted to learn more, so I decided to go for a PhD degree in computer science at Cornell University. At Cornell I asked John Hopcroft to be my advisor, since I was familiar with his book on Formal Languages with Jeffrey Ullman. When Hopcroft asked me what I wanted to do my thesis on, I answered Formal Languages. John then gave me the best professional advice I ever received. He said, “You don’t want to do that. Formal Languages is dead.” John had moved to the area of algorithms, and I took his course and fell in love with the area.

Will you give examples of your research results that were especially impactful?

A. We say that a set A of vertices in a graph is expanded by alpha>0 if the set B that includes all vertices in A and those reachable from them by an edge is larger than A by at least alpha percent. An Expander is a graph for which every not too large set of vertices is expanded by some fixed alpha>0. Sparse Expanders (with number of edges linear in the number of vertices) are important for the design of fast algorithms. There was an open problem to construct sparse expanders. In 1973 G. Margulis, a Fields Medalist, partially solved the problem. He constructed a family of sparse expanders and proved that there is an epsilon>0 such that every not too large subset of vertices was expanded by epsilon, but he could not compute the epsilon. Without knowing the value of epsilon, one cannot use his expanders to speed up algorithms. In 1981, with Ofer Gabber, we co-authored the paper “Explicit Constructions of Linear-Sized Superconcentrators,” which solved the problem by constructing a family of sparse expanders with a known value of epsilon.

B. My algorithms work was mostly in two areas—string algorithms (aka: stringology) and graph algorithms. The most basic problem in stringology is string matching (SM). I designed the fastest possible algorithms for SM and for palindrome recognition. They were real time on the most primitive model of computation—the Turing machine. For this algorithm I introduced an algorithmic technique named “the predictability condition.” I and others have used the predictability condition to improve many other string algorithms.

C. Together with students we also invented a technique called sparsification for speeding up dynamic graph algorithms . The time bound that initially depended on m, the number of edges in the graph, now depends on n, the number of vertices. We and others used this technique to speed up many dynamic graph algorithms.;

What were your key accomplishments as the Dean of the Columbia School of Engineering?

From a financial perspective, we secured a large gift to name the school the Fu Foundation School of Engineering and Applied Science. Another important achievement was the creation of the Department of Biomedical Engineering (BME) in collaboration with Columbia’s Medical School. BME is now ranked in the top ten by US News and World report. Great credit goes to Michael Crow (then Vice Provost now President of Arizona State University) who provided the funds and Dr. Van Mao, who led the initiative.

Other achievements: In 1995, my first year as Dean, Columbia engineering was ranked 31 ^st by US News and World Report; in 2007, my last, it was ranked 19^th.

When I became dean, the school had a deficit and accumulated debt. I healed the finances of the school, paid the debt, and created a surplus even though we kept growing the school especially in BME and CS. In the 12 years the faculty grew from 92 to 155. By the time I left Columbia, the surplus grew to $38M. It helped my successors to grow the faculty even further, and they now number about 250.

The school’s distance learning program also grew considerably during my tenure. Its name is Columbia Video Network (CVN) because it was started using video tapes that were mailed to the students. In the late 90’s it switched to the Internet. The revenues of CVN were a major factor in the school’s financial turnaround.

While you were serving as Dean of Georgia Tech’s College of Computing, you initiated an Online Master's of Science Degree in Computer Science (OMSCS). When the program began in 2014, Georgia Tech enrolled 380 students in five courses. This Spring, the program is enrolling 13,600 students in more than 50 courses. OMSCS has graduated over 11,000 students. Why has the Online Master’s in Computer Science at Georgia Tech been so successful? What will the landscape for online learning in computer science at universities look like ten years from now?

OMSCS has been successful due to several reasons:

1. Price: The total price of the MS degree is under $7,000, about six times cheaper than at state universities and 10 times cheaper than in private universities.

2. Quality: We decided to make the program equivalent to the on-campus program with identical material, homework, and projects. The diploma students earn doesn’t mention that this is an online degree.

3. Flexibility: most students have a full-time job and take one course a term, while a smaller group might take two or three courses per semester. Most of our students finish in about 3 years.

4. Great partners: Udacity, which provided the platform, and AT&T, which provided $4M. These partnerships also helped us attract many of our initial students.

5. A total departure from the norm of extreme selectivity in admissions (at times in the single digits) and accepting all students we believe can complete the program. Typically, we accept approximately 85% of the applicants to the online program, whereas we accept about 21% of the applicants to the on-campus program.

The faculty of Georgia Tech’s College of Computing deserve most of the credit for the planning and the execution of OMSCS.

OMSCS was the first of its kind. It is MOOC-based, so it uses the MOOC platform and the courses have MOOC structure, but are not MOOCs. As such, they are superior to the usual recorded courses that have been used by online teaching.

Over 30 universities have followed in OMSCS’ footsteps. There are now more than 70 MOOC-based programs (not only in CS) that are providing quality education at a much more affordable cost. None, however, are as affordable as OMSCS. Georgia Tech added two such programs.

As for the future, Yogi Berra famously said, “It’s tough to make predictions, especially about the future.” I can only describe my vison and express my hope that it will be fulfilled. It all depends on the right leadership. It is undeniable that our universities have a huge problem of access with untenable tuition levels that have led to $1.7 trillion student debt. Even for those willing to pay, access is far from certain due to constraints on admissions, and many have to settle for second-rate universities. In a recent article in The Chronicle of Higher Education titled, “The Public is Giving Up on Higher Ed,” Michael Smith suggested that universities must change and will change. I envision a system in which online teaching will be far more pervasive in college education. Students will be able to complete all or part of their BA degree online, and benefit from lower tuition fees due to the online portion.

At Georgia Tech, we offered an online course in “Introduction to Computing using Python” in 2017 to our on-campus college students and added two more in 2019. The students rate the online courses highly, in some cases higher than the equivalent on-campus courses. They value the flexibility online courses offer. The tuition is the same, since in-college students pay by the semester whereas OMSCS students pay by the course. In my vision for the future, in-college students will also pay by the course, resulting in much lower costs. Universities will not be harmed financially. They will fill out the dorms and max out their in-person capacity and all the online tuition will be extra. As Michael Smith predicts, the solution is to “go digital.”

Many universities in the US are facing an explosion in CS in admissions and in enrollments. They try to solve it by hiring more faculty, but the growth in faculty size lags behind the increase in enrollments. In some places the number of CS majors per faculty has almost doubled. Going online is clearly the solution. It will also allow the universities to admit many more students that in many cases are as qualified as the ones they admit now, increasing growth in human capital (a benefit not just to the university but to the United States and—I would argue—global society) without sacrificing quality.