Continuing from my last "controversial" post, David Karger offered the following long comment, turned into a guest post:
------------
I wanted to post a comment on Mike's FOCS/STOC post, but fittingly for one of the dinosaurs he mentioned it was too big for the comment length limit. Mike's been kind enough to offer to post my comment as a guest post instead.
Mike's question is one I care about a lot. I still respect theory and do work in it, but as Michael says, much of my attention has been drawn into other areas. Many of them have absolutely nothing to do with theory (see last year's ethnographic study of people's use of pencil and paper for notetaking in TOIS 2009 or our AJAX-flavored interface for visualizing and navigating semistructured data in UIST 2009).
But always, some of my favorite projects are where theory provides the answers to problems that matter in other areas. We just published a paper in Nature Genetics that used some simple applications of max-flow to help biologists visualize the "important" influences in biological netwoks (we didn't need to find NP-hard integral solutions because the scientists wanted to see all the possibilities in the mix). Before that, we applied a beautiful JACM paper of Alon etc., on finding longish paths in a graph, to a problem in natural language processing---designing a procedure to figure out a best selection and ordering of words for a machine-generated summary of a machine-generated document---and published a paper at NAACL, a linguistics conference.. I still remember thinking, when I first read Alon et al., that it was one of the prettiest and cleverest ideas I'd seen in a while, but that it would never be useful for anything practical. Ironically, when my colleague Regina Barzilay outlined the language problem to me, it was exactly the Alon problem with no need for translation; my entire contribution was to know that a solution existed (and thus keep up theoreticians' reputation for smart enough to solve any problem instantly).
Other applications of theory to practice have required more work. Mike recently wrote about our paper showing how to design "network codes" for efficient multicast; the core insight of this work was to connect it to the beautiful results that we all study in randomized algorithms courses, on finding perfect matchings by placing random numbers in a graph's Tutte Matrix. Most substantially, our line of work that led to Danny Lewin and Tom Leighton's founding of Akamai begin with a study in STOC of some theoretical problems around handling flash crowds on the internet, and also generated a whole line of research on building robust and scalable peer-to-peer systems.
With the exception of the first paper on consistent hashing, none of this work has appeared in theory conferences. I think there are several reasons for this. Selfishly, for the author it is much more fun (and valuable in generating future research leads) to present the work at non-theory conferences. It holds the same attraction as tourism, going to strange new places and learning new things from the experience. There's also vanity---the allure of being an exotic theoretician among practitioners instead of one of a crowd of better theoreticians than you. Most important, if you want your work to have an impact on the applied areas, you have to publish in their conferences so they'll pay attention---they don't read STOC/FOCS.
But the second reason is more problematic. Many theoreticians would tell you (some have certainly told me) that the above papers are "not theory". That by dint of their having applications, they are no longer suitable for STOC/FOCS. That these papers have a different home, and FOCS/STOC should be reserved for "pure" (i.e. homeless) theory research. I've been on STOC/FOCS PCs that have rejected nice applications of theory on the grounds that the theory part was too elementary.
In part they are right. The biology and NLP papers I mentioned above did not prove any new theorems. But the omission of applications papers from STOC/FOCS means that theory community is failing to celebrate one of its greatest contributions! There's always been a divide in the theory community between those who are enamored of theory problems that help them understand the deep nature of the universe and computation (scientist/mathematicians) and those who see theory as a way of thinking about solving concrete computational problems that often emerge from other areas (engineers). I think that STOC/FOCS is making a mistake by focusing too much on the science to the exclusion of the engineering.
I would really like to see more "applied algorithms" papers appearing at STOC and FOCS. These are likely papers that have not made a major theoretical advance, but rather have synthesized our existing theory knowledge into a solution to someone's particular problem. These papers are just as important to see as the ones that advance theory; they represent one of the major justifications for doing theory in the first place.
I haven't mentioned SODA yet. That is a conference that was founded in part to attract these kinds of applications papers. But at the same time it was founded to attract more of the theoretical discrete math community, and the multitude of targets makes the outcome diffuse. Possibly as a result, SODA doesn't have the stature as STOC/FOCS; I'd like to see applied algorithms appearing at our flagship conferences.
Even if the STOC/FOCS community decides to do this, we still have to deal with what I said at the beginning, that the applied conferences are often more attractive for this kind of theory. You might say "fine, if that's what they want, there's no problem." But I think there is a problem: our community, and in particular our theory graduate students are not being exposed to this important branch of theoretical computer science.
The best solution I can think of is to allow repeat submission. That is, to let the paper appear first in the applied conference, then at STOC/FOCS. Almost by definition, these two venues will not have a lot of overlap, so I really don't see a downside to presenting such a paper at both of them. There are two ways to get this by the copyright police. The first is to accept the paper for presentation but publish only a reference to it in the proceedings. The second is to ask the author to write a new version of the paper aimed at a theory audience. Given the different audience, the paper is likely to be quite different.
Subscribe to:
Post Comments (Atom)
32 comments:
Just to get comments rolling, I'd like to thank to David for his guest post. Obviously a lot of what he says resonates with me, and I appreciate his taking the time to construct a clear and well-written description of some of the issues from his point of view. I hope this will encourage further discussion of the role of "applied algorithms" in theory and theory conferences.
David, I hope you'll consider doing more guest posts in the future!
I definitely agree that theory grad students are not exposed to applications of theory in STOC/FOCS. It is very easy to get the impression that the only practical applications of TCS research are things like fundamental advances in solving linear programs (which only happen very infrequently) and that everything else is only of scientific interest.
But I suspect there might be resistance to Prof. Karger's proposal from theoreticians who view space in STOC/FOCS as being at a premium: If you publish more applied stuff, that means less space for their papers which could be bad for their careers.
Perhaps if there was less focus on conferences...
I think we need to distinguish between two strands of work. One concerns the application of known theoretical techniques to solve applied problems. Most of the post seems to concentrate on this genre of work. Unless the leap from the theoretical idea to the applied solution is substantially novel, I am not sure why this qualifies as research, let alone theoretical research. And even if the connection is novel, it makes no contribution to enriching the algorithmic toolbox. So, there is little justification for this kind of work to be included in theory conferences. The other strand of research is to re-visit the theoretical framework that we have developed over the years in light of advances in systems research. For example, most algorithmic problems in graphs are defined targeting wired networks, whereas wireless networks (which are ubiquitous nowadays) have a very different set of constraints and objectives. The algorithmic techniques we have developed in our classical model are unlikely to be of much use here. Therefore, there is enormous scope of defining a set of new theoretical problems based of new systems paradigms, and solving these problems will likely add new ideas to the algorithmic toolkit. Papers which aim to define and solve such problems, and introduce new theoretical ideas along the way, should definitely get greater coverage in STOC/FOCS.
Unless the leap from the theoretical idea to the applied solution is substantially novel, I am not sure why this qualifies as research, let alone theoretical research.
Some of the biggest research contributions come from having realized that there is a problem worth studying at all, or from having defined things in just the right way, or from having built a system where such new problems naturally emerge. It is silly to value these contributions less because the solution came easily once the problem was properly defined.
In fact, I think this is the exact argument that the conceptual theorists have been trying to make.
I don't know how many of these applications should appear in STOC/FOCS. The world would probably be a better place if more theorists went to systems conferences. (If only because the theorists would hopefully stem the tide of tragic mishandling of theoretical and mathematical ideas perpetrated by systems papers.)
But the omission of applications papers from STOC/FOCS means that theory community is failing to celebrate one of its greatest contributions!
Is that really true ? STOC/FOCS are theory conferences, and as such, are organized around the presentation of new research into the theory of computation. Papers that solve important problems in (say) networking, NLP or databases (using algorithmic ideas) should be published in those venues.
There is an underlying assumption that tends to fuel a lot of the discussion around STOC and FOCS: it goes something like, "STOC and FOCS define the entire theory universe, and therefore everything that we think is good about theory ought to be in STOC and FOCS"..
STOC and FOCS represent major forums for the study of the theory of computation. They're not as central as they used to be, but that's mainly because there are many more venues, and theory itself has expanded its reach far beyond its original, more inward-looking focus.
This is a good thing.
Now it's great that many theoreticians work in applied areas as well. Heck, I just wrote papers for IJCAI, NAACL, ICDE, and CVPR in the last year or so. But I do it because I like doing it, and that to me is the key.
There's a good argument to be made for recognizing and valuing theory contributions that have a major impact in practice. Right now, all we have is the Kanellakis prize, which is a high bar to cross. I'd like to hear more about ways of validating and encouraging such work, so that possibly more are encouraged to do it, and so that the theory community can be associated with good examples of such work.
But I don't see why publishing in STOC/FOCS is the way to do this. I already have an incentive to do applied work, because I can publish in applied areas. I don't need two CV bullets for the price of one. What I want is a way to spread the word of what I'm doing among the theory community, especially if I feel (like a previous commenter mentioned) that the work could lead to new models, new kinds of problems, etc.
Here's an idea. At the next STOC/FOCS/SODA/whatever, let's have a series of workshop on 'Algorithmic X', where X could be networking, bioinformatics, NLP, computer vision, databases, imaging, whatever. Experts can organize it, coordinate speakers, solicit presentations, whatever, and we can all learn something from the work presented. The conference organizers can solicit workshop proposals ahead of time.
And here's the best thing: This works !! It is EXACTLY what other conferences do ! NIPS/ICML does it, as do the database and data mining conferences, as well as many other areas. Work can be duplicated without any problems, and it's a perfect place to (re)-present more applied material with a theory spin that appeals to the theory folk, exposes grad students to application areas, and opens up interesting new discussions.
Excellent comments by Suresh.
A lighter-weight version of applied workshops is to have an "Applications Hour" each day of the conference, and have an "Applications chair" put together a program of four short talks each day, where speakers outline an applied problem, state of the art, theoretical formulations, and connections to existing work in theory. Talks could be invited or submitted. I bet that this would be one of the most-attended sessions at STOC and FOCS, and not just by dreamy-eyed graduate students.
ET_or_TE: that's a great idea too - maybe a good way to work up to full fledged workshops
A major problem with accepting papers in STOC/FOCS/SODA whose main contribution is applying a theory idea to a "practical" problem is that these papers need to be evaluated based on the merits of the application, and theory PCs are often not well-equipped to deal with such evaluations. For any one of the examples that David gave there are numerous papers that claim to solve a very important practical problem, but people familiar with the field can tell you that the claimed solution is either not useful due to modeling assumptions, or that the problem is not that important. Unfortunately, there are many such cases of "over-selling" the results in the theory community.
That said, the "repeat submission" proposal can deal with such cases, if the submission to theory conferences comes after submission to the non-theory conference.
Some responses to comments:
To anonymous who worried about resistance to taking space from normal STOC/FOCS: for republication only a paragraph is needed in the proceedings, which is negligible. And an extra track at the conference could make room for this work without impacting regular stuff.
To anonymous who feels "I am not sure why this qualifies as research, let alone theoretical research"---this is exactly the attitude I find problematic in theorists. What makes it not research? It wasn't known how to do it before, and now it is known. How is that different from proving a theorem (which, after all, was true long before anyone proved it). Another perspective: why should we fail to celebrate that theory research solved a practical problem, just because theoreticians were clever enough to do the research _before_ the problem needed to be solved? We often justify our work to funders by discussing its broad impact---if we trumpet to outsiders, but don't want to recognize it inside our community, isn't that hypocritical?
To anonymous comment that "The world would probably be a better place if more theorists went to systems conferences", I agree. But how do we get them to go? A great approach is to tantalize them with a look at the kind of work they could do by going, by bringing some examples to their home conference.
To Suresh who said "STOC and FOCS represent major forums for the study of the theory of computation. They're not as central as they used to be", I say that's a shame. If we don't have a center, can we really be called a community? I'd really like to preserve STOC/FOCS as the flagships they once were. Right now to see all the best work in theory you'd have to travel every week. Wouldn't it be nice to find it all in one place so you can find out what it is? Perhaps the idea of "republishing" can be generalized, and we can solicit the best work from SOCG, PODC, COLT to be re-presented at STOC/FOCS.
To Mohammad's good point that we can easily be tricked by "faux applications", the approach of re-publishing work from applied conferences seems to provide a good answer---it provides a certification that the practitioners think we got it right.
David: by your definition, does math not have a community ? I understand the desire to maintain STOC/FOCS as the "center" of the community, but I feel that horse has left the barn already, and that's ok. We're a bigger community than two conferences.
Alternately, as Michael has proposed before, why not make STOC/FOCS bigger so it *can* take back the role of center ? Most other major-area conferences are 5-6 day events, with three days of talks, MANY workshops, tutorials, panels, demos and what not. I'd go to such a super-STOC especially if there was a way for me to participate (either by presenting a tutorial, attending a workshop, or whatever).
Ultimately, I believe that incentives have to align with desires. Starting from an essentially moral position that STOC/FOCS is the place to be is less effective than constructing a new STOC/FOCS that would supply the demands that people have. And I think it can be done without changing the essential structure of the conference too much. In that, I think we do agree :)
This discussion is great. It would also be helpful if blogs like this advertised conferences of areas related to theory (but that are less known in the theory community). Some of us need more prodding even if we know what is good for us.
David, are you aware of the more recent work on fixed-parameter algorithms for k-path that improve on the color-coding method of Alon et al.? For example:
http://dx.doi.org/10.1016/j.ipl.2008.11.004
http://dx.doi.org/10.1137/080716475
Could you please give references to your papers where you use color-coding?
(not a theoretician)
I wa just at Interactive 3D, a smaller graphics conference which turned out to have a pretty good poster session. One particularly cool poster had machine learning applied to user interaction in a viz program, which was definitely outside the comfort zone (GPU rendering) of most attendees. The poster's author told me h liked to come to the conference to help encourage cross pollination and keep clear of groupthink. At the individual level, maybe this is a useful trick that people can use without having to wait for structural changes in conferences.
Just want to point out that a workshop similar in nature to Suresh's proposal was co-located with last year's STOC: a workshop at UMD on theory and multicore computing.
I attended it and thought it was very thought-provoking. I don't know what new research came out of it, but I do know that some of the preliminary research presented there ended up in good conferences.
I'm enjoying the interesting -- and useful -- comments; I think the ideas of "repeat submission" (properly implemented) and special sessions or co-located workshops are all interesting, and I'll see that this sort of feedback gets to the SIGACT Executive Committee. So please keep commenting to suggest ideas or voice an opinion on how, or if, you think STOC/FOCS/SODA could be improved.
With respect to repeat presentation / special sessions / etc., such things have been implemented by AAAI for some years now. See e.g. the nectar track, the senior track, the challenge track at
http://www.aaai.org/Conferences/AAAI/aaai10.php
I would like to add a couple of comments to this very good discussion.
One is that there is such a thing as a computer science theory community. In every sizable department there is such a thing as a "theory group", and we know who we are. We may identify with a smaller sub-community, but the algorithms people go to the game theory talks, and complexity people go to the quantum computing talks and so on.
This is good because it makes it easier for techniques to move between different applications, and for results to be developed that would have been impossible without this kind of interaction. (For example the use of randomized hashing in complexity and cryptography, or the use of semidefinite programming in quantum complexity theory.)
It is also good because when a sub-area goes through a dry spell of new ideas, as periodically happens, people can seamlessly start doing something else, and then come back years later with fresh ideas. When an isolated sub-area goes through a dry spell, instead, people have to keep cranking out papers, whose motivation becomes increasing mysterious. (Indeed, when people complain that STOC and FOCS are subject to "fads," they should contemplate the alternative.)
With this premise, I think there are at least two important purposes for flagship conferences: (1) to keep ideas circulating between subareas; and (2) to facilitate the flow of ideas in and out of the theory community -- that is, introducing new models and problem concepts motivated by new applications, and "exporting" useful work that builds on the theory.
STOC and FOCS fall short on both terms, because, for (1), it is just impossible for a community that has become so large to have all its important papers in one place and for (2) because for many such "flow of ideas" papers their natural home is a more applied conference.
As a solution, perhaps instead of having several presentations segregated in a third section, as some commenters have suggested, we should have several invited presentations, perhaps as much as ten, inviting the best papers from related conferences like SoCG, Crypto, etc. (with no *quota*) and also papers from conferences that have algorithmic work (such as, totally randomly, KDD, WWW, Machine Learning?) and which are the kind of papers that all theoreticians should know about.
I agree with Suresh's first post. It is best if the applications of theory get out to the application areas where they will have the direct impact. It is useful for the knowledge of those impacts to feed back to the theory community but this is probably best accomplished by augmenting the major conferences rather than radically restructuring them.
Many conferences have the notion of satellite one-day workshops and It seems that the time is ripe for STOC/FOCS to institute these on a more regular basis. (We have had them sporadically but there is no regular process for including them.) These can work very well in the context of federated conferences like the Federated Logic Conference. (FCRC might be a natural place to include application one-day workshops but they have no structure for this because FCRC has grown so large.)
One reason we don't have this more often is that the timing and logistics of running conferences makes it trickier to include the workshops in the initial planning. For example, co-location of conferences like that of Complexity and EC with STOC this year provides a very nice opportunity but there is no umbrella to allow the easy inclusion of such workshops.
Daniel, thanks for your comment. A reference to the color coding paper we wrote is linked to from the blog post. The faster color-coding algorithm you provided looks interesting; unfortunately, we needed an optimization algorithm (for max weight path), not just a decision algorithm. The Alon et al. algorithm adapted easily to max-weight path; I'm not sure how to adapt the algebraic one (though a technique like that used for parallel maximum matching might perhaps work).
Regarding the general discussion: I don't believe that the "workshop" approach will yield the kind of results I am hoping for. The problem is that conference attendees must make a separate and concrete decision about extending their stay for the workshop, and given the time pressure many of us decide no. We need something that is available during the conference, that we can drop in on, see if we like it, and stick around. That's why I suggested a third track rather than a workshop. This augments without disrupting the existing conference structure.
I am in full agreement with Luca's characterization/objectives for flagship conference. I would have written much the same but felt my post was already too long. I would love to see best theory papers (or more precisely, general-interest papers) being forwarded from _all_ the conferences we attend. We can keep the workload for doing so down by asking the PCs for those conferences to do those selections. This could apply to both our specialized theory conferences and some applied ones.
Unless the leap from the theoretical idea to the applied solution is substantially novel
You mean novel in that (1) it required extra new theorems or (2) that is an unexpected application of the technique or both or neither?
I think theory conferences tend to accept papers that do (1) and reject papers that do (2), even though a novel application of the technique might well be a valuable new source of problems and insights for theoreticians.
And even if the connection is novel, it makes no contribution to enriching the algorithmic toolbox.
A new application of a technique certainly enriches our toolbox. Consider AGT. All they are doing is running algorithms and the first few papers were not even that technically challenging. Yet it has proven to be a rich source of problems.
There are at least two good reasons why re-publication of applications of theory in STOC/FOCS is a good idea:
- It is good politics. It reminds people (ourselves as well as others) that theoretical tools do have an impact in the real world. Whenever the next NSF budget allocation takes place we can point the relevant people to the appli-STOC and appli-FOCS tracks for that argument.
- The second reason is that historically applications have been an excellent source of insight, be them cryptography or optimization problems modeled as graph problems or data streams or game theory or what-have-you.
I agree that the best way to ensure that the applications are valid is to re-publish selected results from other conferences such as KDD, AAAI, IJCAI, etc.
I think it's great to experiment with new models for the conference, and I like the different ideas being thrown out. For the sake of argument, let me try to mount a defense of workshops and also make a critique of republication, with the caveat that I think it's good to think about all such models.
David refers to the scheduling problem - people have to make a decision to stay an extra day, and this is a problem. Again, we can look to the many communities that have regular workshops, and how they do it.
1. They have 5-day events, rather than 3.5 day events like we do. This works because it creates a bigger splash around the conference, and it spreads the burden.
2. Workshops are front- and back-loaded (usually on the first and last day). Again, we have ALENEX/ANALCO as an example closer to home, and we usually get reasonable attendance for each of these, with many people actually sticking around for the main conference.
3. Other forms of presentation (tutorials/panels etc) are interleaved within the conference. again, since the conference lasts longer, this is possible.
4. Workshops have to be proposed and approved: this creates a kind of 'will the community enjoy this' filter that allows for better workshops.
Note that the goal of having workshops is not to have the core theory community attend en masse. The goal is to (a) bring new people into the STOC/FOCS orbit (b) expose *interested* people to new topics that they'd have to go to a different conference to attend otherwise. So even if say 25% of the regular attendees were to attend workshops, that's a win.
Coming now to the republication idea: we have some prior data points to consider. At both SODA and SoCG, we've experimented with experimental "tracks", and SODA had the (in)famous short paper experiment. All of these experiments failed, and I think they failed because
(a) the tracks got ghettoized and marginalized
(b) the notion of 'experimental work' or 'discrete math' is too broad.
Similarly, I feel that republishing 'best of' papers is way too broad. Tutorials are a better mechanism for this, because they allow the quick dissemination of highlights from a sub area, and even invited talks can serve this purpose. In other communities, tutorials are proposed and peer-reviewed just like papers, and then if approved, the authors present at the conference. So tomorrow I could propose a tutorial on say 'geometric applications of path planning in game theory', and I'd have to detail which papers I wanted to talk about and why, and would have to make the case for why the target audience should care about it (I've done two tutorials of this kind already, and am submitting a third right now)
Finally, I think that with whatever model we design, it's important to get the incentive structure right. it's customary to cite tutorials, workshop presentations, and even workshop organizing on CVs. However, it's not yet clear to me how to cite a 'republished paper'. And this is important, as our game theory experts will attest to :)
However, it's not yet clear to me how to cite a 'republished paper'.
This is not a problem. As other people have pointed out these already exist within the AI community. Here are some citations obtained by running the queries
CV nectar AAAI (in google)
and
nectar AAAI (in google scholar)
# A* Search via Approximate Factoring, Aria Haghighi, John DeNero, and Dan Klein, In proceedings of AAAI (Nectar Track) 2007. [pdf]
Y. An, J. Mylopoulos, A. Borgida ``Building Semantic Mappings from Databases to Ontologies'', AAAI NECTAR 2006.
Machine learning and SAT: Acquiring Constraint Networks Using a SAT-based Version Space Algorithm, by Bessiere, Coletta, Koriche, and O'Sullivan in the AAAI-06 Nectar Track.
[St. Amant et al., 2006] St. Amant, R., McBride, S. P.,
and Ritter, F. E. (2006). AI support for building cognitive
models. In Proceedings of the Twenty-First National
Conference on Artificial Intelligence (AAAI),
Nectar Track, Menlo Park, CA. AAAI Press.
I certainly sympathize with the idea of building and expanding bridges between theoretical and applied conferences. Both are likely to benefit in this way.
However, I do not believe that there are strong obstacles that prevent anyone from doing this already. IMHO, it is not difficult to publish two papers along the same line of research, one at an applied conference, and one at a theory conference (assuming the research is interesting to both communities). I have done it, many other people have done it, too many examples to list. In particular, the "applied publications followed by theoretical publication" route makes lots of sense, since the motivation has been vetted by the time of theoretical submission. Other direction can also work.
Of course, doing that does require some effort:
(a) one must be careful about identifying and attributing the contributions of the two papers. This *is* a little bit of pain, but a not major one, since typically different communities care about different things (proofs vs empirical results). Having different (even if related) results in the two papers can make things easier.
(b) one needs to write the papers differently, in order to address the issues important to the individual communities. This perhaps takes most of the effort. However, this has to be done in any case: the same paper is unlikely to be understood, let alone appreciated by two different communities. Empirically, some translation is always required.
Still, it is good to brainstorm what can be done to further streamline the process. One option (along the lines of what David suggested): what about "short communications" or "posters" ? This would take care not only of (a) but also of (b) above, since it is easier to write 2 pages in a "different language" than to write the whole new paper. Some conferences (e.g., PODC) have such options. Along the same lines, SIGMOD has research tracks as well as demo tracks and industrial tracks; this serves a similar purpose (shifted by one level towards applications).
As Suresh says, many of our prior experiments in broadening the content of our theory conferences have failed/been marginalized. I believe the reason is simple: we don't allow re-publication. When an article can only appear once, we will naturally try to put it in the best possible place for it. So our best work goes to the main conference, and these side tracks are left with more marginal work, which is a self-amplifying process.
Of course, needing to pick one venue is also the reason many applied theory papers appear in the applied conferences rather than the theory conferences. With republication, this problem goes away. You can submit to the best place and also to STOC/FOCS. Actually, calling it republication is a bit of a red herring. I see no particular reason to print the article all over again, unless you are writing a completely different article for the benefit of the theory audience. The important part is the talk, not a publication at all; I just think it would be useful to include a paragraph in the proceedings as a record of what was presented at the conference.
Piotr's point about the possibility of publishing a theory and an applied paper is a good one, but it only applies in the (not uncommon) case where one combines substantial theoretical progress with an application of that theory. This case works well because the practitioners often don't want to see all the details of the theory, and vice versa, so two publications are natural. But it doesn't work when the applied problem was solved by a straightforward application of known theory---there is then no theory paper to publish. I remain convinced that this kind of success is worth highlighting at theory conferences.
To add to Suresh's comment: there *is* at least one republication model that seems to work, although both broader and smaller in scope than SoCG/SODA experiments. I am referring to CACM "Research highlights", which aims to publish recent papers that are of interest to the broad CS audience. Over the past year or so, there have been several examples of papers of both "theory of interest in practice" as well as "practice of interest to theory" flavors. Of course, there are only 24 of them published per year, so the throughput is limited.
From little that I know, similar models seem to be popular in IEEE circles as well. Of course, IEEE folks are a little more journal-oriented that their CS peers.
I just looked over the most recent CFP for the AAAI nectar track. It's an interesting model that could work along the lines that David is envisioning, without too much extra overhead.
There's one issue though, and maybe it's a problem that the original proposal isn't really trying to solve. AAAI is an established flagship conference: people (at least in certain parts of AI) go there anyway. Having the nectar track is then great, because you're there, and you hear interesting stuff.
STOC/FOCS is not quite at that level - in fact one beneficial side effect of any such endeavor would be to get them to that state. But as such, you're unlikely to get new people to come to STOC/FOCS just because the nectar track exists (except the presenters of course).
I think now that the reason I (and Paul and Piotr too) have been arguing in favor of satellite events is to address this second issue, of getting more people from outside the core to come to STOC/FOCS as well.
I am rather late to the discussion but in any case I have two things regarding the post.
First, I want to say some thing about the Alon etal paper. While I was at Lucent Bell Labs there was some effort to develop a tool to help schedule technicians for repairs. Clients scattered around some geographic area had windows of availability and the goal was to schedule a technician so that he/she could visit and do as many jobs as feasible during a day. The problem is more involved than finding a long path because of weights, time window constraints, travel and some other side constraints. However, it is fairly easy to see that the color coding approach of Alon etal can be used in this setting. Since a technician can visit only say 10 sites, the problem is amenable to the approach and in fact one of my colleagues implemented the algorithm following my "seeing" the approach.
I did not think it was worth publishing the above although one can say that some one else not familiar with the Alon etal paper probably won't be able to come up with the algorithm so easily. On the other hand, I can imagine that in academia one would write up some thing like this, especially if it is a collaboration between an applied person and a theory person.
Although I think one should occasionally highlight applications of theory ideas as above and maybe mention them in a talk, I am unsure that these should be published in our regular theory conferences. Lots of people outside mainstream TCS researchers use advanced "known" algorithmic ideas - they are not all going to come to STOC/FOCS. I think our time is better spent, especially at conferences, in absorbing and understanding new ideas and areas. This could include some non-trivial and high-impact use of existing ideas but I would say that fairly routine though clever uses of existing ideas is not that helpful.
My beef with conferences as a whole is the following. The PC spends a lot of time selecting papers. I think the job of selecting the clearly top papers is easy. Then the PC "wastes" a lot of energy trying to compare apples and oranges. That is fine at some level but what this means today with easy access to papers and numerous conferences is that people don't go unless they have a paper. At some level, the goal of conferences to foster a community and bring together people is diminished. I feel that there should be a nice mega-theory conference once in say 2 years at least that most theoreticians feel like going to.
My 3 cents:
1. David, you are right - singular "application stories" are hard to capture in the two-paper approach. One would need other ways of disseminating and promoting them.
2. Chandra: I think the idea is that that such papers, although published in regular theory conferences, would *not* be regular theory papers (possible alternatives: no paper, short paper, poster, etc).
3. Chandra+Suresh: I think having a track accommodating many such papers would go a long way towards solving the participation problem.
fyi all: I just noted the ICALP call for workshops. It's structured just like in other conferences - workshops on the first and last day of the conference - topics solicited on all topics in theoryCS.
So we at least have one example close to home. Are there any ICALP folks lurking here who might be able to comment on how the workshops have gone in the past ?
Is there any empirical evidence on whether co-located workshops work better when they are at the end points of the conference or right in the middle? My feeling is the latter would give folks less "excuse" to skip these workshop but I could be wrong. (The only place where I know about the middle workshop was the ITA workshop last year.)
Overall I think the idea of more practice oriented workshop is great. Maybe a workshop along the lines of "open problems in area x," would be way to get the theory folks to attend.
Post a Comment