I was going to post this as a comment on Michael's post, but it started getting longer and longer.
The main question being discussed there is: how do you balance the theory and practical sides of your work effectively from a point of view of getting and keeping faculty jobs ? it's good to remember that not every problem is amenable to a joyous merge of theory and practice: There are levels of hell (heaven?) involved here, that go something like:
* prove fundamental new result, and this leads to breakthrough implementation for a problem people couldn't solve (this happens usually in an area relatively untouched by theory thus far, and can really make you famous) (I'd imagine RSA/Diffie-Helman fall in this category)
* Brand new result: leads to improvements in efficiency AND accuracy of known methods by orders of magnitude
* Brand new result: improves on efficiency OR accuracy of known methods, by orders of magnitude.
Below this line, you're unlikely to get a theory publication out of the contribution:
* Observation that known approaches (or derivations thereof) lead to improvements in efficiency AND/or accuracy by orders of magnitude
* New theory result, some improvements in efficiency AND accuracy
And here's where it gets positively hellish:
* mildly new theory result, reasonable improvement in efficiency and accuracy, but not orders of magnitude, and you go up against an entrenched, highly optimized heuristic (k-means, anyone ?)
At this point you really have to choose which you care about, the problem or the theory, and then branch out accordingly. Papers in this last realm are really difficult to publish anywhere, even when they nontrivially improve the state of the art.
ReplyDelete(1) Observation that known approaches (or derivations thereof) lead to improvements in efficiency AND/or accuracy by orders of magnitude
(2) New theory result, some improvements in efficiency AND accuracy
If we want to make the case that theory is useful (it is and we should) we will need to create a home for papers in this middle category.
The top level results are such breakthroughs that they will appear in whatever conference they are sent to.
The next level down is the problem. They are not trivial but neither of SODA/STOC/FOCS caliber.
Of the two cases at the top of this message publishing in (2) is the hardest. You either submit to theory conference (pizza parlor) or a systems conference (burger joint). Your paper which is a combination of theory and practice is half a pizza, half a burger. Theorists will complain that is only half a pizza, the systems people will complain that is only half a burger, when all the while it is a full meal with pizza for primo and burger for secondo.
Hey cool blog you have here, why don't you guys go check out this Geometry themed t-shirt at Threadless!
ReplyDeletehttp://www.threadless.com/submission/194683/When_I_Grow_Up_I_Wanna_Be_A_Triangle