Reading PhD applications

Believe it or not, it's already time to start reviewing applications for fall 2010 admission to the PhD program at UIUC. Because I'm the head of the algorithms group, I read every application that indicates primary interest in algorithms, plus any others that others that other faculty bring to my attention during the evaluation period. Out of that imperial buttload of applications (about 75), the algorithms group will recommend less than 10 new students for admission. The final admissions decisions will be made by our graduate admissions committee. (Altogether, there are about 750 applicants to our PhD program this year; I don't know how many admission offers we plan to make. I'm not on the admissions committee.)

Even though I've just started reading applications, I'm already reminded of several frustrating mistakes that lots of applicants make. Maybe I should say this more positively... Here is a list of recommendations (requests?) for people applying to grad school next year! These are all tied to the main thing I look for in prospective PhD students: clear evidence of future excellence as an independent computer science researcher.

I should emphasize that these suggestions reflect my own personal biases; many of my colleagues disagree with me, sometimes vehemently. In particular, these are definitely not departmental policies!

• Put your work on the web! Prior research experience is fantastic, but the one-sentence description in your statement of purpose really doesn't tell me much. Set up a web page (either through your school or through some free hosting site) with links to as much of your work as possible, and include the URL in your resume and in your statement. “Work” includes conference and journal submissions, technical reports, independent study projects, class projects, software demos, and even progress reports for incomplete research. Even if it's already published in a regional workshop or conference proceedings, put it on the web. If it isn't on the web, it doesn't exist!

• Request recommendation letters from people who can accurately judge your research potential. The best letter writer is a faculty member who (1) has direct, personal knowledge of the applicant's research ability, (2) has experience with successful PhD students, and (3) is active and trusted in their research community. In general, don't request letters from department heads (unless they've worked with you directly), teaching assistants, fellow students, parents’ colleagues, or managers of non-research jobs, unless their letters fill some otherwise gaping hole in your application. [I broke this rule. When I applied to grad school, I got letters from managers at my programming job as badly needed evidence that I'd learned how to work.]

• Say what you're interested in working on and why. Be specific! I look for students who have enough independence and curiosity about something to ask interesting questions or even make half-baked conjectures. Nobody expects that you'll actually work on the problem you write about; that's not the point. We can't even really expect you to work in the field that you write about. By not writing about your own interests (or worse, describing your interests only by listing the faculty members you want to work with), you're strongly suggesting that you don't have any.

• If you're interested in working with specific faculty members, know what they do. If possible, say something intelligent about some of their results, not just the broad area they work in; make it clear that you read more than the list of faculty on the department web page. Considering faculty with different research interests than yours is an excellent idea, but then make sure it's clear that you understand the difference. For example, don't write that you want to work with me because of your deep interest in approximation algorithms, or cryptography, or networking.

• Look good at what you say you want to do. In particular, if you want to study algorithms, don't get a B- in your undergrad algorithms class, unless maybe you took it as a freshman (but you got an A in the graduate algorithms class the next year), or you missed the final exam because you were working on a STOC submission (which you put on the web). [I broke this rule.]

• Never suggest that you're getting a PhD “by default”. Getting a PhD in theoretical computer science is a high-risk multiple-year commitment with a negative expected payoff, even for successful students. I honestly can't recommend it to anyone who doesn't have to do it. Don't apply to grad school because you “really liked college”, or because you're too lazy to look for a job, or to impress your boyfriend, or because that's what your parents want you to do. We want students who love what they're doing!

• Evidence of intelligence is necessary, but not sufficient. So you got a perfect GRE score, or you have a 3.9+ GPA, or you scored in the top 0.1% on the IIT entrance exam, or you got second place in some international olympiad thing. That's great, but those are all evidence that you can answer closed-form questions with well-defined answers under timed conditions. Research (at least, good research) ain't like that. Low scores are red flags, but high scores are basically meaningless. Evidence of independence, creativity, passion, and maturity are also necessary (but not sufficient). [I am definitely in the minority here. Many faculty, indeed many departments, will gladly accept anyone with a 4.0 GPA, regardless of other factors.]

• Finally, do not submit an application with spelling, grammar, or punctuation mistakes. Do I really need to explain this one?

Also, if you happen to have an extra one, I'd like a pony. A flying pony with rainbow chocolate sprinkles. Thank you.

Comments

[pierre]

Here is my mental translation of your advice into my language.

Imagine you are an undergraduate student in computer science, and you love what you do. You take as many classes as you can, and naturally, you get quiet good grades. You are often one of the top students in your class, and your professors have a very good opinion of you. You might think that an excellent record like yours would be enough to get you into the top schools.

Nope. Second tier schools welcome you with open arms, but to get into the best schools, you need
more. You need a research statement which does more than conveys your enthusiasm for studying computer science. More importantly, though, you need demonstrated potential to do research. This is the big one. So off to do research, then!

