In memory of Shimon Even (1935-2004)

[See short bio]

Shimon Even was born in Israel on June 15th, 1935. He died on May 1st, 2004.
In addition to his pioneering research contributions (most notably to Graph Algorithms and Cryptography), Shimon is known for having been a highly influential educator. He played a major role in establishing computer science education in Israel (e.g., at the Weizmann Institute and the Technion). He served as a source of professional inspiration and as a role model for generations of young students and researchers. Two notable avenues of influence were his PhD students (see see list below) and his books Algorithmic Combinatorics (Macmillan, 1973) and Graph Algorithms (Computer Science Press, 1979).

This page contains:

Eulogy by Guy Even (read during the funeral)

We always admired Abba. This is obvious. During the past months, since you became ill, we have discovered and rediscovered how much we love you. Imma did not leave you for a moment. For over a month, she slept in the hospital on the floor beside you. All we wanted was that you would feel better and recover. We all spent long hours in the hospital next to you, trying to ease your suffering and trying to understand the twists of the medical world. The phone never stopped ringing with calls from friends inquiring about your health. You preferred detachment. You were not a man of words, and while you were sick you could not do much.

When you fell sick, the first thought that crossed our minds was "what about the grandchildren"? When will they have a chance to enjoy you? To learn from you? What a terrible loss! What a waste! You were an incredible teacher never relying on jugglery. You were simply tailored for the job: crystal clear thought, explicit style, perfect handwriting, uniform pace, you explained everything, without gaps. A combination of modesty and perfectionism.

Whenever your works were mentioned in talks in the university and in conferences, I became full of pride. I knew the stories behind your works. You always loved to tell and share. From you I learned that even scientific research is about people and not dry Math as many tend to believe. The thing I love most to do is to cite your works in my talks. The sentence: "in the paper of my father and his colleagues this and this was shown" always rolls in my tongue with infinite pride.

Together with Imma you built a model family. As you saw, we recruited ourselves together to help you. The pain and anguish did not spread us apart, but unified us. From you we learned to bear a firm opinion but also to respect different opinions. Always distinguish between the opinion and the bearer of the opinion. I recall the last visit to Prof. Catane before Pesach. Five family members stuffed in the doctor's office. We exhausted the doctor with an endless sequence of questions, and Abba was glad. He was satisfied to see that we are all interested, that we all care, that we formulate clear questions, in his words: "intelligent questions". You were glad and satisfied after this visit because you knew that you had succeeded. Succeeded in building a united family in which everybody knows how to work according to your system: with logic, thoroughly, and with care.

I took three courses that you had taught in the Technion. I always knew that you gave us all a starting point that made things so much easier for us. We were built from you and you spared us the need to have to start from the beginning. Now this base is gone, and it is so hard to imagine how we will do without you.

We shared many jokes and stories about luck. The luck that accompanied the family has abandoned you in the past months. And without luck, all the good deeds are futile. But during the last weeks, luck has not only abandoned you, it betrayed you, with cruelty, ruthlessly, a total crushing.

I have nothing to say Quadish about. I feel that a prayer of glory is fake in this day. You taught us integrity and first and foremost internal integrity - so that we will always be faithful to ourselves and to our principles. Ceremonies do not coincide well with modesty and integrity. When I asked you about the Bar-Mizva ceremony, you said that you did not gain from it. You made things easier for me because I did not want it in the first place. From you I learned that attention is given year-round and then ceremonies are not needed. It is a pity that we will not be able to receive attention from you. It is even worse that we will not be able to give you attention anymore.

Abba, we miss you and promise to remember you and what you have taught us.

The Family

Eulogy by Arny Rosenberg (to appear in Theory of Computing Systems)

