I was leafing (again) through George Varghese's text,
Network Algorithmics
, and this caught my eye:
In summary, the uncritical use of standard algorithms can miss implementation breakthroughs because of inappropriate measures (e.g., for packets filters such as BPF, the insertion of a new classifier can afford to take more time than search), inappropriate models (e.g., ignoring the effects of cache lines in software or parallelism in hardware), and inappropriate analysis (e.g., order-of-complexity results that hide constant factors crucial in ensuring wire speed forwarding).
Thus another purpose of this book is to persuade implementors that insight into algorithms and the use of fundamental algorithmic techniques such as divide-and-conquer and randomization is important to master.
These words succinctly express feelings I commonly have. Standard algorithms theory often fails to live up to its promise in practice, untethered as it has become from applications. At the same time, a properly designed algorithm can yield immense breakthroughs in performance, so implementors cannot do without them. I believe we need more people willing to sit in the middle, but perhaps first we need more creative ways to bring theory and practice, or theorists and practitioners, together.
6 comments:
Is there a good venue for publishing applicable theory? STOC/FOCS/SODA do not seem like good venues because:
* Algorithms with small hidden constants tend to be simpler, hence less likely to be accepted unless the problem is famously hard
* The first paper studying a new model tends to be less sophisticated than later papers, hence a paper studying a new model is at a disadvantage.
* Theory reviewers are not particularly well qualified to judge how well a model matches reality and hence we would have trouble accepting the right papers with new models even if we wanted to.
I have too little experience with conferences outside theory to say whether or not applicable theory is respected at more applied conferences.
Perhaps there should be a hybrid conference where papers are reviewed by two theoreticians plus two people from an application area?
Warren S.
My latest blog post is related:
What comes first, theory or experiments?
http://www.daniel-lemire.com/blog/archives/2009/01/22/what-comes-first-theory-or-experiments/
Basically, I discuss what happens when you sit in the middle. The downside: you cannot pick just "any" problem. You need to pick a problem that allows you to make progress both theoretically, and practically. That's harder to find.
Example #1: O(log n) is not an acceptable latency. (I'm looking at you, P2P researchers.)
Warren's question goes to the heart of the matter. Perhaps EC, AAAI, WWW, PODC?
Also, how do you think a grad student trying to "sit in the middle of theory & practice" can develop a successful research career? It seems really hard from the theory side. Corporate labs seem to like more "applied theorists" if you'll pardon the phrase, but there are very few relevant corporate research jobs. I don't see the broader theory community rewarding this kind of research. Perhaps you can do it if you try to wear an AI hat or a networking hat, etc, and then interject some theory into your papers. Anybody care to confirm or deny this?
Also, how do you think a grad student trying to "sit in the middle of theory & practice" can develop a successful research career?
It is a very difficult path to follow. You are trying to serve two masters with diametrically opposite goals. Practitioners will criticize your papers for their lack of "systems sophistication" while theoreticians will shoot them down for their lack of "theoretical complexity".
Similarly, theoreticians will say that the experiments in your paper are not needed, while practitioners will gripe about the useless proofs in your papers.
Perhaps you can do it if you try to wear an AI hat or a networking hat, etc, and then interject some theory into your papers.
I think this might be the best way to go about it (have a look at SIGCOMM with its large number of theoretically minded papers published by "networks" authors).
I don't see the broader theory community rewarding this kind of research.
Not at the present time, but other fields (Networks, AI) are definitely warming up to theoretical results which address real life questions.
Anybody care to confirm or deny this?
I don't want to totally discourage you, since the problems are very interesting and the area is ripe for picking, but be prepared for a few lean years in terms of impact, quality of venue for publication, etc.
Also, how do you think a grad student trying to "sit in the middle of theory & practice" can develop a successful research career? It seems really hard from the theory side.
As a graduate student doing networking research somewhere in the "middle" I find this problematic. I have been surprised (unpleasantly) by the tension between Systems and Theory researchers. In the worst case, the arguments, e.g., "this paper is all theory, there is no practical use of this research", degrades into nasty jabs at the other camp. This is discouraging. As a graduate student this makes formulating a research philosophy difficult. This culture leads me to believe that for a given problem I must approach it from either a theory perspective or use a systems-based approach, but not both. I know this is not true and fortunately my adviser is somewhere in the "middle" but it appears to me, at a minimum, this line of thinking is common in our community.
Post a Comment