In the comments on my last post on algorithms and implementation, someone asked where to publish when you sit in the middle, and how can a graduate student succeed by being in the middle. The comments seemed to suggest that publishing was hard and succeeding as a graduate student this way was largely impossible.
Sadly, and disconcertingly, I find myself largely agreeing. I think the theory community has developed to the point where, almost universally, if you want to earn a reputation as a top theorist in graduate school, you have to publish FOCS/STOC/SODA papers. And really this can't be done by focusing on practical issues. More practical papers can be published in other venues -- WWW, INFOCOM, even SPAA and PODC -- but to the theory community these papers don't carry as much weight. (Note: yes, obviously there are RARE exceptions.)
Strangely, I still think there's a reasonable job market for practically-minded theorists, both in research labs, and in smaller universities, where they'd much prefer a theorist who would interact with other groups (like networking or AI) because they really aren't big enough to have theorists who don't have "outside interests". And I think evidence of being able to work with practitioners helps most any theorist looking for a job -- you just can't build your reputation on it. But it can be hard to get that balance of theory and practice "right" as a graduate student.
I see a fair amount of people who are theoretical but practically minded simply going into other fields, either as a graduate student or after. You can be a "theoretical" networking person or AI person and succeed, and a number of graduate students who could be theorists figure out they'll be better off in these areas. You can start out as a FOCS/STOC/SODA person and then branch out to other areas. Go look at Karger or Kleinberg's DBLP pages and see how much more they've been doing in the recent past outside the confines of FOCS/STOC/SODA compared to earlier in their careers. (Or look at John Byers and Soumen Chakrabarti, who worked primarily in theory as graduate students, but switched to other areas.)
Perhaps this would make a good conference panel someday. (Offhand I'd recommend getting Mikkel Thorup and Muthu Muthukrishnan to participate -- they seem to me like role models for people who want to sit in the middle -- though I can think of many others as well...) Heck, come to think of it, I'm the STOC chair, maybe it would make a good panel coming up real soon. Please let me know if you'd like a panel on this issue -- something like "How to Succeed doing Practical Theory?" -- at STOC.