Sunday, January 25, 2009

More on Algorithms and Implementation

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.


Suresh Venkatasubramanian said...

I think you're dead-on about the value (from a job perspective) of having a practical component to your work, (as evidenced by taking the theory work and actually applying it in some domain). The expectations for theory people (in terms of practical value) are often so low, that this impresses people to no end :)

However, I'm less clear about how to make this model work for funding. My limited experience thus far suggests to me that NSF panels are somewhat territorial i.e if you want to get money from a panel in applied area X, it helps to have the panel folks view you as "part of the family" rather than "theoretician trying to steal money away" (yes I've heard this phrase). In order to do so, you need to have a real commitment to the practical side of what you do, which often means that it's hard to keep up the theory end of things.

thoughts ?

Michael Mitzenmacher said...


1) You're right, it helps to have some street cred when you're applying to a specific program. There's a chicken and egg problem there -- you need some funding before you start writing lots of papers in a community so you can get enough street cred to get some funding...
2) BUT, you can start by working with someone in that area -- probably a good idea anyway. If you want to work in algorithms for networking, co-PI a grant with a networking person, preferably after writing a paper with them. Doesn't the NSF love "interdisciplinary" work these days?
3) Also, you can apply to one of the less-territorial funds -- in the past, these included ITR, Cybertrust, even FIND, where I think they're looking for people who might build a connection from theory to practice.

But you're right, it's not easy by any means, and requires a real commitment.

Anonymous said...

As a PhD student in CS who will be on the academic job market in a couple of years, this brings up a larger question as well: Is it better to be a specialist or a generalist? You make the case that if you're interviewing at a small university then being a generalist might be better. What about big R1-type places? Is it better to have your papers spread over several areas, or have a bunch all in one subfield such as theory, AI, or graphics? (Assuming that the quality of the work is the same in both cases.) My impression is that you make the shortlist on your strength in your principal subfield but that you want your job-talk to appeal to the whole department. This perspective may be pretty naive, though. Any thoughts?

Anonymous said...

As you mention the podc/spaa community: this tends to be a general problem for this community. They aren't really embraced by the theory people (as its not focs/stoc), and they certainly aren't embraced by the systems people (its not sosp/osdi).

Thus, when it comes time to apply for a faculty position, you run into some problems. The first is the need to be pigeon-holed: "Do you see yourself as a theorist or a systems person?" you are repeatedly asked. Any answer that isn't one or the other is not appreciated. Next, you run into the problem of needing to convince some group to back your candidature. Yet the theory group would prefer a real hard-core theory person, and the systems group would prefer a hard-core systems person. And while you might be a good second or third choice to both groups, that doesn't necessarily get you very far.

So the upshot is that if you can really do both, i.e., publish at both STOC and OSDI, then that probably puts you in a very desirable middle ground. But otherwise, I think it's difficult.

Anonymous said...

Thus, when it comes time to apply for a faculty position, you run into some problems...

All I can say is what I see from my own perspective (faculty member in theory at a top-20 R1 school).

At many schools (mine is one of them), systems people appreciate someone with a strong theory component. And while the theory group might prefer a hard-core theorist, they can also recognize the value of someone with interdisciplinary ties.

So I think the upshot is to ask around to find a school that will fit you.

Anonymous said...

Crypto is an area where you can be both theoretical and practical.

Rasmus Pagh said...

I try to do theory work that is practically motivated, so there is potential for a companion paper that is more on the practical side. To write a paper targeted at another community, I try to find collaborators with more experience in this. Currently, it seems that writing several, more targeted papers is better (or at least easier) than trying to sit between two (PC?) chairs.

An excellent example is the AMS sketch for second moment estimation. A follow-up paper in PODS (with an added author) pointed out that it could also be used for join size estimation. I think that this is part of the reason it also has had a large impact in the database community.

Anonymous said...

There is are multiple questions embedded here:
(1) what gets you in the door for an interview
(2) what gets you hired, and
(3) what gets you promoted/funded

If you are doing theory these days (and aren't in an area like crypto whose value people outside theory believe they can understand and respect) you probably don't get (1) without papers in FOCS/STOC/SODA. It is good to have a core strength but also to show some versatility that embellishes your record. On the other hand if you've passed (1) then Suresh is right, that algorithmic implementation work can be a big plus for (2) at the majority of places where people outside of theory are in the majority making the decisions.

For (3), it is really best to concentrate your work to become known for something. If you are doing implementation, then to get points for it, it should be something that you can actually get people to use. It has to be at a level that letter writers will know about it before they start writing. My impression is that relatively little of the theoretical work aimed at practice is actually respected by practitioners. Work that is respected gets very high points but the rest gets ignored.

Recent NSF program directors have been relatively good at getting joint funding for some of the cross-boundary proposals. However, part of the problem for proposals at the edge of theory seems to be that they tend to be handled by a single very diverse panel that applies much less consistent standards than the core algorithms and complexity panels do.

Anonymous said...

My impression is that relatively little of the theoretical work aimed at practice is actually respected by practitioners.

Part of the problem is that practitioners are not familiar with how theory goes about solving a difficult problem. The first few theoretical iterations generally attack mock ups of the problem instead of the real problem. This is a way to cut our teeth and test the promise of certain lines of attack: if we can't solve the simplified problem using theory technique X what hope do we have with the real problem?

This sensible "prototyping" drives practitioners to distraction since in the process we omit important aspects of the actual solution.

After sufficient prototyping new instantiations of the problem should start approaching reality.

Alex Lopez-Ortiz

Anonymous said...

Strangely, I still think there's a reasonable job market for practically-minded theorists, both in research labs, and in smaller universities,

I agree with Michael. At smaller institutions and research labs you will get mileage from having combined interests. But in the rarefied heights of the top 10 departments, theoreticians are evaluated first and foremost by how many papers they have in FOCS/STOC/SODA. So unless you think you can publish enough papers in both practical and theoretical conferences (Muthu comes to mind) than it is perhaps best to stick to one field over the other, at least until tenure is behind you.

Alex Lopez-Ortiz

Anonymous said...

Please let me know if you'd like a panel on this issue -- something like "How to Succeed doing Practical Theory?" -- at STOC.

Depends on whether or not I'll be there, i.e. whether one of my papers is accepted.

Can you please make sure to include people from AI (e.g. COLT) as well as systems? Ask someone like Avrim Blum for advice on who to invite.

Anonymous said...

Anonymous said...

Crypto is an area where you can be both theoretical and practical.

which begs the addendum "but most cryptographers are neither" (I am not kidding - try reading some CRYPTO papers and ask expert theorists or security experts about their value).

Jen Rexford said...

I think having a panel on "practical theory" work would be great. My two cents, echoing some of the other postings, is that it takes quite a bit of effort to be "problem driven" (as a good "practical theory" paper needs to be, IMHO) -- to have a problem formulation that is faithful to the real problem, an evaluation that captures the practical trade-offs, and writing that is both accessible and stylistically appropriate for the more practically-oriented venue. It's admittedly a tall order, but the folks who do it can have a lot of impact.

Arguably the easiest way to get over the hump is to collaborate with someone who has domain knowledge and a sense of the culture of the publication (or funding) venue. Another approach is to get feedback from those kinds of folks. The people I've seen be successful at this are tenacious about grappling with the problem formulation and presentation, and willing to solicit a lot of feedback and revise their papers to fit the audience.

Suresh Venkatasubramanian said...

I started off writing a comment here, and that mutated into a blog post: