Research-Life Stories – Oded Goldreich (2nd post)

Oded Goldreich makes a second contribution to the Research-Life Stories Project (see the first one here):


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…

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s