Research-Life Stories

by Oded Goldreich

[February 2013]


This collection of my research-life stories was triggered by a request of Omer Reingold to contribute to a collection of research-life stories that he intends to maintain on Windows on Theory. I am very supportive of Omer's initiative, mostly because I like stories and believe in their value. Specifically, I hope that the variety of different stories that will be posted will free aspiring young scientists (esp., students) from the illusion that there is a right way to do research and that one should follow some mold that exists somewhere.

I believe that there is no generic (universal) advice on how to do research, but to follow one's own inclinations (i.e., feelings and thoughts). That is, I believe that there is no "proven path" or sets of guidelines that lead to good research. The paths to good research are as varied as research itself, as varied as the researchers themselves, or actually as varied as the combination of research projects and individual researchers. Individual researchers find their own paths, according to whatever fits them. They may seek and/or be assisted by advice from others, but they must decide which advice fits them. The advisers, too, should better target their advice at the specific individual seeking it; that is, try to fit this individual. At the last account, the advisee is the one who matters.


A (late-career) story that illustrates the above

In the Fall of 2008, while visiting the TOC group of Tsinghua University, I participated in an international panel of TOC researchers that was assembled to address questions by dozens of local graduate students. Many of the students sought advice on how to do research. When my turn came to answer, I noted that each of the dozen panelists that talked before me has offered different advice. Knowing many of the panelists, I could see that the advice they offered fit their own personality, their own research style, and the way their own career has evolved. I felt that this best illustrated my thesis that there is no universal and/or generic advice, but to fit the "way of research" to the individual researcher.

Research (being the most advanced form of study) is a highly complex human activity. In particular, it is a highly creative activity, which is exactly the type of activity that we find most difficult to understand. Numerous thinkers have devoted much thought to the notion of creativity; in fact, few other notions have attracted so much attention. Still, as is the case with many notions central to human life, no definite theory arises from this huge body of thought. In light of this fact, the idea of giving advice as to how to do research strikes me as very weird.

I think it should be clear that scientific research arises from the interaction between the objective contents of the discipline and the subjective understanding of the researcher. It seems that almost everybody acknowledges that even the contents of the discipline is subject to interpretations, and that different scientists may hold different opinions and views regarding the relative importance of parts of the existing knowledge as well as the relative importance of different research directions and problems. Thus, even with respect to the objective part of research (i.e., the scientific contents) there is no agreement, and one should definitely not be surprised by the lack of agreement regarding the subjective part (i.e., the researcher).

Of course, all of this does not mean that people do not have opinions regarding the aforementioned matters. Furthermore, some people even believe that their opinions regarding these matters are universally true. You may find such opinions on various blogs, and you may even find some of them useful. (In fact, I have my own advice to myself and to people like me.) My only advice is to take only whatever fits you (i.e., whatever you find useful and/or reasonable).


My first research project (1981)

In one of my first meeting with my predetermined interim supervisor, Shimon Even (who later became my Master and Doctorate thesis advisor), tossed a Rubic Cube at my direction and asked if I can arrange it. I felt compelled to do it, although I hate puzzles and am not good at solving them.

Having no other clue, I noticed that other students that knew how to arrange the cube are often repeating a sequence of four rotations (the first on the right face, the second on the front face, and then in opposite directions on these two faces). So I just went home and put small stickers on each of the 54 small sub-faces of the cube, and recorded the effect of the aforementioned four-move sequence on these 54 stickers noting that many remained invariant. I then started to develop more complex move-sequences, each using a few of the prior move-sequences, which kept invariant more and more of the 54 sub-faces. The end result was an algorithm by which I could arrange the cube by using move-sequences that change few sub-faces at a time.

When I returned to Shimon's office a few days later and told him that I can arrange the cube, he rotated it at random and tossed it to me. I started arranging the first and second layers, using relatively less complex (and less short) move-sequences, and when I came to arranging the very last sub-faces I noticed that I am in a situation that would require me to do a sequence of 150 moves. I felt embarrassed to waste so much of Shimon's time, and told him that instead I would prove to him on the board that I can arrange the cube.

After Shimon finished laughing (which took a while), we started discussing the difference between my algorithm and the more intuitive methods of other students, which never ran into so many moves. The question of the minimum move sequence arose naturally. Phrased in general terms, this yields a computational problem regarding permutation groups (i.e., given a group generated by a set of permutations and a target permutation, what is the shortest sequence of generators that yields the target). Again, instead of being constructive (i.e., providing an efficient algorithm), I proved that the problem as NP-Hard.

