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.