Giving American Flags and Conceptual Contributions to Orphans

I am worried that, lately, I am agreeing too much with James Lee. I hope my friends will stage an intervention if I start saying things like “…this group acts by isometries on Hilbert space…”

I agree with his choice of favorite STOC’08 talks, but also with his comments on the statement on the importance of conceptual contributions in theoretical computer science, which was recently written by a group of distinguished theoreticians, was briefly discussed at the STOC’08 business meeting, and was commented upon here, here and here.

In Mr. Spritz Goes to Washington, Lisa and Homer help pass a bill to divert flights from over their house by tacking their air traffic bill on a “giving orphans American flags” bill.

I felt that the statement (and the subsequent public and private discussions) similarly mixes the unobjectionable with the potentially controversial. There have been two themes that are entirely agreeable.

One is the importance, and value, of simplicity in proofs. This goes without saying, and I think that the community does a good job in recognizing simple resolutions of long-standing open questions, as well as new simplified proofs of known results. In fact, I think it would be hard to find someone who suggests that, all other things being equal, a harder proof is preferable to a simple proof.

Another is the importance of introducing new concepts and models. Indeed, there would be no theoretical computer science without its “concepts,” and the field would die if it would stop innovating. Again, nobody could possibly argue against the importance of new definitions and models.

Then, there is something which is said in the statement in a way that is not self-evident:

Once understood, conceptual aspects tend to be viewed as obvious, which actually means that they have become fully incorporated in the worldview of the expert. This positive effect is actually a source of trouble in the evaluation process, because the evaluators forget that these contributions were not obvious at all before being made.

Indeed, our community should be warned of dismissing such contributions by saying “yes, but that’s obvious”; when somebody says such a thing, one should ask “was it obvious to you before reading this article?”

I think (and I echo things that were better said in comments that I linked to above) that if something looks obvious after reading a new paper for the first time (as opposed to looking back at a classical paper from twenty or more years ago), then the paper is not making a valuable conceptual contribution. The time that it takes to read a paper cannot be sufficient to “alter the worldview” of the reader: the concept must have been “in the air.”

To be sure, usually even the greatest discoveries are in the air when they are made, a point which I want to write about in a different post. The fundamental difference, however, is that reading about a good conceptual discovery for the first time is startling and exciting, like hearing a good joke for the first time. If an expert feels nothing when reading about a conceptual discovery, it is usually a very bad sign, although one can come up with various exceptions.

Often quoted exceptions are some early papers in the great foundations-of-cryptography revolution of 1982, especially the Goldwasser-Micali-Rackoff paper on Zero Knowledge, which ended up appearing in 1985. What was special about that line of work is that it was not in the air, but, rather, ahead of its time. Obviously, I wasn’t there, so I don’t know, but I guess that people at the time were not saying “this work is obvious,” but rather “what the hell is this?,” which is quite different.

A final remark is that when a paper presents a new model or problem (and I understand that these are the kind of papers that the statement refers to), there can be no “intrinsic” value attributed the model or the problem; the value will be in the understanding and general progress that will come by studying the model and finding solutions to the problem, and how this will connect with different problems, different models, and applications.

There seem to be only two ways to validate a new conceptual proposal: one is to present preliminary evidence that one can do interesting things with it. (I think, in this case, too much emphasis is put on achieving quantitative improvement; I am impressed enough to see known, hard, results, recovered in a completely different way.) The other is the “gut feeling” of the expert, which feels that the new ideas are the “right” way to think about the issue at hand.

It seems right to reject a paper that fails both tests.

About these ads

