Friday, April 18, 2003
The Turing Award
As noted in a comment to the last post, it is now official that Ron Rivest, Adi Shamir and Len Adleman won the 2002 Turing Award.
Unfortunately outside of computer science and particularly outside academics the Turing award is not so well known or respected.
In 1987, I was a graduate student visiting my old fraternity at Cornell, Anne Marie Hopcroft came in. Anne Marie was dating one of the fraternity brothers
at the time. "My father won the Turing Award! My father won the Turing Award!", she exclaimed. Nobody, besides myself, seemed the least bit interested. She and I tried to explain
the importance of the award but to no avail. Had her father won the Nobel prize, you could be sure the reaction would have been different.
The 1997 movie Good Will Hunting gave great publicity for mathematics much by explaining the importance
of the Fields Medal to the masses. What can we do to make the Turing Award better known?
Tuesday, April 15, 2003
The ACM doctoral dissertation award, given to the best doctoral thesis in computer science,
was awarded to Venkatesan Guruswami for
his thesis "List-Decoding on Error-Correcting Codes". Another theorist, Tim Roughgarden, was one of the runners-up. This was definitely a great
year for theory Ph.D. theses.
Rumors are flying that theorists Ron Rivest, Adi Shami and Len Adleman won the Turing Award for their
work on the RSA cryptosystem. The Turing Award is the highest honor in computer science, the closest we have to a Nobel prize.
Monday, April 14, 2003
Finding Problems to Work On
Often graduate students ask me for a good problem to work on. This is
one of the biggest challenges of an advisor. A good problem for a
graduate student must fulfill each of three characteristics.
Finding problems that
fit any two of these three is not hard, but if a problem is doable and
interesting, someone likely would have solved it by now. Too often
interesting is the property that is given the least emphasis.
generally give the advice that my advisor, Michael Sipser, gave to
me. Pick up a proceedings of a recent conference in your area and read
through the abstracts of papers until you find one that interests you.
The "interests you" part is important, for without it you
won't have the motivation to study further.
Read the paper thoroughly. Read related papers. If you lose interest,
start the process all over again.
Once you've read several papers in an area that interests you talk
about it with your advisor and your fellow graduate students. Some of
these papers might list open questions and you could work on
those. You might say, "Karp listed this as an open question, and
if Karp can't solve it why should I be able to?" Karp is a very
smart but also very busy person. It is unlikely he spent more than an
hour thinking hard about these questions. As a graduate student you
can spend much more time focusing on these problems and could easily
make more progress than someone like Karp could.
Even better is to formulate your own problems. Perhaps there is an
interesting variation in a model that the original paper, for whatever
reason, did not cover. Perhaps you can find connections between two
papers that no one had noticed before. These are great problems to
work on: As you are breaking new ground, theorems can start flowing
like water. Just remember not to have too much weirdness in your
questions; keep the research interesting.