Our next entry on the Research-Life Stories Project is by Oded Goldreich (a second installment by Oded will be posted in a few days).
——
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…)
Windows On Theory 
One thought on “Research-Life Stories – Oded Goldreich”