On May 1, 2004, the world of theoretical computer science suffered a stunning loss: Shimon Even passed away. Few computer scientists have had such a long, sustained, and influential career as Shimon. As an educator, he played a major role in establishing computer science education in Israel, at (at least) two major institutions: the Weizmann Institute and the Technion. As a researcher, he was a pioneer in the areas of graph algorithms and cryptography; he worked also in such diverse areas as switching and automata theory, coding theory, combinatorial algorithms, complexity theory, and distributed computing. In all of these areas, Shimon produced high-quality, innovative research for more than four decades. As a mentor to aspiring researchers, he was almost without peer, producing numerous doctoral students who went on to have their own successful research careers. (In this last regard, had Shimon stayed on at Harvard in the mid-1960's, I would have been his first doctoral student.)

In a sense, Shimon was the purest of pure theoreticians, following his nose toward research problems that were "the right" ones at the moment, not the faddish ones. Shimon's standards were impeccable, to the point where he would balk at employing any result whose proof he had not mastered himself. Shimon's integrity was unimpeachable: he would go to great lengths to defend any principle he believed in.

With all of the above, Shimon was always a friendly, approachable person. Few who interacted with him escaped without hearing at least a few of his seemingly endless supply of stories.

My personal relationship with Shimon began in 1962, his last year of grad school and my first, and it lasted until the very end. My personal sense of loss is immense. Indeed, for all of us whose lives intersected his, Shimon's memory remains a vivid, lasting inspiration.

Our field has truly lost one of its role models.

[May 2, 2004]

Eulogy by Oded Goldreich

Shimon had a tremendous influence on my life. Needless to say, Shimon leads the handful of researchers that has most influenced my professional life. But he also fits in the set of dozen people (including my parents...) that have most influenced my life at large.

It is already more than twenty years since I have graduated, but I still identify myself firstly as his student. For example, a few months ago, after a talk I gave, some guy came to me with a question. I started my answer by saying "my adviser, Shimon Even, would say...." (The specific quote, which is one of my favorites, is when a problem looks natural to me, I don't need a specific application.) In general, at times I hear myself expressing an opinion, and only later do I realize that it is either actually Shimon's opinion or is "just" strongly influenced by his views and attitudes, which I have mostly adopted. Needless to say, Shimon did not force his opinions on me. It is just that his opinions and attitudes were so appealing and were expressed or manifested so compellingly, that one would need a very good reason not to adopt them.

As opinionated and "full of attitudes" as Shimon was, few people are so accepting of The Other and the different. He might have strongly disagree with you and still (as long as your opinion is legitimate) you would clearly sense his deep respect of your autonomy as a human being. Unfortunately, this can be said of very few people...

I feel fortunate to be among the ones who's meeting with Shimon has left a life-long mark in their personality and have his image constantly present in their soul. It is his rich image that comforts me at this sad time.

[May 2, 2004]
[A less personal eulogy to Shimon Even will appear in the proceedings of PODC04.]

Eulogy by Nissim Francez

Back in 1969, Shimon, together with Amir Pnueli, interviewed me for admittance to the graduate program in Computer Science, just established in the Weizmann institute. Years later, I asked Shimon what convinced him to admit me, in spite of never having approached programming before, and he said "well, you knew what finite automata were ..." This was Shimon, the one that looked for the underlying science even where engineering was supposed to be the name of the game.

Not being familiar with Shimon's way of grading examinations, I was sure I am about to leave this intellectual paradise, having exited the Algorithms exam with what looked as a grade of 17 (out of 100). Fortunately, his grading system converted it to 85; even more fortunately, I succeeded well in Amir's courses, and stayed to complete my Ph.D with Amir.

It was Shimon again who brought me to the Technion, after two years of postdoc abroad. Since then, we became colleagues. Over the years, we had many arguments on scientific issues (not to speak about political issues ...), but I knew he can be trusted to accept criticism or opposition and not hold it against me when deciding on tenure on promotion, for example. Of course, sharing neighboring offices, we had also a lot of fruitful discussions. His advice was always appreciated by me.

Clearly, Shimon was a source of scientific inspiration to me, even though I drifted away from Algorithms, Complexity theory and the like. He served as an inspiration source for the whole department, being the senior scientist in it, shaping it and highly influencing its development.

For many years, for me Shimon was the department. I miss him.

[May 5, 2004]

Book of Condolences

Yefim Dinitz (see tribute), Shlomi Fish (see story), Nissim Francez (see eulogy), Oded Goldreich (see eulogy and story), Sheila Greibach (see story), Gili Granot, Amir Herzberg (see story), Gene Itkis (former post-doc), Shay Kutten (see message), Gavriela Lev (see message), Leonid Levin, Rafail Ostrovsky (see message), Wolfgang Paul (see some thoughts), Erez Petrank, Ron Pinter (see message), Amir Pnueli (see message), Yuval Rabani, Tal Rabin (see message), Sergio Rajsbaum (see story), Arny Rosenberg (see eulogy), Alan Selman (see story), Yonatan Stern (see message), Boaz and Tami Tamir (see story), Uzi Vishkin (see message), Avi Wigderson, Yacov Yacobi (see story)

Memorial Book

Message by Ron Pinter

On May 4th the Annual Rothschild Lecture was delivered by Andy Yao at Haifa University. Before the lecture, Alon Itai (one of Shimon's first PhD students and the current Dean of the CS Dept at the Techion) said a few words about Shimon. In addition, Marty Golumbic (who presided over the event), Noga Alon (who introduced Andy), and Andy himself, expressed their own grief, followed by a moment of silence by the audience.

Message by Amir Pnueli

I think it is important to mention at this point that, in addition to all the other multiple tributes and praises, Shimon was also responsible for starting the Computer Science teaching program at the Weizmann Institute and being its head and major inspiration for the seminal period of its inception.

A Story by Sheila Greibach

I still have happy memories of the long ago time as a fellow grad student with Shimon (we received the Phd in the same year) in the TA bullpen at Harvard. Since I didn't rate a desk, Shimon was kind enough to give me storage space in his and help liberate a typing table for me and make me feel welcome though the only woman there.

I still remember the games of give-away chess that helped relieve grad student stress. Shimon helped me to my first published theorem (the undecidability of ambiguity for minimal linear grammars) by knocking down my first "proof" of decidability - then I went back to my apartment, stayed up all night, and came up with the undecidability proof which could withstand the Even test!

Later, I had the honor of co-authoring a paper with him (with the late Ron Book and G Ott).

The First Time I Met Shimon [by Sergio Rajsbaum]

The first time I met Shimon personally was around October 1987. I went to talk with him when I was a Masters student at the Technion looking for a thesis subject. I was not aware of the tremendous prestige and strong image he had at the Technion; people used to think he advised only "geniuses" (and at the Technion people understand through examples of world class famous leaders that this word has a *very* strong meaning), and many even feared him. Simply, I knew he was probably the best teacher of the Department of Computer Science, that he had written a classic textbook on Graph Algorithms, and that I liked his research interests. So very innocently I knocked on his door, and said "hi" with a smile. He welcomed me warmly, also with a smile, and for a long time told me some of his wonderful stories about famous computer scientists. He was interested to know I had recently arrived to Israel from Mexico, and told me some more stories about the old days of the country's history; he loved Israel and always wanted me to stay there for good. He told me that I had to choose between one of his two current interests: Crypto and Distributed Computing. I chose the later, heard some more funny stories about his former student Baruch Awerbuch, and I left the room motivated and eager to start reading Baruch's paper he suggested to present him the following week ("Complexity of network synchronization"). For a young masters student this meeting was an unforgettable experience.

Later on, I was getting admiration comments from students and even secretaries- "wow, he accepted you as a student?!" and so on. When I switched to continue working on the same subject with him towards a PhD (at the Technion there is a "direct path" option to do this switch), still somewhat innocently, I literally became the "hero" of some of these people (and realized how far away from looking like a "genius" I looked). When I first met him I had no clue that this was his image, and it surprised people to learn that he knew nothing about me, except that I had taken his Crypto course and not excelled, and yet received me so warmly. I feel my friendship with him started that very first meeting. I am very grateful to Shimon; he is one of the people that have most influenced my life personally and professionally. It is due to his views and attitudes about science, and through his encouragement and trust that I took an academic research carrier.

Sergio Rajsbaum
Mexico City, UNAM
May 10, 2004

Some thoughts and a story [by Oded Goldreich]

Sergio's story illustrates many of the characteristics of Shimon, which people close to him take for granted but others may totally miss. In particular, it is a pity that people felt timid to approach him, but this was certainly not his fault; it was not his fault that he was so impressive. Like a Greek God, not perfect and yet immense.

Sergio's story made me go back to my very first memories of Shimon. The first are from his legendary Graph Algorithms class. I vividly recall my admiration to his style of presenting material; always focusing on the key ideas and on the underlying intuition. I was even more amazed by his never-failing ability to "hit the point" every time he answered our questions (i.e., he would always understand what is actually underlying our confusion or doubt and respond to it). He seemed to me the personification of wisdom, indeed god-like. Needless to say, the thought of being his student had never crossed my mind.

Half a year later, in the summer vacation after my 2nd undergraduate year, I was traveling in Europe. I was in London, it was almost 11PM, and the last Tube was about to leave the center of the city. I ran through the entire station and entered the wagon with the doors slamming behind me. I almost fell on a distinguish Lord who was sitting across the door. After a moment, I told myself "strange, this majestic Lord looks like Professor Even" and then we recognized each other. It turned out that we were heading to the same station, and then to the same hotel. So Shimon and Tamar invited me to their room for a midnight cup of tea. There was a nice conversation, but this was not the beginning of a wonderful friendship. He was very friendly and I did notice this fact, but this did not make me feel comfortable with him. How could I have been comfortable with somebody I viewed as a Greek God.

Our ways crossed again only a year later. I was selected to be his TA in that legendary course, and somehow I became his graduate student. One thing just led to another, or maybe it was only my perception and he had it all planned. In any case, in spite of all his efforts, I could never rid myself from the feeling that I was dealing with a (Greek) God. Throughout all the years that followed, I loved him and I knew he loved me, but I had to force myself to call him "Shimon" -- even calling his attention (without calling him by any name) felt too daring.

This is my story. It probably sound weird and says more about me than about him. But still, I believe that it explains the big paradox of how come that a warm and open person like Shimon may induce such "fear" (where by "fear" I mean the Hebrew word used in "fear of god", a term that is a hybrid of "fear" and "deep respect" and "love").

An anonymous story

It was in Berkeley, probably in the summer of 1980. I saw Shimon Even walking on the edge of the sidewalk. He was concentrated on keeping his balance on the edge and was smiling to himself. I thought to myself: I like this guy!

Message by Uzi Vishkin

I have written the attached note for Shimon Even's retirement party last year. I will miss him very much.
Dear Shimon,

Here is my story on how your inspiration actually made a significant difference in my life.

As an 11th grader high-school student, I took a pre-combinatorial-algorithmics class with about 20 others high schools students from the center region of Israel with you. The course met once a week at the Weizmann Institute.

I later proceeded to get my BSc and MSc in Math from the Hebrew University which followed by military service and then doctoral studies at the Technion in Computer Science.

Your influence in that early course was pivotal for my decision to pursue a computer science degree in general and at the Technion, in particular.

I distinctly remember how towards the middle of a PDE graduate class at the Hebrew University I raised my hand and asked the Math professor when we will start solving equations as opposed to just proving theorems on the existence of solutions and their uniqueness. He immediately looked down on me and responded without hesitation: engineers solve, mathematician don't!

As I reflected later on this answer, which looked to me very significant then since I was told by everybody what a big name this professor had, I remembered that 4-5 years earlier the first person who taught me that not only solutions but even algorithms are Kosher was you. This ended up guiding me to chose Computer Science and go to the Technion.

I was honored to become in 1981 one of your first academic grandchildren, as Yossi Shiloach was my doctoral advisor, and later produce one of your first academic grandchildren in 1986 (Gadi Landau, followed by Baruch Schieber, Omer Berkman, Yossi Matias, and Cenk Sahinalp), and rely on them to produce yet another generation.

I am deeply indebted to you for the difference you have made in my life.

Uzi Vishkin

Message by Rafail Ostrovsky

Shimon Even made a strong influence on my scientific life and my approach and love of science. Every time I visited Israel, I would meet with Shimon and be warmly greeted and hear a kaleidoscope of wonderful stories about not just science, but the personalities involved, always told with great love for people, for science and for life is general. One example comes to mind especially vividly: Shimon told me how, many years ago, he was lecturing in Italy on algorithms and discovered a young Italian student in his class who asked all the right questions and was amazingly fast. Shimon told me how he called Manuel Blum and urged him to accept this brilliant young student into Berkeley Ph.D. program. That young student-- it turned out-- is my own Ph.D. advisor - Silvio Micali. In recent years Shimon encouraged me to move to academia, as always with a story how he worked in industry and what happened, and was delighted to hear about my recent move. We lost not only a great scientist but a wonderful, funny, genuine person, and I lost a friend and a mentor.

A Story by Alan Selman

The first time I interacted with Shimon Even was in December of 1980 when I wrote to him about some reports that he and Yacov Yacobi had written. I had some technical questions and comments. Also, I asked whether I might be able to spend a sabbatical year at the Technion. Shimon wrote back that "we will be happy to have you here," and within two months time, somehow, had arranged for a Fulbright award to be available to support the stay for my family and me. I never ceased to be astonished by this arrangement. We spent a wonderful sabbatical year, which was not only enlightening and productive for me, but was a great experience for my family as well. Shimon was a great host, great help, and great friend during our stay. Our research discussions were a joy, because Shimon had amazing intuition about problems and a keen sense about what are the interesting questions. We remained friends ever since. Although our research paths diverged and we never worked together again, we corresponded regularly. Over the years Shimon was my source for information about life and current events in Israel.

A Story by Amir Herzberg

While all my undergrad and grad studies were in the Technion (EE/CS), I was not lucky to learn under Shimon (which, Oded probably says, explains some things). However, Shimon also had a major influence on my professional development, in several ways. I'll mention only the most critical of them, that began while I was working on my MSc thesis, which dealt with cryptographic protocols. It began when I found some attacks on his design of electronic wallet (with Oded and Yacov). Shlomit Pinter, my advisor, was a bit hesitant about these claims, and suggested I show them to Shimon. I must have been trembling when approaching him on this matter, but Shimon surprised me - he was really excited, interested and happy, although it turns out he was aware already of these problems and had solutions similar to mine; he also encouraged me to complete the work at least for the thesis (which I did).

With all this encouragement, I was happy to hear Shimon will be one of my MSc thesis readers. I was therefore quite disappointed to hear, indirectly, later, that he was not very excited about it. I was further disappointed that he didn't tell me. At that point, considering Shimon as highly as I did, I was considering giving up on research. But I decided that before I give up, I must ask him directly what he thinks of my potential as a researcher. Trembling even more than on my first visit, I came to his office. And again Shimon turned the visit into a wonderful surprise. Yes, he was not excited about the thesis. But he still thinks I can be a good researcher - I just need much more demanding coaching (while he didn't say so, I am quite sure he was really annoyed at some "theorems" I gave - until that point, I didn't really take any theory classes, so you can guess how that looked). He then went on and suggested maybe I should talk with Oded, who just returned to the Technion. I certainly heard Oded is coming, but on my own I certainly wouldn't dream of approaching him - with my lack of knowledge of theory of computation... I also suspect Shimon encouraged Oded to do his best to turn me from a hacker/engineer into a computer science researcher - I'm not sure how successful this attempt was, but it was definitely an experience...

Comment by Oded: Shimon had great respect for good engineering, and it would never have occurred to him to "convert" an engineer into a theoretical researcher. I shared (and share) his attitude. What we saw was a person with superb engineering skills that was interested in pursuing theoretical research. Such people are rare and we definitely wanted to assist them.

Message by Yonatan Stern

I was shocked to hear today from a Haim Gottesman that Prof. Shimon Even died two weeks ago. He was my Masters degree advisor at the Technion in 1979-1981. I took several of his courses in undergrad and fell in love with the subject of algorithms and developed tremendous respect to Shimon himself. I was grateful when he agreed to become my advisor. He was an inspiring teacher and a wonderful advisor, always open to my ideas yet quick to point out weaknesses and incompleteness in my arguments. He influenced my career in many ways and I stayed in touch with him for several years after graduation while pursuing a career in industry. Even though I was not in touch with Shimon for many years, the news of his death shocked me and I feel that I lost a mentor and a friend.

Yonatan Stern, CEO
Eliyon Technologies Corp.
Cambridge MA

Some Thoughts by Wolfgang Paul

A great scientist with a great sense of humor has died. We knew he was mortal. We feel a sense of loss, even though his death does not affect our daily life at all. Is the loss real or are we just being sentimental?

The following experiment was invented by psychologists: you ask a person to draw a map of ALL streets, paths, places and rooms they know. What you get is the persons internal spatial model of the world. It usually is amazingly small (except for taxi drivers). All our memories and all our expectations live there. This model is the sum of the life we lived so far. It is very real; the so-called reality is just input for its construction.

And then, by an immaterial string of letters transmitted by electronic mail, we learn that we must adjust the model, make it smaller, make it...less rich.

Shimon does not live there any more. I am not as rich as I used to be.

A Story by Boaz and Tami Tamir

For us Shimon was a combination of Guy's father and a great lecturer/researcher, and we were able to enjoy both worlds. We remember one visit at Guy's apartment in Ramat-aviv a few years ago. Shimon and Tamar were also there. Tomer (Guy and Daria's son) tried to explain the rules of the game 'Bul-Pgia' (master-mind) to our son Eran, they were about 6 years old then. Shimon joined them and we enjoyed every minute watching the private lesson our son is getting from 'Professor Even', a real lesson of cryptography basics.

Message to Guy by Shay Kutten

I guess I should have been ready for these bad news, but I was still shocked. Your father was the best lecturer I have ever heard. He managed to transfer his love for the profession to his students, including to me, and graph theory is still one of my favorites, to a large degree thanks to him. I thought he was a very charismatic person to whom my alma mater was and still is connected in my mind. I deeply feel his departure. I also feel pain I could not visit you on these sad days. I hope you know my thoughts are still there.

A Story by Yacov Yacobi

I met Shimon in the mid 70s and was lucky, happy and proud when he agreed to become my D.Sc. mentor. We usually met once a week and I fondly remember those meetings as very challenging and full of fun (Yardena, Shimon's secretary, said that she could always tell when I was inside by the mutual bursts of laughter). Shimon introduced me to Complexity Theory, and when he first drew on the board "the map of the world as we know it" (= P, NP, etc.) I was fascinated by the beauty and far-reaching power of this theory.

Shimon's wisdom, enthusiasm, appreciation, and humor were major driving forces in my life in those remote bright years.

A Message by Gavriela Lev

I felt that Shimon was always there, like a rock, with good advices for a former student. The rock fell.

A story by Shlomi Fish

Several years ago, during my undergraduate studies of Electrical Engineering at the Technion, I wondered how can one determine if two graphs were equivalent and developed an algorithm for this task. A friend of mine, who took a class by Shimon Even, recommended that I consult him. I went to Shimon's office and found him eager to listen to me and help me. He found a flaw in my algorithm, told me of the history of the problem and referred me to many useful facts. He was also willing to meet with me again, some time later, to evaluate a modified algorithm that I have developed. It turned out that my algorithms resembled some known algorithm.

I'll always remember Shimon as a very nice and friendly man, who was willing to help me and to share with me some of his professional knowledge. I was very sad to hear that he passed away.

A Message from Tal Rabin

On May 14th, a special NYC Theory Day took place at Columbia University. Before the lectures, in his opening comments, Zvi Galil spoke of Shimon. He mentioned his own personal debt to Shimon telling that Shimon and Amir Pnueli are the ones who influenced him to go into Computer Science. He said that he heard their lectures while being a third year undergraduate student in Mathematics, and if it were not for these lectures he would have probably be in Math.

Three of the other speakers also mentioned Shimon in their lectures. Dick Karp said that Shimon was very instrumental in the development and advancement of Computer Science in Israel, and in particular by helping form two major departments at Weizmann and at the Technion. He concluded by saying that Shimon will be greatly missed.

Shafi Goldwasser told a wonderful personal story about her first encounter with Shimon. During the summer of 1980, when Shimon was visiting Berkeley, he took the time to talk to her. He asked her what she working on and she answered: Cryptography. Without further ado in his direct fashion, Shimon proceeded to find out what does she realy know about cryptography ... which was unfortunately very little! As she left his office, there was only one way to save face: figure out what is was about.

Peter Shor said that he got to know Shimon when Shimon was visiting Bell Labs. Although he did not get to know Shimon very closely, from what he knows it is clear that Shimon will be greatly missed.

A Tribute by Yefim Dinitz

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].

Other material available on-line

Former Doctorate students: Baruch Awerbuch, Reuven Bar-Yehuda, Alex Biyukov, Gideon Ehrlich, Fanica Gavril, Oded Goldreich, Alon Itai, Oded Kariv, Aharon Kupershtok, Yehoshua Perl, Sergio Rajsbaum, Michael Rodeh, Yossi Shiloach, and Yacov Yacobi.

Partial list of former Master's students: Hillel Gazit, Igal Golan, Gilad Granot, Dan Kimmel, Igal Kohavi, Gavriela Lev, Yair Oren, Yachin Pnueli, Ishai Rabinovitch, Yonathan Stern, and Rafi Tayar.

Back to Oded Goldreich's homepage.