Yefim Dinitz talk at Shimon Even's Party (2003)

Following is a transcript of Yefim's speech at Shimon's retiring party (Nov. 2003).
Shimon had a very important influence on my life in the scientific community. I'd like to tell you about three major impacts he had on my professional life.

The first impact dates back to 1973, and was really crucial. You may ask how a person in Israel could influence somebody in the past USSR, when there was no possibility neither to go out from the USSR, nor to publish at or even communicate with the West? In order to clear this question up, let us begin from even more "ancient" period, with the early history of computing and algorithms in the USSR.

The following anecdote sheds some light on how things were done in the USSR. Shortly after the wall fell in 1990, an American and a Russian who had both worked on development of weapons meet. The American asks: "When you developed the Bomb, how were you able to perform such an enormous amount of computing with your weak computers?". The Russian responses: "We used better algorithms."

This was really so. Russia had an old tradition of excellence in Mathematics. Besides, there was a usual Soviet way of attacking hard problems by combining authority pressure and peoples' enthusiasm. When Stalin decided to develop the Bomb, many bright mathematicians, in particular, Izrail Gelfand and my first Math teacher, Alexander Kronrod, put aside their mathematical studies and "dug" deeply in the novel computing area. They have collected and created teams of talented people, and ... succeeded. The teams continued to grow and work on theory and practice of computing.

The supervisor of my Master thesis was George Adelson-Velsky (nicknamed Gera), one of the fathers of Computer Science. Among the other students in his group were M. Kronrod (one of the future "Four Russians"), A. Karzanov (the future author of the O(n^3) network flow algorithm), and other talented school pupils of A. Kronrod. Then, in 1968, the Bomb project was over long ago. As well, the work on the chess program Kaissa, created by members of A. Kronrod's team, under the guidance of Adelson-Velsky, was finished; Kaissa won the first world championship in 1969. The new passion of Gera became discrete algorithms, which he felt had a great future.

The fundamental contribution of Adelson-Velsky to Computer Science was AVL-trees. He (AV) and Eugene Landis (L) published a paper about AVL-trees in early 60's, consisting of just a few pages. Besides solving an important problem, it presented a bright approach to data structure maintenance. While this approach became standard in the USSR, it was still not known in the West. No reaction followed their publication during a couple of years, until another paper, 15 pages long, was published by a researcher, which understood how AVL-trees work and explained this to the Western community, in its language. Since then, AVL-trees and the entire data structure maintenance approach became a corner-stone of Computer Science.

We, the students of Gera, absorbed the whole paradigm of the Soviet computing school from his lectures. The eagerness to develop economical algorithms, based on the deep investigation of the problem and on using data structure maintenance and amortized running time analysis as necessary components, constituted this paradigm. All this became quite natural for us in 1968, 18 years before the first publication in the West on amortized analysis, by R. Tarjan. Hence, it was not surprising that my network flow algorithm, invented in January 1969, improved the running time of the Ford-Fulkerson algorithm based on using and maintaining a layered network data structure, and on a delicate amortized analysis of the running time.

Back then, such an approach was not surprising for us in the USSR, but was very unusual in the West. Professor Shimon Even and his talented Ph.D. student Alon Itai (which is present now as the host, the CS Faculty Dean) were very curious and intrigued by the two new network flow algorithms: mine and of Alexander Karzanov, in 1973. It was very difficult for them to decipher these two 4-page papers (such was the page restriction of the prestigious journal Doklady). However, as you the friends of Shimon are aware, Shimon was not used to give up. After about three days long effort, Shimon and Alon understood both papers, except for the layered network maintenance issue. The gap was fixed by using the Karzanov's concept of blocking flow (which was indirect, in my paper), and a beautiful way of using DFS for finding each augmenting path.

As all of you know, Shimon is an excellent lecturer. During the next couple of years, Shimon presented Dinic's algorithm in lectures he gave in many leading research universities of the West. The result was important, the idea was fresh, the algorithm was very nice, combining both BFS for constructing the layered network and DFS for operating it. The success was great, and Dinic's algorithm achieved its place in annals of Computer Science community. Almost nobody was aware that the algorithm, taught in many universities since then, is not the original version, and that a part of its beauty--combining BFS and DFS--was due to a contribution of Shimon and Alon. But this is so, and I declare this today.

The original algorithm published in a Soviet journal was not understood by others in the West, as well. Shimon told me once that, in particular, he has learned that Bob Tarjan had tried to reconstruct the algorithm from my paper, but was not successful. After more than 20 years, I finally explained to Shimon the original version of my paper. After that, Shimon though continued to teach his version of my algorithm but used to add a remark like: "My friend Yefim Dinitz invented this algorithm at the age of 19. In his paper on this algorithm, he was first to publish an amortized running time analysis as early as 1970!".