Oops. As an undergraduate, there really is no research you can conduct independently, and the chances of you being able to seriously contribute to a research project is small - it usually takes graduate students a couple of years to really learn their field.

What you need to do is find professor X who will give you a good research project. Good in this case can mean several things: (i) X needs someone to do some coding. Your name will go on the paper even
though you have no understanding of most of it. (ii) X knows of an interesting research problem which can be solved in a way understandable by an undergraduate, but has too much other work to write it up. That's where you come in. (iii) X does 99% of the work for you by framing a question which is unanswered, important, and yet simple enough to be understood and solved by you.

If you find such an X, things will be great for you. You will have preprints to post on website, a recommendation which says you have good research potential coming from a known researcher, and X will likely help you with your research statement to make sure you don't look gauche by listing keywords which were fashionable five years.

[Humbert Humbert]

>>As an undergraduate, there really is no research you can conduct independently

Wrong. Consider astronomy: there are billions upon billions of stars up there, and only so many that the experts can focus on. That's why to this day amateur astronomers are still making interesting (if minor) discoveries.

So too with CS: there are innumerable interesting problems to be solved (and unlike the physical sciences, we don't need access to fancy equipment to solve most of them). My undergrad experience was that I solved some very small -- but interesting -- problems of my own simply because I wanted to see cool stuff happen on my screen. And you know what? Grad schools ate it up. Just have fun exploring new ideas and don't worry about whether they're earth-shattering new research (for now).

A final word of caution: don't *ever* let Professor X hand you a problem (if you can avoid it). The reason you're in school is to develop your own creative thought process -- not to work out the kinks in someone else's creation. Professor X is simply there to keep you on track (and to let you know when hostile mutants are nearby).

[Sariel]

The numbers of people being admitted is going to be down - there is less money. I expect we will make around 80 offers, and expect to get in 40-50 students out of these. --S

[JeffE]

Pierre: What Humbert said. Again: What Humbert said.

Your description was spot on, right up until the point where you said "oops". Undergraduates CAN do computer science research independently, especially in algorithms.

Moreover, you're confusing "do research" with "seriously contribute to a research project". I'm *much* happier recommending a student who has lots of interesting ideas that never work, or who independently solves a problem nobody cares about and/or was solved decades ago, or who only shoots down my bad ideas, than a student who successfully slogs down a road someone else laid out for them and gets a SODA paper out of the process.

All that I mean by "research" is do interesting things that nobody told you to do. Find and fix minor bugs in other people's published papers. Make an iPhone app that computes the homology groups of whatever the camera is looking at. Build three dimensional Voronoi diagrams out of wood and string. Translate the Art of Computer Programming into iambic pentameter, or rewrite CLRS in the style of Gilbert and Sullivan. Demonstrate that you can work independently, that you have lots of ideas, that you can tell good ideas from bad, that you can do the necessary scholarly legwork, that you pay attention to detail, and that you're not afraid to look stupid.

[Michael Mitzenmacher]

Jeff --

I think you've given good advice, but I'm deeply afraid that now, based on your comments, I'll be seeing folders containing the Art of Computer Programming translated into iambic pentameter, or, worse yet, CLRS rewritten in the style of Gilbert and Sullivan in the future. I realize that students sending such things in will, of course, have intrinsically violated your boldfaced principle of do interesting things that nobody told you to do, but I'm afraid I expect them now anyway. I will not forgive you.

Best, Michael

[Aaron Sterling]

Getting a PhD in theoretical computer science is a high-risk multiple-year commitment with a negative expected payoff, even for successful students.

I agree with this, and think the situation will become more acute in the coming years, as the ill health of the California university systems affect academia throughout North America. (And many of those universities already have budget problems of their own.) A question I don't know the answer to is: how long has this been true? Would you say the statement I quoted has been true for the majority of student for at least 25 years, or was there a watershed event, say 1993/collapse of the Soviet bloc?

[pierre]

Humbert and JeffE,

If a problem is important/interesting, and has an easy solution (which must be the case if it can be solved by an undergraduate), why hasn't anyone bothered to write up a solution by now? My answer: it can't be that important/interesting.

JeffE, and perhaps Humbert, differ because they have a slightly different definition of what it means to do research. Suppose you spent several months doing what JeffE suggests. You go through a published paper, find some typos. Whats next? I suppose you send in a list of these typos along with your applications? Next, you take some mathematical abstraction and write a java app which produces cute pictures of it. You write up a list of ideas you have for solving some open problems, none of which work, and all of which are considered naive by the experts.

Would this be enough (in addition to top grades in courses) to be accepted by the top schools? It seems quite unlikely to me, though I'm open to being corrected.

[JeffE]

If a problem is important/interesting, and has an easy solution (which must be the case if it can be solved by an undergraduate), why hasn't anyone bothered to write up a solution by now? My answer: it can't be that important/interesting.

You're welcome to your opinion, of course, but you're wrong. Undergraduates can and do produce hard results; see Mihai Patrascu. Results that are easy in retrospect are not necessarily easy to find (unless P=NP); see Timothy Chan. Even for problems that are truly easy to solve, someone has to ask the right question first; the simplicity of the result does not make it uninteresting or unimportant. In fact, simple results are more likely to have broad impact in the long run than towering intellectual achievements that only experts understand; see PageRank.

Suppose you spent several months doing what JeffE suggests. You go through a published paper, find some typos. Whats next?

You show your work to a local expert (an active researcher in your field of interest, preferably the paper's author) who can appreciate what you've done and suggest things to try next. If you impress her, she might invite you to sit in on a seminar, or do an independent study project, or collaborate on an open problem. Then you either follow her suggestions (because they sound cool, and you believe that she knows what her community values), or not (because her suggestions are boring). Either way, do something else you find cool and interesting.

Research involves a heavy mix of individual effort and community feedback. Part of the effort is in getting the feedback, and listening to it, and giving feedback back.

You write up a list of ideas you have for solving some open problems, none of which work, and all of which are considered naive by the experts.

If this is all you do, then you're right, it won't help much. (But “naive” is certainly better than “obviously wrong”!) Some of your ideas have to be interesting. This is part of “Look good at what you say you want to do.“

And yes, by putting your ideas out there, you run the very real risk of looking naive. Part of what we're looking for is the maturity to know which of your ideas are good, and the confidence to put them out for public view even if you're not sure.

[JeffE]

I'll be seeing folders containing the Art of Computer Programming translated into iambic pentameter, or, worse yet, CLRS rewritten in the style of Gilbert and Sullivan in the future. I will not forgive you.

I am so confident that this will never, ever happen that I will write the final stanza of such an application myself.

For my algorithmic insights, though I'm still an lowly undergrad,
Are sure to yield results no SODA, STOC, or FOCS has ever had.
Although if Mitzenmacher reads my folder he'll be kinda pissed,
I am a very good theoretical computer scientist.

Chorus: If Michael Mitzenmacher reads his folder he'll be kinda pissed,
But he's a very good theoretical computer scientist.

[pierre]

Undergraduates can and do produce hard results; see Mihai Patrascu.

I agree that this happens, but it doesn't happen very often. Anyway, people who produce
hard results as undergrads probably do not need advice on getting into grad school.

Results that are easy in retrospect are not necessarily easy to find (unless P=NP); see Timothy Chan. Even for problems that are truly easy to solve, someone has to ask the right question first...

True, but the ability to ask the "right" questions is something that only comes with years
of experience.

You show your work to a local expert (an active researcher in your field of interest, preferably the paper's author) who can appreciate what you've done and suggest things to try next. If you impress her...

A big if.

I guess this is the key point that we've been arguing about. Take your typical smart undergraduate
from a top school; someone who loves computer science and gets A's in all of his/her courses. Will
this person be able to look at a paper in some technical area and come up with insights which
will impress an expert?

There are a few people out there who are quite advanced as undergrads, and perhaps they might. For
almost all others, graduate school is what you have to go through to be able to produce such insights.

[JeffE]

A big if.

Yes. A big if. Luck plays a huge part in this process. There is absolutely nothing that you can do to guarantee success. All you can do is raise your expectation of success. (The variance, to paraphrase Baruch Awerbuch, is a function of the committee reviewing your application. The origins of skewness and kurtosis are left as open problems.)

True, but the ability to ask the "right" questions is something that only comes with years of experience.

Usually, but not always. And more often than not, too much “experience” makes asking the right question impossible. It's hard to put down a tool you've used for years and pick up something new. An amazingly large number of important results are discovered by students.

I guess this is the key point that we've been arguing about. Take your typical smart undergraduate from a top school; someone who loves computer science and gets A's in all of his/her courses. Will this person be able to look at a paper in some technical area and come up with insights which will impress an expert?

Certainly not all of them. Many extremely smart undergrads have no talent or interest in computer science research; their strengths lie elsewhere. But a surprisingly large fraction of them, yes. If they try.

For almost all others, graduate school is what you have to go through to be able to produce such insights.

Ahh, perhaps we are miscommunicating here. Undergrads come up with publication-worthy insights all the time, but that's not a fair bar to use for admission to a PhD program. (Alas, Illinois is not MIT or Princeton; we admit theory PhD students who don't already have STOC/FOCS papers.) The student's insights have to be put in context. The same insight can be impressive coming from an undergraduate, routine coming from a graduate student, and disappointing coming from a senior researcher. I trust my colleagues who write letters to make that distinction.