17 thoughts on “Giving American Flags and Conceptual Contributions to Orphans

  1. I think that if something looks obvious after reading a new paper for the first time, then the paper is not making a valuable conceptual contribution.

    Smooth analysis is natural and straightforward, yet it is one of the most important conceptual contributions to analysis of algorithms in quite a while.

    the concept must have been “in the air.”

    If the concept was “obvious” and “in the air” how come no one else made reference to it or used it in any way?

    Either the concept has already been extensively used in which case is not new and can be safely rejected, or it hasn’t been used, in which case it is a novel and valuable contribution.

  2. Nice post, Luca.

    Alex, what the original paper did with smooth analysis is certainly not trivial. Of course, at a certain high level this concept, as any other, is trivialized. But if someone was trying to write a paper saying: “look we have this kind of idea, and don’t quite know what it’s good for, but hey, maybe it helps somehow with LP or some other optimization problems” — do you think they should’ve gotten credit for inventing the concept?

    Pursuing a new concept (idea) until it works or fails takes courage that we should reward. Putting it out there in conceptual form without a convincing result just means that the investment of courage is transeferred to the second paper. (Also see Luca’a older post on “the second paper,” which is kind of describing this phenomenon.)

  3. what the original paper did with smooth analysis is certainly not trivial.

    I agree, which is why I didn’t say “the paper on smooth analysis”. The paper is both conceptually interesting and technically difficult.

    My point is that the study of the distribution of the worst case instances in euclidean space is a conceptual breakthrough, even if it hadn’t been accompanied by the equally impressive result on LP.

    “look we have this kind of idea, and don’t quite know what it’s good for, but hey, maybe it helps somehow with LP or some other optimization problems” — do you think they should’ve gotten credit for inventing the concept?

    Yes, absolutely, though not anywhere as much distinction as with the actual paper, but pointing out this unexplored idea for the analysis of algorithms has clear scientific value and should be credited.

    Putting it out there in conceptual form without a convincing result just means that the investment of courage is transeferred to the second paper.

    We agree, which is why a purely conceptual paper in the case of smooth analysis would be of lesser value. Whoever takes the risky step should be rewarded.

    Interestingly, in the case of relativity the technical contributions by Lorentz and Poincare are considered of lesser value than the conceptual contribution that time is relative by Einstein.

    In this case the risky, valuable step was the conceptual one.

  4. You’re right that in some cases, the risky step may be the conceptual one. (Not that Einstein didn’t do hard-core technical stuff in his lifetime…)

    But I think we won’t see too much of that in CS, since we are not interpreting nature (where everybody has mis-concepts), but developing our own nature (the algorithms we study).

  5. You’re right that in some cases, the risky step may be the conceptual one.
    But I think we won’t see too much of that in CS,

    I’m not so sure. “GoTo considered harmful”? “polynomial = tractable”? “worst-case analysis (say as opposed to average case or adaptive analysis)”? “using asymptotics rather than exact analysis”?

    These are conceptual rather than technical contributions and all of them of great value. Some were “in the air”, others are duly attributed.

    Having said that, in general for any science good conceptual contributions should be 1 to 2 orders of magnitude rarer than good technical papers.

  6. Actually, I believe it has been “known” for a long time that adding random perturbations to the input of numerical algorithms seems to improve their condition. The real breakthrough of Spielman and Teng is that you can actually give a formal explanation for why this is the case, and for one of the most important algorithms of our time (simplex).

  7. Replace CS by TCS in my comment :) Many areas certainly have a lot of ideological debate (AI, programming languages etc), because their goals are very different from those of TCS.

    Looking at your TCS examples: worst case vs average case vs adaptive is still a very active issue. Worst case is not a concept, it’s something that has worked in a million examples, something we do regularly, but we also challenge regularly.

    We don’t challenge asymptotic analysis so often, but that’s because Knuth and people of that time already fought the battle. (Mind you, we de challenge it a lot for approximation factors, competitive factors etc). Again, asymptotic analysis is not a “concept” to put in STOC; it is a trend in the community that should and did take long to establish. It certainly doesn’t pass the manifesto’s criterion of “obvious once you’ve read the paper.”

    Finally, don’t get me started on polynomial = tractable…

  8. Actually, I believe it has been “known” for a long time that adding random perturbations to the input of numerical algorithms seems to improve their condition.

    The phenomenon had been observed empirically. They gave a precise definition and proved that under this definition hard instances for the simplex method are rare in a measure theory sense.

    A bad referee report would have read: “we knew this already”. A good referee report would have read: “cool, they formalized our intuition and proved useful results explaining our empirical observations”.

  9. if something looks obvious after reading a new paper for the first time… then the paper is not making a valuable conceptual contribution.

    I think there’s a slippery slope here — one piece of advice I have been given about writing (and inevitably fail to accomplish) is that no matter how hard you had to sweat to get a result, you should present it as simply as possible and to make it seem “obvious.” In the information theory literature I think there are several problems where the result seems obvious but it is a valuable conceptual contribution. Furthemore, there are cases where a new proof of an old (hence obvious) result introduces a conceptual simplification.

  10. I think Lance was “trolling” in the above post, meaning that he was saying something he did not really believe, for the sake of stirring a reaction.

    I always try to clean up and simplify a presentation as much as possible (“imagine if he didn’t try”, snarky people may say), I encourage my students to do the same, and it has worked out well. Perhaps part of it is that I work on problems where previous work is very complicated, and the reviewers are relieved, rather than disappointed, to read something understandable. (Indeed, I usually get the worst referee reports when, due to laziness and time pressure, I submit a paper that is more complicated than it needs to be.)

    Possibly it is different when one is trying to initiate something new, but my contention is that, when there is a valuable conceptual contribution, the reader will have a “aha!moment,” and the word that will come to mind is “elegant” and not “obvious.”

  11. I agree that the “obvious in retrospect” comment does not completely fit with the “conceptual” theme in the rest of the letter as people have understood it. This reflects a mixing of issues that makes the phrasing of the letter problematic. Here’s my take on what it really ought to refer to.

    There are two different kinds of “conceptual” contributions that are being conflated in the letter: those that impact the understanding of existing concepts and those that introduce new concepts. I think that the “is it obvious ONLY in retrospect?” question is a fair one with respect to contributions that impact the understanding of existing concepts. In this case, presumably, there should not be the issue of the short time to read the paper since these deal with existing concepts with which the PC members should have some familiarity.

    On the other hand, as you, James Lee, and others have pointed out, if the paper is introducing some new concept, downgrading one’s opinion of it because the results are “obvious in retrospect” is often perfectly legitimate, even if it is “ONLY” in retrospect. (Of course, it may be that the new concepts or results themselves are so compelling that the paper should be accepted even if the results are obvious in retrospect. ) If we restrict the test suggested in the letter so that it doesn’t apply to this class of conceptual contributions then I think it is OK but not otherwise.

  12. Paul,

    What is the rationale to reject a paper that is obvious “ONLY” in retrospect?

    If it is obvious only in retrospect those outside the program committee who haven’t seen it would remain unaware and more importantly unable to reproduce it.

    It seems to me that no scientific purpose would be served by keeping the paper under wraps.

  13. Alex: Why should anyone outside the committee care if the new concept isn’t intrinsically compelling?

  14. A concept can be obvious once explained yet compelling. For example the existence of transdichotomous algorithms is “obvious” once we declare the number of bits in a word not to be a constant, yet this observation is a source of many compelling algorithms.

    Another “obvious in retrospect” concept is the price of anarchy. If there is no central coordination it is only natural to expect a performance penalty as compared to the optimum solution which can make use of global information. Compelling? you bet!

    Conversely, a proof can be a technical tour de force, but otherwise a conceptual dead-end leading to no further developments, or even worse a technical solution to a very specific question of little relevance (I’m as guilty as anyone of occasionally solving a variant of a problem which in retrospect maybe didn’t need to be solved).

    Why would the paper introducing the price of anarchy be less meritorious than a proof that a specific, rather contrived model of network routing has a certain upper or lower bound on its price of anarchy?

  15. Alex: Maybe you parsed my one line comment differently from the way I intended it. I wrote “if” and meant “if”, not “whether”. If a paper introduces a new concept that isn’t intrinsically compelling and what it has to say about that concept is pretty straightforward then that seems like a perfectly good reason to reject the paper, even though the concept may be new. None of your examples, good or bad, are of this form. (Novelty of a concept alone does not equal merit; it ought be either non-obvious in retrospect or compelling in its own right. Even if you think that the price of anarchy or trans-dichotomous RAM ideas were obvious in retrospect, it was clear and you’ve argued that they met the compelling standard.)

  16. it ought be either non-obvious in retrospect or compelling in its own right.

    Then we are in agreement. Problem is when referees (under heavy time pressures) use non-obviousness as a proxy for compellingness. Generally these two are highly correlated but it is important to keep an eye out for when they are not, i.e. “obvious” concepts that are nevertheless compelling.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s