Now, you can see that the wide acquaintance with my algorithm in the West was due to Shimon. Therefore, when I arrived in Israel, many doors were open to me. However, not all of them: The academy was cautious. During my last 15 years in Russia I worked in the industry, and have published just a little. One can easily understand the difficulty. The Technion was not eager to suggest a tenure track position to me, as Shimon suggested.

I'd like to make a philosophical observation, now. No system is able to maintain itself without a certain conservatism, without rules taking care of its stability. One of the methods is counting papers of a candidate before offering a position. Another criteria is teaching experience - mine was fairly small. Such rules are very hard to overcome, and this must be so. On the other side, there is a place for miracles in our life, and there are people that bring about such miracles. This essential aspect of life is crucial, among other things, for innovations.

In my case, such a person was Shimon. It was already known that he is able to do things that seem to be impossible. Also in my case, the miracle occurred. Shimon has succeeded: I became an Associate professor at the Technion, a really important achievement, in my novice state. My friend, a faculty at the CS Dept. of the Technion, expressed the fight at the Technion by the metaphor: "Shimon threw chairs." I can imagine something like this, can you?

Shimon's third influence was that he taught me to teach. Once more, you may be surprised how this could happen: I was neither a Shimon's Ph.D. student, as many of you, nor ever registered to his course. However, I really listened to the most of his Graph Algorithms course. When? Why? What for?

When I began to teach at the Technion, I knew that I am able to interest people when I present a subject close to me. However, I could do this only without time pressure. However, as all of you are aware, time is a scarce resource in university courses. As long as I was teaching a compulsory course in parallel to Orna Grumberg, my teaching went on not so bad. However, after a couple of years, there was an external CS Dean who assigned me to teach Graph Algorithms (a compulsory course) not only for the first time but also alone. This became a catastrophe, though the material was not new, for me, of course. Let me explain why.

As a result of my mathematical education, I always felt obliged to clear up all the details in a proof. Otherwise, it would not be a proof. Such proofs are sometimes even interesting, but I felt that it is the ONLY way to present proofs. Most of you know well that algorithm correctness proofs are not similar to Math Analysis lemmas. They usually have beautiful basic ideas, but sometimes their full proofs are heavy. In my course, I tried to teach students to see all the details, and to process them appropriately. I felt that a great aim would be achieved, by this, for the listeners. Poor students ... . But I felt obliged! Let us stop this particular story.

After this bad experience, I decided to listen to Shimon giving the same course. I had in mind a few delicate points which I was very eager to see in Shimon's presentation. Usually, when presenting issues related to these points, Shimon simply went his other way, and it was difficult to judge. However, once I had in mind a pure gap, which was really hard to fill and impossible to avoid. Imagine, I sit in the class, and feel that the moment is approaching. Closer, very close. But there is almost no time for it, up to the lecture end, what is it? Shimon comes to the critical point, and ... he is already explaining the next detail. Shimon not only did not give an explanation, he even did not mention the difficulty. HIS PROOF WAS NOT FULL!

I could hardly imagine such a way of presentation. I walked around with a storm in my soul for a couple of days. Eventually, I've realized that ... Shimon is right. We have a bounded time in our courses. Our courses contain important results and ideas, and they are not easy. We must let students absorb what they are able to absorb, and give them the feeling that they understand. By hiding some gaps, we will achieve these aims, and this is for the good of our students. In fact, just a few of our students will become theoreticians, and those would have time to learn how to give a full algorithm correctness proof during their grad studies.

Since then, I tried to follow Shimon's way of dealing with difficult proofs. I feel that this was very useful, even crucial, for my teaching ability.

To be honest, I did not follow all of Shimon's advises. One of them was not to continue working on graph connectivity structures. Shimon knew a few people who had started their careers with strong results in this field, presenting their results in conferences, have published almost no journal papers, and eventually stopped publishing. I continued in this area as my main one. One particular result that I am proud of is a 56 pages long paper in SIAM Journal of Computing, in this area. Another result is that the Technion decided not to give me a permanent position (that paper was published after this decision).

However, I am in academy since then, now in the Ben-Gurion University, and feel that this is my place. Thanks to Shimon, for his many efforts in helping me.

Summarizing, I'd like to stress one of my above points. Our life would be much more boring without miracles. Let us be happy that they occur, sometimes, and be grateful to persons who bring them about, and, in particular, to Shimon.

As you may be aware, after leaving his position at the Technion, Shimon became a Vice-President of the Tel-Aviv Academic College. Let us wish him to continue to be strong as usually, and have a fruitful continuation of his academy activity.

Reproduced by Yefim [August 2004].


Back to Oded Goldreich's homepage.