mediocrity. It gives the illusion that
research is about making small increments to someone else’s work. But
worse, it almost guarantees that after
a while, the work is driven by what can
be solved, rather than what needs to be
solved. People write papers, and the
papers get accepted because they are
reviewed by the people who wrote the
papers being improved incrementally,
but the influence beyond the world of
paper-writing is minimal.
the early model:
theoretical theses
In the first years of computer science
as an academic discipline, many theses were “theoretical,” in the sense that
the contribution was mostly pencil-and-paper: theorems, algorithms and
the like, rather than software. While
much of this work was vulnerable to
the problem just described—paper
building on paper—it is quite possible
for a theoretical thesis to offer a real
contribution. For example, even before
I joined the Princeton faculty, I had a
summer intern at Bell Labs, Ravi Sethi.
At that time Ken Thompson and Dennis Ritchie were involved in the Mul-tics project, an operating system for
the GE635 computer. This beast was
the first to have more than one register in which arithmetic could be done,
and the word passed to Ravi and me
that they needed techniques to compile code in a way that made best use
of several registers. Ravi’s thesis was
an algorithm for compiling arithmetic
expressions using any given number of
registers, in the fewest possible steps.
This algorithm actually was put into
the C compiler for the PDP- 11, a few
years later.
While Ravi’s thesis was “
theoretical”—neither of us wrote any code—
the work illustrates how I believe any
thesis should develop. The work was
not based on what some paper left
open, but rather on an expressed need:
a way to compile expressions using
several registers. The big advantage
we had was that we were part of an environment that was pushing the frontiers. Had we not been at Bell Labs, it
is doubtful we would have realized the
problem was worth addressing. We
surely could not have read about it in
a paper. Even Andrei Ershov, who had
previously published the node-num-
When i went off
to study for my
doctorate, i had
no idea what writing
a thesis entailed;
had i known, i never
would have gone
to graduate school.
bering scheme we used, only saw it as
a way to compile for a one-register machine, and did not suggest in his paper
that someone else should look at machines with multiple registers.
the ideal Ph.D. student
The best scenario is that the student
tells me what their thesis should be,
and carries it out independently. Moreover, their thesis topic is selected because they perceive a need on the part
of some “customer.” Sergey Brin came
closest to this ideal, since he and Larry
Page, with no help from me, saw both
the need for a better search engine
and the key ways that goal could be
reached, while students at Stanford.
The one missing element: neither of
them got their degree; but more about
that later.
A close approximation was George
Lueker, who came to visit me one day to
ask if I had any ideas for a thesis topic.
George was not then my student, being
enrolled in the Applied Math Program
at Princeton. I happened to be reading
about chordal graphs that morning,
and suggested an algorithm to detect
chordality. A year later, he came back
and showed me a thesis he had written
on pq-trees, a data structure that even
today has several important applications beyond chordality testing. Several
other students have dragged me kicking and screaming to learn a new area,
even if I then got involved in selection
of their thesis topic. Matt Hecht had
me learn about data-flow analysis; Allen Van Gelder did the same with logic
programming.
Why does it matter who suggests the
thesis topic? We’re trying to get young
scientists to the point where they can
make independent judgments about
what is worth working on. There are
several decisions to be made: what is
worth doing, what is feasible to do, and
how do you do it? While an advisor can
help with all these things, it is wonderful to meet a student to whom this
comes naturally. Another point that I
tried not to forget as I grew older was
that young people can often see things
that those of us who have become set
in our ways cannot. Trusting the technical judgment of the young is not a
bad strategy.
What students need
To make students successful, we need
to be ready to provide many services.
Finding customers. As mentioned at
the beginning of this Viewpoint, there
needs to be an exposure to problems
that are at the frontier, and that are
needed by a “customer.” Sometimes,
they can find a customer in industry,
as Ravi Sethi did at Bell Labs. Summer
internships can be a great opportunity. However, advisors should encourage students to intern at a strong
industrial research group, one where
the goals are more than minor tweaks
to what exists.
Whether the thesis is theoretical
or an implemented solution, students
need to be guided to understand who
will consume their contribution if they
are successful. And the answer cannot be “people will read the paper I
will write, and they will use the open
problems in it to help form their own
theses.” Especially when dealing with
theoretical theses, the chain of consumption may be long, with idea feeding idea, until the payload is delivered.
Yet if we let students ignore the question of whether such a chain and payload plausibly exist, we are doing them
a disservice.
Walking before you run. Exposure
to problems is not enough. Some, although surely not all, Ph.D. students
need to convince themselves that they
can do something original. Here are a
few ideas that have worked:
˲ One way to give a beginning student practice with the mechanics of
research is to think through a small
problem yourself, and then propose