Although the foregoing proof could pass as a Master Thesis in~1981 (but probably not today...), I actually ended-up submitting a different work as my Master Thesis. That work consisted of a taxonomic study of various edge testing problems for networks, where most of these problems were proved to be NP-complete. For some technical details on this story and some stories of some of the master theses of my own students, see my essay Demystifying the Master Thesis and Research in General: The Story of Some Master Theses.

My first non-public meeting with Shimon Even (1979)

The foregoing reference to Shimon's laughter reminds me of Shimon, since there was something unique in his laughter, as there was something unique in many of his behaviors and attitudes. I wrote a few stories about Shimon, and the first one is reproduced here.

My first memories of Shimon 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. (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 (his wife) 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 sounds 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 awe (where by "awe" I mean the Hebrew word used in "awe of god", a term that is a hybrid of "fear" and "deep respect" and "love").


A story on "they say" (early 1980's)

Ever since I started my first steps in Cryptography, I have heard various researchers saying with confidence that "Cryptography is dead" (or, more politely, that "all that is interesting in Cryptography has been done"). I wish to stress that I first heard this assertion in 1982! And, then, I heard it in 1983, 1985, 1986; in short, almost every year. Actually, I did not hear it for several years now, but this may be due to the fact that I drifted away from that exciting field and thus may not be a natural victim of such statements.

In the early 1980's I also got unsolicited advice from a prominent researcher saying that if I wish to have an academic career in Israel I better switch from Cryptography to other areas, since "there are too many cryptographers in Israel" (this was in 1984, I think).

I must admit that I was never affected by these assertions and pieces of advice. But my guess is that all of this could have had a negative effect on other researchers. What made me immune to this is a good question. My guess is that I tend to distinguish between opinions and facts, and I tend to doubt opinions that are common wisdom or knowledge. (In fact, I recall that when I was 10-years old I said that if everybody claim something then it is probably the case that they did not come to that conclusion by their own thinking, but are rather following a social convention.)


A generic story

My impression is that, unlike other researchers, I am not a great believer in brainstorming sessions. While almost all of my research was done in collaboration with others, this collaboration typically took the form of discussions of our current state of understanding and consultations regarding where to go from there. In some cases, actual progress and/or ideas arose in these discussions themselves, but in more cases these discussions where a media for exchange of information, ideas, thoughts, speculations, and the like. These exchanges were often crucial to further progress, which was typically achieved by one of few of the participants thinking about what was said later (i.e., when being alone).

I vividly recall a few occasions in which a crucial idea occurred to me. The occasions (i.e., locations and times) in which crucial ideas have occurred to me vary: They include sitting on the toilet, immersing in the bathtub, lying awake in bed late at night, and listening to a talk. In many cases ideas occurred to me when sitting for hours in a cafe (e.g., one of Berkeley's self-service cafes or one of Tel-Aviv's cafes). Other cases include when attending a classical or rock concert, and when hanging out late at night in a favorite bar (e.g., Tel-Aviv's Mid-Bar, which closed almost two decades ago...).

The foregoing references to success stories beg some reference to failure stories. The fact is that I often get into difficult periods (say months) in which I am searching in the dark for something of which I only have a very vague idea. In addition to the intellectual difficulty of conducting such a search, it also tends to be emotionally exhausting. Specifically, often for a long period, I do not get any feeling of progress and this is very frustrating. Only in retrospect, I sometime realize that these "bad periods" were actually periods of progress, although I did not realize it while living them. My advice to myself is to realize that progress depends on the ability to survive these unavoidable "bad periods". One way of surviving them is reminding myself of the fact that I came out of past bad periods and that in retrospect they seem useful (i.e., served as an incubator of ideas that were still unclear and even unconscious at the time). (Other advice to myself and to people like me can be found HERE.)


A story of cultures (1981 vs 1985)

In the summer of 1981, I was working with Po Tong (and others) on a taxonomy of computational problems related to network testing. Most of these problems were NP-complete, and one day I thought that I had a proof of NP-completeness for yet one variant. I showed it to Po, who smiled and said "This is very nice, let me say it a bit differently" and showed me a polynomial-time algorithm... (Needless to say, my proof of NP-completeness was wrong...)

In the Spring of 1985, I was working with Johan Hastad (and others) on the "bit extraction problem" (aka bit-fixing sources). At some point a relatively large group was gathered at Silvio's office to hear of our finding. Johan said he can prove something in some way, and I said that I have a simpler proof and I wish to show it first and later I'll show why Johan's approach will not work. Johan's reply was "Do you want to step outside and fist-fight?" (Needless to say, I declined since Johan is much stronger than me...)


How I started enjoying the process of writing technical papers (1983-4)

When I was a graduate student at the Technion (1980-3), I really hated the process of writing technical papers. In retrospect, I realize that this was rooted in the specific technology I used at the time. I would write drafts in pencil, and bring them to the weekly meeting with my advisor, Shimon Even, who would almost always start from the first page and read along while marking and/or erasing and modifying the text until our meeting was over. I would then copy the corrected draft anew and would try to improve it so that Shimon would get further ahead in our next meeting. (Otherwise, from my perspective at the time, there would be no progress.) Needless to say, this process was quite a pain, and I really tried hard to minimize the number of iterations. (When these iterations were over, the draft would be typed by a professional scribe (a designated secretary). Neither I nor Shimon had direct access to a typing device.)

Things changed dramatically when I started my post-doc at MIT: Like everybody else there, I had a computer (a.k.a a text editing machine) at my disposal. I was excited to try it out for some leftover I had from my graduate studies. Learning to use a text editor and a text processor (vi and troff, resp) was far less frustrating than copying drafts again and again.

Things became fun when I started to collaborate with others, not only in the research itself but also in writing. The first two cases were the work with Silvio and Shafi (on pseudorandom functions) and the work with Benny (on the security of RSA bits). In each case, we had long sessions of writing interleaved with arguing and with making fun of all kinds.

At this point it was clear that writing was fun, and it kept being so also when I started writing texts alone. I developed a practice of writing and then reading and marking and debating with myself the various possibilities; at times I'd even play the roles of Silvio, Shafi or Benny. At other times, I play the role of Shimon, but now I do not need to rewrite the text anew after each iteration...

Indeed, my liking the process of writing predates my advocacy of writing for the benefit of readers and the emotional benefits of writing.


The impact of advisors

I am often frustrated with "my" failure to educate my students (i.e., make them internalize some set of values, norms, or attitudes). At such times, after overcoming my emotional sorrow, I reflect on the common overstatement of the impact of advisors on their students.

It is clear that advisor influence their students, mainly by offering a living example of a (specific type of a) relatively mature scientist. However, typically, such influence does not transform the students, it rather sharpens their profile, making clear prior vague tendencies that were embedded in them. In fact, in many cases, students select advisors that fit their (conscious or unconscious) tendencies, and much of the student-advisor similarity observed later may be rooted in this initial similarity.

Still, sharpening and distilling previously vague tendencies, and shaping them to fit the specific nature of the research activity (in a specific field) is of great value. Although these effects only bring to the surface deeper tendencies, bringing things to the surface allows using them and leads to their actual impact on reality.

Let me demonstrate the above by referring to my own experience with my graduate studies advisor, Shimon Even. One clear characteristic of Shimon was his preference of deeper understanding over broader knowledge. (Indeed, people often talk of their commitment to depth, but the issue is of the trade-off between this commitment and the commitment to broad knowledge.) Shimon would repeatedly study the same algorithm (or the same idea), get to understand it better and better, but rarely be content with his current level of understanding. I think his attitude was in agreement with my own attitudes, but it was by seeing Shimon that I got more aware of my own attitudes and saw what they mean in the context of research.


A pre-career story (1977, 1980)

I became a TOC-researcher quite by accident, or at least so it seems to me. In fact, it all started with a car accident I had while being in my army service. It evolved to one month in a hospital and six months in a chest-long cast. At this point I was disposed from the army. It was August 1977, and I was after a six-month long enjoyable vacation (charged to my army service). So prolonging the vacation did not seem so appealing, whereas entering undergraduate studies seemed natural, except that registration was open (at this late stage) only at the Technion (Israel Institute of Technology).

I was unresolved with respect to what I want to do with my life for several years. Studying philosophy or history, or practicing law or psychology seemed most appealing to me at that time. But none of these was viable in August 1977 (i.e., unlike the Technion, registration for all universities was closed for several months), and so I had to choose among what the Technion had to offer. I chose CS (as 1st priority), because I liked an experimental course in CS that was given in my high-school; it consisted of one semester of finite automata (which I liked very much) and one semester of programming (which I also liked). My 2nd priority was civil engineering (of which I got some clue as a child from my father), and the 3rd priority was Aeronautics. So, I guess I made some choice after all (in setting these priorities), and I soon realized it was a good one -- at least in the sense that my fellow students seemed nicer than those at the Technion at large.

I enjoyed my undergraduate studies; especially all CS-courses. In fact, I enjoyed much less courses in other disciplines, and some of them I really did not like. But towards finishing my studies, it was not clear to me what I want to do next. Working in the CS industry did not appeal to me. So the options were either going to graduate school (of which I had hardly a clue) or switching to a different discipline.

Avi Wigderson said one should apply to graduate schools in the US (we got to know each other a bit during our studies). Together with David Peleg, we consulted Shimon Even who told us that this made sense only if we get admitted to one of the top ten schools (as otherwise we may just continue at the Technion's CS department, which he ranked as possibly inferior only to these top ten). Consequently, I went to the US consulate and took application forms for ten graduate schools. I also went to Tel-Aviv University (TAU) and took an application form for undergraduate studies in psychology. Being lazy and looking at the detailed forms of the US schools, I thought again about the idea of going to graduate school in the US and realized that I don't really want to live in the US (at that stage). I guess the TAU forms were less imposing, so I filled them up, got admitted, and even got an exemption from learning a second foreign language based on my claimed knowledge of a programming language... But then I realized that being interested in psychology does not mean that I am interested in being a therapist. In fact, I realized that my natural impatience is not compatible with being a therapist.

In short, only one option remained: Graduate studies at the Technion. I had no clue what this meant, but applied and was admitted nevertheless. Luckily for me, David and Avi went elsewhere, and so I became the student with the highest grades in undergraduate school admitted in that term. This insignificant (in my opinion) fact had a significant and lasting impact on my life: Shimon took me as his TA for his Graph Algorithms course and nominated himself as my temporary adviser. The next stage in my story is told above.


A story on Graph Algorithms (1978, 1980, 1997)

Shimon Even's course Graph Algorithms was the course I enjoyed most in my undergraduate studies. I think this was due to the material itself, which I found very appealing, and the highly clear and inspiring presentation by Shimon (see the first paragraph in my story of my first encounters with Shimon). But when I took it (in 1978), I found the material quite difficult. I'm sure I would have found the idea that I will be TAing it in 1980 inconceivable.

But when I started TAing this course in 1980, I found the material very simple and easy to understand. I could not understand nor even recall why I found it so difficulty a couple of years ago. In retrospect, I think that we often underestimate the impact of professional maturity: Things become simpler to those who study more advanced and complex material; they become simpler as they are internalized by repeatedly using them in various ways or just by getting back to them again and again. Indeed, when you see a performance the second time, you experience it differently; ditto re learning material.

Anyhow, I also became Shimon Even's student, but I felt disappointed of not doing any graph algorithms research during my graduate studies with him. This disappointment grew into a (mild) feeling of inferiority towards those who did conduct graph algorithms research (e.g., Reuven Bar-Yehuda, who was Shimon's student at about the same time). This mild feeling of inferiority stayed with me for several years. This does not mean that I thought that Cryptography was inferior to Graph Algorithms, but I felt that I miss something by not being involved in graph algorithms research. Occasionally, I did get close to graph algorithms in research on distributed computing (and somewhat even in NP-completeness results regarding graph problems), but it wasn't quite the same.

The first time I felt a bit part of the club (of graph algorithms researchers) was in STOC'97, where my joint work with Dana Ron was presented. After the talk, I bumped into Baruch Awerbuch (who was also Shimon's student) and felt different than before: I felt I completed a research of a graph algorithmic nature, and furthermore of a nature he may find interesting. While not being widely accepted as (standard) graph algorithms research, property testing (of graphs) does materialize another old dream of mine (which goes back to my graduate studies period): Employing randomness in the context of graph algorithms.

It is not that I am working in property testing these days because this fulfills an old dream about working on graph algorithms, but this old dream certainly does not hurt...


On professional developement (1978 vs 1980)

I wish to reproduce (in revised form) the two first paragraphs of the last story in order to make an important point regarding the impact of professional developement: Things become simpler to those who study more advanced and complex material; they become simpler as they are internalized by repeatedly using them in various ways or just by getting back to them again and again. Indeed, when you see a performance the second time, you experience it differently; ditto re learning material. Now for the story.

When I took Shimon Even's undergraduate course Graph Algorithms in 1978, I found the material quite difficult: I failed the mid-term exam, and was very happy to get a good grade in the final, since such a grade surpassed my expectations at the time.

The following semester, I took an advanced graph algorithm course given by Shimon. I took the course without credits, since I did not want to stress myself and had enough credit points anyhow. At that time, I found the advanced material challenging, but not as difficult as I found the basic material in the semester before. Indeed, I was surprised at this phenomenon.

When I started TAing the basic course in 1980, I found the material very simple and easy to understand. I could not understand nor even recall why I found it so difficulty a couple of years ago.


Back to Oded's page of essays and opinions or to Oded's homepage.