The Alternative to Resentment

A year ago, in a post entitled Anti-Complexitism, I tried to grapple with the strange phenomenon—one we’ve seen in force this past week—of anonymous commenters getting angry about the mere fact of announcements, on theoretical computer science blogs, of progress on longstanding open problems in theoretical computer science.  When I post something about global warming, Osama Bin Laden, or (of course) the  interpretation of quantum mechanics, I expect a groundswell of anger … but a lowering of the matrix-multiplication exponent ω?  Huh?  What was that about?

Well, in this case, some commenters were upset about attribution issues (which hopefully we can put behind us now, everyone agreeing about the importance of both Stothers’ and Vassilevska Williams’ contributions), while others honestly but mistakenly believed that a small improvement to ω isn’t a big deal (I tried to explain why they’re wrong here).  What interests me in this post is the commenters who went further, positing the existence of a powerful “clique” of complexity bloggers that’s doing something reprehensible by “hyping” progress in complexity theory, or by exceeding some quota (what, exactly?) on the use of the word “breakthrough.”

One of the sharpest responses to that paranoid worldview came (ironically) from a wonderful anonymous comment on my Anti-Complexitism post, which I recommend everyone read.  Here was my favorite paragraph:

The final criticism [by the anti-complexites] seems to be: complexity theory makes too much noise which people in other areas do not like.  I really don’t understand this one, I mean what is wrong with people in an area being excited about their area?  Is that wrong?  And where do we make those noise?  On complexity blogs!  If you don’t like complexity theorists being excited about their area why are you reading these blogs?  The metaphor would be an outsider going to a wedding and asking the people in the wedding with a very serious tone: “why is everyone happy here?”

Yesterday, in response to my reposting the above comment on Lance and Bill’s blog, another anonymous commenter had something extremely illuminating to say:

Scott, you are missing the larger socio-economical context: it’s not about excitement.  It’s about researchers competing for scarce resources, primarily funding.  The work involved in funding acquisition is generally loathed, and directly reduces the time scientists have for research and teaching.  If some researchers ramp up their hype-level vis-a-vis the rest of the community, as the complexity community is believed to be doing (what with all them Goedel awards?), they are forcing (or are seen as forcing) the rest either to accept a lower level of funding with all the concomitant disadvantages, or invest more time in hype themselves.  In other words, hypers are defecting in the prisoners dilemma type game scientists are playing, the objective of which is to minimise the labour involved in funding acquisition.

This is similar to teeth-whitening: in the past, it was perfectly possible to be considered attractive with natural, slightly yellowish teeth. Then some defected by bleaching, then more and more, and today natural teeth are socially hardly acceptable, certainly not if you want to be good-looking.  Is that progress?

I posted a response on Lance and Bill’s blog, but then decided it was important enough to repost here.  So:

Dear Anonymous 2:47,

Let me see whether I understand you correctly.  On the view you propose, other scientists shouldn’t have praised (say) Carl Sagan for getting millions of people around the world excited about science.  Rather, they should have despised him, for using hype to divert scarce funding dollars from their own fields to the fields Sagan favored (like astronomy, or Sagan’s preferred parts of astronomy).  Sagan forced all those other scientists to accept a terrible choice: either accept reduced funding, or else sink to Sagan’s level, and perform the loathed task of communicating their own excitement about their own fields to the public.

Actually, there were other scientists who drew essentially that conclusion.  As an example, Sagan was famously denied membership in the National Academy of Sciences, apparently because of a few vocal NAS members who were jealous and resentful of Sagan’s outreach activities.  The view we’re now being asked to accept is that those NAS members are the ones who emerge from the story the moral victors.

So let me thank you, Anonymous 2:47: it’s rare for anyone to explain the motivation behind angry TCS blog comments with that much candor.

Now that the real motivation has (apparently) crawled out from underneath its rock, I can examine it and refute it.  The central point is simply that science isn’t a Prisoner’s-Dilemma-type game.   What you describe as the “socially optimal equilibrium,” where no scientists need to be bothered to communicate their excitement about their fields, is not socially optimal at all—neither from the public’s standpoint nor from science’s.

At the crudest level, science funding is not a fixed-size pie.  For example, when Congress was debating the cancellation of the Superconducting Supercollider, a few physicists from other fields eagerly jumped on the anti-SSC bandwagon, hoping that the SSC money might then get diverted to their own fields.  Ultimately, of course, the SSC was cancelled, and none of the money ever found its way to other areas of physics.

So, if you see people using blogs to talk about research results that excite them, then instead of resenting it, consider starting your own blog to talk about the research results that excite YOU.  If your blog is well-written and interesting, I’ll even add you to my blogroll, game-theoretic funding considerations be damned.  Just go to WordPress.com—it’s free, and it takes only a few minutes to set one up.

67 Responses to “The Alternative to Resentment”

  1. lylebot Says:

    Do you agree with the implied premise that most of those comments are coming from researchers outside of TCS? I’ve actually been assuming that many of them are from other TCS researchers…

    (I’m a computer scientist competing for federal funding, but I’m not a TCSist. Personally I love to read about the kind of stuff you post—I probably wouldn’t hear about it otherwise, it is genuinely exciting, and it has changed (for the positive) the way I see some things in CS. I’ve talked to colleagues that read your blog and feel the same way.)

  2. coffeemug Says:

    Perhaps people become angry because this particular blog is well-written and technically sound. It’s easy enough to start a blog that is incomprehensible and succeeds very little in communicating ideas. In general, the more successful something is, the more it gets attacked. And also in general, the vocal minority of dissenters takes up much more of the comment space than the readers who find it uncontroversially interesting, or even the ones who might have slight disagreements but just don’t care to invest energy into a comment.

    Some of the backlash might just be an annoyed reader saying, “Ugh. Just because I can’t write a blog that communicates as clearly or as regularly doesn’t mean TCS should be popularized more than the stuff that I think is important.”

    I think that’s a silly point of view, but probably this bias is coming through somewhere in there.

  3. Aram Says:

    Could be selection bias: I rarely leave comments on posts where my reaction is “I generally agree. Thanks for the sensibly-written commentary!”

    The fixed-size pie fallacy applies in a lot of places, e.g. in international health, there is proportionally more funding for AIDS than for childhood diarrhea and pneumonia. In part, this is because AIDS can better capture the imagination of Western donors. But defenders of the AIDS funding argue that this money was essentially new to international health, and that AIDS advocacy grows the pie. I think they’re probably right, but it’s not completely obvious.

    Another example with different politics: our Libya spending didn’t result in proportional cuts in our Afghanistan, Iraq, Yemen, Pakistan, etc. spending.

  4. Gary Says:

    I generally agree. Thanks for the sensibly-written commentary!

  5. BBT Says:

    Picture a group of scientists trying to break down a wall (call them Leonard, Sheldon, Howard and Raj), and after twenty years of trying all sorts of tricks, they haven’t even scratched the surface. Then one day a couple of new researchers walk in, try a new idea and _finally_ make a minor scratch on the surface of the wall. There are, of course, high-fives all around as well as victory dances, and a big celebration ensues.

    Then a researcher outside the field (call her Penny) walks by and asks “what is all this about?”. Leonard says “we’ve been trying to break this wall and we just made a scratch on it” (cue in a wide Leonard grin here). Penny looks at the small scratch, shrugs her shoulders and walks away.

    Both attitudes are reasonable: the enthusiasm of progress after years of fruitless labor and the calmness of the bigger picture view of “but still we haven’t moved very far”.

    There is no reason to take offense with either comment, and I’m surprised how much each side personalized their point of view in this discussion, rather than trying to understand what the other side is saying.

  6. Timothy Gowers Says:

    I think that one reason for the reaction to the post on the exponent for matrix multiplication is that the excitement-worthiness of mathematical results is not a linear scale, but more like a partial ordering. From what I understand (after reading not too carefully your post and that of Dick Lipton) the new result doesn’t introduce a fundamentally different method (though it does introduce highly non-trivial new systematic ways of dealing with existing methods), or have any practical effect on all those algorithms that need matrix multiplication. However, it is a breakthrough in the rather literal sense that there appeared, after twenty-five years, to be a barrier, and that has now been broken through. That last reason is a perfectly legitimate reason to get excited, but the first two reasons are legitimate reasons not to overdo the excitement (which I don’t think you did, by the way). If mathematicians had fifty words for breakthrough, this discussion would never have arisen: we could just call the result a very exciting breakthrough of type 3 with a certain amount of type 1 interest and the possibility of some type 2 interest in the future, or something like that. As it is, when you use the word “breakthrough”, some people enthusiastically agree and others are not so sure, but they are talking about different things.

    As should be clear from that, if you just ask the question, “Was the level of excitement about the new exponent for matrix multiplication reasonable?” then in my view the answer is that it obviously was. I also agree that it is ridiculous to criticize outreach activities: we should be all be doing what we can to communicate what is going on in our fields, and if there is some competitive pressure to do so, then that is all to the good.

  7. Lev Reyzin Says:

    I don’t think that the angry comments are from people misguidedly competing with the complexity theorists for funding. Anonymity and distance cause people to behave strangely and write things on your blog that they would never consider saying in person.

    Also, anonymously complaining and writing insults is much easier (and to some people more fun) than having a thoughtful blog…

  8. Anonymous Says:

    I think you have to distinguish between outreach aimed at the general public and communication happening within the field of CS/TCS:

    (1) We probably mostly agree that it is very important to have outreach to the general public about the excitement and value of science. This can increase both the overall funding for science and the number of people who want to do science.

    (2) But I can see how someone could view complexity-related announcements on your blog as being communication inside CS, rather than directed to the general public. In so far as such a person sees these kinds of announcements as efforts to build buzz/hype about complexity results *solely/primarily inside computer science*, then it might be reasonable for them to worry that this will effect how the limited NSF budget for CS is distributed — with more money going to TCS/complexity because the impression has been created that TCS/complexity has more exciting results/progress.

    In fact, I think people doing science outreach often make an effort to argue for the broad utility/excitement of the whole scientific endeavor, rather than just their favored sub-field, in part to make it clear that their goal is entirely (1), and not to engage in (2).

  9. ano Says:

    Are the nasty comments coming from
    (1) people inside theory CS (who are somehow unhappy with TCS, or blogs, or something),
    or
    (2) people outside TCS?

    If you’re convinced that it’s (2), then one theory is that *you* are to blame for writing so well. (And Lance, and Lipton.) There aren’t such good blogs in other areas, and people can’t resist reading your blog even though they’re not interested in complexity theory, etc. :-)

    Seriously, though, before you feel disheartened by the bad comments, you should keep in mind that the majority of readers don’t leave comments, but they’re grateful for your efforts and benefit from it (which is why they read). Google Reader alone says your blog has 1,033 subscribers through Reader, and there must be many more who are reading it through other means. So don’t let the half-a-dozen anonymous trolls get you down.

  10. Scott Says:

    lylebot #1:

      Do you agree with the implied premise that most of those comments are coming from researchers outside of TCS? I’ve actually been assuming that many of them are from other TCS researchers…

    Yeah, I also suspect that many of them are people within TCS (or related areas of math), who feel that their own subfields are being slighted by the current TCS blogs, and who choose to respond not by pitching their own blog-tents but by egging the existing ones.

  11. ano Says:

    Anonymous #7: do you think the NSF budget is distributed based on the contents of a blog called “Shtetl-Optimized”?!

  12. Jay Gischer Says:

    Jealousy isn’t limited to TCS or even CS, and competition for funding isn’t necessary to foster it. Simple attention is enough.

    However, jealousy is an important signal. If you feel jealous of someone, it’s very likely that you need to do something different in your own life.

  13. choncan Says:

    I’m hesitant to push this too far, because I know I’m in hand-waving grand-social-theory territory, but I think it is just the case that some percentage of the internet commentariat in general, across subjects and interests, peruses the web these days in service of some particular psychological affectation or other that is convinced that there is a grand conspiracy of the fake experts lording their phony expertise over the common man. Each member of this crowd eventually comes across a subject or field or community that they think they can see right through and expose for the nonsense it is, and some sort of downward-comparison psychological superiority is derived from the process. Any area host to periodic debate or back and forth of any kind seems to work best for these purposes. The obvious example I’d cite in the modern world is economics. No doubt one can quibble with the empirical validity of much economic theorizing, but I’m not talking about comments on some technical post about some equilibrium condition, or about the interpretation of some model. It seems like an economist can make a post discussing the observation that often times newly married couples seem to invest more heavily in childcare products, and some internet scholar will chime in with “yeah that’d be fine if economics weren’t BULLSHIT!!!!!!!!!!!!!!! STOP LYING TO THE PUBLIC, TRAITOR!!!!!!!!”

    Think also of people making similarly-toned comments on climate change posts, or string theory, or the popularity of books like that “end of science” book and so on. I really do think there’s an aspect of it where experts talking to other experts about a technical subject functions as some sort of insanity magnet, attracting people who’ll comment, at varying levels of coherence, “I see what you’re up to with your jargon here, your scientism, you charlatans, but you can’t fool me, I see right through you!” (Andrew Gelman some days ago made a throwaway post about how he’d written down rah-rah type buzzwords uttered in some meeting he was in, and one of his intrepid commenters said, “Yeah, well, it’s not like you don’t do the same thing!” and listed such similar buzzword jargon as “expectation” and “variance”. So, yeah.)

  14. anon Says:

    There are different kinds of anonymous commentators on complexity blogs, so let me clarify that I am of the kind that are completely in favor of getting excited about nice results in complexity. My disagreement was about what I would consider a break-through. I agree with Gowers. My sense of “break-through” differs from yours. If you stated “a break-trough in my opinion” or used “interesting”, “exciting”, and “very nice” in place of “break-through” I wouldn’t feel the urge to comment in disagreement at all. I forgot that regardless of its popularity, it is still a personal blog. Anyway, sorry for not being sensitive and careful in expressing my disagreement.

  15. Anonymous Says:

    Tim Gowers has written a good response. Scott, your plug for the new result had no nuance, they are your friends, and you are by your own admission not an expert on the topic. You were aggressively negative in a recent post on some other people’s work which you are an expert on. It appears to me that you are not willing to even give a nanometer to the possibility that part of your excitement is proximity to the people in question. All this does not matter really – it is your blog after all. However, you should not be completely surprised nor fail to understand why some including reasonable people who admire you were bit less enthusiastic about the whole business.

  16. Anonymoose Says:

    Scott: You never responded to commenters on why you say that Stothers “discussed an improvement” while Williams “released a breakthrough paper”. You have to admit that its a little strange to paint the contributions this way before reading them. A cynic would point out that it’s easy to guess which of those two people is your good friend.

  17. anon Says:

    To complement what Scott wrote, Lance and Bill’s Complexity blog accepts guest posts, so if anyone in TCS feels that one of their friends has a nice and exciting result in TCS, they should write a blog post about it and send it to Lance and Bill.

  18. Scott Says:

    Anonymous #14:

      Tim Gowers has written a good response. Scott, your plug for the new result had no nuance…

    Well, at least we agree about liking Gowers’ response. :-) Let’s look at what he actually concluded:

    if you just ask the question, “Was the level of excitement about the new exponent for matrix multiplication reasonable?” then in my view the answer is that it obviously was.

      You were aggressively negative in a recent post on some other people’s work which you are an expert on.

    Dude, I have no idea what you’re talking about here. If you mean Pusey et al.’s “The Quantum State Cannot Be Interpreted Statistically,” then I plainly wasn’t “aggressively negative” about it: rather, I spent hours trying to explain what I found new and interesting in that paper. Indeed, Lubos Motl, who was aggressively negative, vociferously attacked me (calling me a “mad engineer” and an “anti-quantum-mechanical crank”) for refusing to say the paper is rubbish (which it’s not). Yet another example of how I can’t win…

  19. yie Says:

    I wasn’t originally going to comment, but since _you’re_ still posting
    about it I guess you’re a glutton for punishment. Or something…

    Anyways, the thing that I found off-putting about your post (which echoes bits from the Ryan William’s announcement) was the tone. While the vast majority of your postings come off as good natured, this one seemed a little “Oh look my bestest friend (and me, in case you’d forgotten) is smarter than you!”. I’m not questioning that–but it’s one thing to be celebratory and another to rub everyone else’s noses in it.

  20. yie Says:

    er, kill that extra apostrophe in Williams.

    I guess the thing that I didn’t make explicit was that, in general, I think you do a superb job of explaining stuff in a way that’s accessible yet not condescending, and somehow for me that ‘not condescending’ part was missing.

  21. Anonymous Says:

    I’m CS, but not TCS. Keep doing what you are doing – it is helping those of us on the periphery of the field keep up without having to slop through journals. My only complaint is that you don’t post often enough :)

  22. Luca Says:

    Before addressing the premise that funding is a zero-sum game, which is incorrect, I think that one should address the premise that NSF funding is influenced by what is written in blogs, which is preposterous.

    Also, I am very excited that an improved algorithm for matrix multiplication is now classified as “computational complexity.” Now that my field has achieved total domination of theoretical computer science, I think that we should move on to include AI too in computational complexity.

  23. Mitch Says:

    Yie said

    “but it’s one thing to be celebratory and another to rub everyone else’s noses in it.”

    I didn’t get that at all from Scott’s post but I think part of the reason the post might have had a more celebratory tone than usual is that a dry proclamation of this result would read like an Onion article: “Mathematicians discover that something they thought was atleast 2.374 can actually be as low as 2.373!!!” Using some slight tounge in cheeck humor (lightning fast etc) was (imo) a good way for Scott to convey the importance of the result to a non CS audience.

  24. Scott Says:

    Anonymoose #15:

      You never responded to commenters on why you say that Stothers “discussed an improvement” while Williams “released a breakthrough paper”.

    I’ve changed it, and I apologize. I was trying to reflect the fact that one author communicated her result effectively (by writing a paper with the property that experts who read the paper would reliably understand what she did), and the other did not. To me, that’s an absolutely enormous difference—much, much larger than the Monday-morning quarterbacks of science will ever realize—and something whose importance can’t possibly be stressed enough to students.

    On the other hand, after corresponding with Andrew, and realizing how his failure to communicate might’ve been due to health and job issues, as well as lack of good advice from the people around him, I also felt bad about using him as an example to harp on this point, despite its importance. So that’s what I apologized for.

    But enough about this—really!

  25. yie Says:

    @Mitch:
    That’s just what threw me off – even as I first read the post I saw the bold red “lightning fast” and knew the improvement was going to be, like Tatooine, in a decimal place far, far away.

    Despite all that, it just didn’t work for me in a way that most of Scott’s writing does, and I guess some other posters might have had similar reactions. Maybe I’m just not getting enough sun these days. =)

  26. Scott Says:

    yie #18:

      While the vast majority of your postings come off as good natured, this one seemed a little “Oh look my bestest friend (and me, in case you’d forgotten) is smarter than you!”

    See, this is a perfect example of how I write one thing, and what enters some other people’s heads is very, very bizarrely different. Maybe someday, if I see enough examples, I’ll be able to PAC-learn the transformation that’s being applied.

  27. Scott Says:

    Luca #20:

      I am very excited that an improved algorithm for matrix multiplication is now classified as “computational complexity.”

    To be fair, I think there are many hardness results—for example, NP-completeness for problems in scheduling, computational geometry, etc.—that can reasonably be classified as “algorithms research,” since what people really cared about was solving the problem faster in practice, and NP-completeness is mainly interesting insofar as it’s a barrier to that.

    Conversely, I think there are certain algorithmic results—for example, algorithms for Unique Games, or post-Strassen matrix multiplication algorithms—that can reasonably be classified as “complexity theory,” since there what people really care about is the lower bound, and (as in Sipser’s joke) the algorithms are mainly interesting insofar as they’re barriers to lower bounds.

  28. Mike Says:

    Scott,

    I usually really just hate everything you write, but I thought the Vassilevska Williams post was excellent!! ;)

  29. Ellie Kesselman Says:

    Comments from @anon #13 and @Anonymous #14 are very good. (There are so many variants on Anonymous here I feel like I’m on Twitter). Let’s do this out of order. @anon and @Anonymous both raise the point that this is YOUR blog, Scott. You are a courteous host to those who participate, but as you can see, nuances can be lost along the way.

    Next: If you choose to voice an opinion, you risk the chance of being called an “anti-quantum mechanical crank”. That was harsh, certainly. But every expert, whether the field is economics (Ph.D. economist personal blog comments can be vicious, while highly eloquent), Comp Sci (vicious w.r.t. “the programming language wars”) or even Mathematics will be ruffled if original work is perceived to be unjustly criticized.

    Your good-humored tone is quite wonderful, and differentiates your blog from others. It permeates your writing at the Shtetl of Math. I am Ashkenazi. I can say that with impunity, and respect for you in my heart. Now stop apologizing, enough is enough already. And no more with the Yet another example of how I can’t win… woe-ist-me. Just go back to doing what you were doing, after some internal reflection on the words of @anon, @Anonymous, @Anonymoose and @ano who all love you. And @lylebot too. Such a nice comment, from another field entirely! I’m from mathematics, just not as highly degree’d as the adepts here. Nor as adept.

    Penultimate thought: NSF funding probably IS influenced by blog content. I doubt it is assigned a weighting or mentioned explicitly in grant evaluation criteria, but it has some influence, I suspect.

    Last: My perception is identical to that expressed by choncan, see comment #12. The circumstances causing that behavior (won’t even guess about that!) will not dissipate any time soon. If I were you, I would be psychologically prepared for such.

    P.S. Scott, are you referring to Andrew Gelman having health and job issues in your comment #22? (I did a word search on this post for “Andrew” which led me to wonder that). I hope not, as he is so bright, productive, congenial.

  30. Scott Says:

    Ellie Kesselman #27: No, Andrew Stothers.

  31. Thomas Says:

    Game theory is NOT the right framework to capture the activities of living, thinking, social beings.

    Iterated game theory might stand a better chance, as one might have expected, considering that our activities and relationships are … iterated over and over again..dah

    Now it turns out that in iterated game theory the prisonner’s dilemna that seems to be the only inspiration of “Anonymous 2:47″ can, and does lead to very different equilibria:

    “Although the Prisoner’s dilemma has only one Nash equilibrium (everyone defect), cooperation can be sustained in the repeated Prisoner’s dilemma if the discount factor is not too low, that is if the players are interested enough in future outcomes of the game.” (http://en.wikipedia.org/wiki/Repeated_game)

    See also Axelrod’s nice experiment (http://www2.econ.iastate.edu/classes/econ308/tesfatsion/axeltmts.pdf).

  32. D. Eppstein Says:

    yie: I think you need to read http://abagond.wordpress.com/2010/07/24/the-tone-argument/

  33. Mitchell Porter Says:

    Scott: “consider starting your own blog to talk about the research results that excite YOU.”

    Coincidentally, I did that, just the other day!

  34. anonymous Says:

    I think the most incriminating aspect of this complexity-self-promotion controversy is the fact that complexity theorists are touting Vassilevska’s result as a complexity result. Stop it. Give credit where credit is due: this is an algorithms result, and algorithms research deserves the PR boost, not complexity. A glance at Virginia’s page reveals that most of her research can be more aptly characterized as algorithms rather than complexity, and this is true of this result.

  35. just some confused passer-by Says:

    Just thought another “bizarrely different” reaction might be interesting, from a physics PhD student who has read this blog a few years now but otherwise knows absolutely nothing about complexity theory. This is pretty embarrassing to admit, but…

    I honestly thought that the original post was a joke post. I thought it was an amusing piece of characteristic dry humour, hyping some very minor result (obviously by a very good friend who was in on the joke). When I read things like “breakthrough” and “I had a hell of a time keeping the secret”, I took them to be sarcastic! So for me this really was an Onion article, and the “lightning fast” bit fitted the general tone.

    Why did I misinterpret this so badly? Because I am completely ignorant about the subject, had no idea about the relevance of the bound to other algorithms, and just saw a number being changed at the third decimal place.
    I genuinely read about the first twenty comments in this spirit, thinking everyone was playing along. Feel pretty stupid looking back now!

  36. Scott Says:

    anonymous #32:

      I think the most incriminating aspect of this complexity-self-promotion controversy is the fact that complexity theorists are touting Vassilevska’s result as a complexity result.

    As I explained in Comment #25, I think today’s fast matrix multiplication algorithms can reasonably be thought of as “complexity theory”—and certainly the anti-complexites on the blogosphere haven’t hesitated to consider them as such! But just for you, I changed “computational complexity theory” to “theoretical computer science” in the OP—happy? :-)

  37. ano Says:

    It is natural that some people read the original post and were not as excited as you were. What I don’t get it is why it spurred them to make nasty comments. We’re all quirky people who get excited about different things (many of which are of no interest whatsoever to others). But why should someone being excited about something only he cares about (say) and expressing his excitement on a personal blog that exists for this very purpose, be a cause for others to rant?

  38. ESRogs Says:

    The comments on this blog are so weird.

    As a practicing programmer who remembers learning in compsci undergrad that the best known exponent for efficient matrix multiplication was some strange number between 2 and 3, I can report that hearing that the bound had been improved was quite interesting — it’s fun to read your posts and feel like I’m keeping up with what’s going on in the field a little bit, even though I’ve been out of school for a few years.

    Please keep communicating results to the public!

  39. Scott Says:

    Aram #3:

      Could be selection bias: I rarely leave comments on posts where my reaction is “I generally agree. Thanks for the sensibly-written commentary!”

    LOL, yes! In fact, when I do get comments like that, they’re usually comment-spam with a link back to some online gambling site. This thread has provided some welcome exceptions, for which I’m genuinely grateful.

  40. coo Says:

    I generally agree. Thanks for the sensibly-written commentary!

    I humbly urge other readers to post positive feedback comment: since Scott wants to PAC-learn the reactions to its posts, the selection bias put the problem in the bandit setting. By expressing ourselves we should be able to recast it into the fully supervised setting, thus lowering quite a bit the sample complexity of the task.

  41. Paul Carpenter Says:

    Okay here’s me being a little dim witted and a little off topic but there’s a lot of comments saying “oh come on, the blog is called Shtetl-optimized” – could someone please explain the joke of the title to me?

  42. Bram Cohen Says:

    In defense of calling the result a breakthrough, progress had been held up for a long time because going from the second to the third tensor actually makes things worse, while jumping to the fourth tensor results in an improvement. This makes the implied claim of ‘we knew we could get such a result all along, and just didn’t do the busywork of finding it’ seem even more dubious than the 20-year span in which that didn’t happen does. To my mind, the arduous technical work in this result is something to be applauded, not sneered at as mere engineering work!

    Compare this with the reception of Selberg’s proof of the prime number theorem using classical methods. It was hailed as a great breakthrough at the time, but decades later it’s become pretty clear that restricting yourself to classical methods doesn’t make proofs any more insightful, it just makes them longer and more difficult to find.

  43. GASARCH Says:

    1) Thanks for the comments on my blog and for this post!

    2) The funniest comment indicated that we bloggers all
    work together like a shadowy conspiracy. I don’t even
    coordinate with Lance!

  44. Scott Says:

    Paul Carpenter #41: Not even I get the joke. :-)

  45. anonymous Says:

    This is anonymous #32 in response to Scott #36. Yes, that is much better, thank you :-). That being said, I’d like to point out that your opinion in comment #25, describing how such results can reasonably be thought of as complexity, is a very biased personal opinion, and I claim it is more controversial than you think. Of course, this is your blog, so you are free to classify any research in the world as complexity, but know that many would consider that unreasonable — certainly in this case. I think a strong argument can be made that many — if not most — researchers in computer science care more about how fast one can multiply matrices, rather than how fast one can’t multiply matrices. Those researchers aren’t so much interested in the lower bound like you claim. It seems to me that you, as well many of your complexity theory colleagues, like to cherry pick what you classify as complexity theory based on how fundamental the research is: when proving problems were NP-hard was “vogue” and “new”, it was complexity; as soon as it became routine it was ostrasized as algorithms research. When an algorithmic problem is fundamental, any progress — positive or negative — is referred to by a complexity theorist as complexity, in an obvious and disingenuous attempt to plant a flag all important progress in TCS. The only objective classification scheme that I can think of, though imperfect, is that upperbounds are algorithms and lowerbounds complexity.

  46. The Meaning of Omega « Gödel’s Lost Letter and P=NP Says:

    [...] the reaction it has. We agree with, and have tried to extend, Timothy Gowers’ comments here. As for how these values can be invested, only time will be the [...]

  47. Peter Boothe Says:

    You may be overthinking this. I suspect that the high amount of negativity you see is largely due to John Gabriel’s Theory. I, for one, don’t contribute much, largely for the same reasons as Aram.

  48. Scott Says:

    anonymous #45: There’s an amusing irony in what you write. Here and elsewhere, we’ve seen numerous commenters saying some variant of “ha ha, those silly complexity theorists, getting all worked up over an improvement of 0.003 to some exponent, even though any real computer scientist knows the resulting algorithm is of no practical use whatsoever!” So then what happens when complexity theorists try to adopt such an unwanted intellectual orphan? They immediately get accused of stealing it from the rest of CS!

    My own preferred division is simple and, I think, closer to current sociological reality. “Algorithms research” is about solving important computational problems faster, while “complexity research” is about understanding the inherent capabilities and limits of computation. As a result, algorithms researchers tend to care more about upper bounds, and complexity theorists more about lower bounds—but that’s by no means a hard-and-fast rule, especially when we remember how many lower bounds contain algorithms at their core, how many algorithms were discovered by trying to prove lower bounds, etc. By their nature, the two fields overlap a great deal, are worked on by many of the same people, and can never be cleanly separated. But to whatever extent we can separate them, I think it’s on the basis of goals, not of O() versus Ω().

  49. plm Says:

    I am quite happy to see here attempts to use mathematical modeling used to make points in social science.

    And similarly I am a little unhappy to see the post eventually dismiss that use of modeling and revert to intuitive/qualitative evaluation, which concluded the post.

    I find arguments on all sides quite insightful but I feel they come short of allowing us to decide confidently what to do.

    Hopefully next times modeling efforts will go further, and perhaps reach the conclusion.

    I think scientists’ blogs are a good place to show the value of scientific education and research, to display to the public that scientists can decide better thanks to what was invested in forming them and having them develop our knowledge, research, thereby justifying further investment and listening to their advice.

  50. anon Says:

    The more I hear you get upset over this, the more I imagine you as this guy: http://xkcd.com/386/.

    Long story short, don’t expect too much from these tubes, or it will ruin your life.

    That said, please don’t stop blogging. Or become cynical. You’ve convinced me that this is one of the most interesting fields in science today, and that is as a complete layman.

    Cheers

  51. Scott Says:

    plm #49:

      I am quite happy to see here attempts to use mathematical modeling used to make points in social science. And similarly I am a little unhappy to see the post eventually dismiss that use of modeling and revert to intuitive/qualitative evaluation, which concluded the post.

    Honestly, I don’t see how the original comment differed in the slightest from my response to it in the use of “mathematical modeling.” The commenter asserted without argument that science is a Prisoner’s-Dilemma-type game, where “hypers” are the defectors and people who keep quiet about research advances in their fields are the cooperators. I gave examples to illustrate my view that science is actually an extremely different type of game. Neither of us made any attempt at serious social science, or for that matter made any nontrivial mathematical arguments. Why, then, was the original comment an “attempt to use mathematical modeling to make points in social science,” whereas my response was “intuitive/qualitative”? Are you mistaking cynicism for intellectual rigor? :-)

  52. plm Says:

    Scott #51:

    I could probably write more to the point, apologies.

    Modeling is a many-faceted activity.
    It may be routine and obvious, as for engineers or architects using CAD software.
    It may be clearly necessary, as in a physical problem, e.g. writing a differential equation for a pendulum (though this was probably not clear before Newton).
    It may also be psychologically difficult to accept. E.g. if we know that those CEOs are earning too much why would we try to quantify the benefits of compensation inequalities across different jobs? Or if we know that science outreach is good in any form to any extent, in any circumstances why bother?

    The original poster probably first thought he was right and then tried to justify himself. I often feel this. Yes rigor may be a consequence of cynicism here, but I think there is at least some rigor and that is what I appreciated.
    And perhaps (s)he was wrong and you are right, but I like rigor.

    In the present case, it seems to me that simply mentioning game-theory is highly evocative and not so obvious (you said it was illuminating). It could have been done without referring to an actual mathematical theory (game theory), but this would not have the same impact, on scientists, like you, trained in game theory, and mathematically cultivated.

    I think I remember an article on Terence Tao, where it was mentioned that his mother told him to “try a quadratic” to evaluate a periodic continued fraction and he instantly found the answer.
    I also think there is a MIT joke regarding how when Wiener asked for explanation of a formula and was given just that same formula he replied “Nice, I hadn’t thought of that.”.
    There’s also Deligne’s coat of arms.
    And in general we know (?) that a short proof does not imply that a result is easy.

    Anyway, the concept of a game is “mathematical”, the idea of Nash equilibrium too, it is elegant, it speaks to our scientific skills.

    I like rigor, probably because it reassures me, it allows me to understand that I am wrong, accept it.

    Blogging, handling comments at least, can be taxing psychologically so if it is felt as an outreach duty, and a competition on top of that… I have not analyzed the issue thoroughly, and I do not know who is right, but I can see why some react defensively.

    I rather agree with you on the question of blogging and outreach, but I am reluctant to say you are right, because the attitude of assuming things are obvious when no careful analysis has been carried out has deep implications IMO, and I suspect such assumption is in your interest -what comes to mind maybe wrongly: laziness, it was your first stance, you are a longtime blogger, an optimistic/enthusiastic attitude which I and many appreciate, but not so compatible with some kinds of rigor.

    I will stop here though I am not sure I said what I should have, I hope you find a useful idea in my narcissistic speech.

  53. Scott Says:

    plm #52: Thanks for the interesting clarification.

    I guess I belong to a culture where people describe social situations using game-theory concepts so routinely (equilibrium, chicken, prisoner’s dilemma, defection, zero-sum, payoff function…), that it no longer impresses me as very novel. When I said the original comment was “illuminating,” I meant because of its remarkable candor and its insight into some commenters’ thought processes—not because I regarded the idea of comparing science to a prisoner’s dilemma as non-obvious.

  54. Nilima Says:

    Scott, I admire the clarity of exposition and arguments on your blog. I read it regularly precisely because your blog reflects both (idiosyncratic? \footnote{I don’t work in TCS/complexity}) taste in science. If one wanted carefully caliberated and inoffensive recreational reading, one may wish to stick to the AMS Notices. With young kids in our house, my husband and I had to find inexpensive and convenient substitutes for dinner on the town. So we read your blog together once the kids are asleep (someday we’ll revert back to going out instead).

    I must now admire your graciousness with this whole discussion. Fast matrix computation results are cool. If someone isn’t stoked about this, tough.

  55. Nilima Says:

    edit:I read it regularly precisely because your blog reflects both (idiosyncratic? \footnote{I don’t work in TCS/complexity}) taste {\it and enthusiasm} in science.

  56. Scott Says:

    Nilima #54:

      If one wanted carefully caliberated and inoffensive recreational reading, one may wish to stick to the AMS Notices.

    Uh, I’d be careful with that—did you see Neal Koblitz’s AMS Notices piece attacking much of modern cryptography? :-) (See also the letters in response.)

  57. Nilima Says:

    Scott, yes, I remember that tempest. But such entertainments are few and far between in the Notices. Mostly, though, the Notices provide the equivalent of comfort food. Nutritious, lovingly prepared, and guaranteed to not upset.

  58. plm Says:

    Nilima #57:

    I take the opportunity to add on the wonderful Notices of the AMS (http://www.ams.org/notices):
    For emotional issues I refer in particular to the “Letters to the editor”, recently there was discussion about music modeling, time-frequency analysis of music, topical bias in journals, the free will theorem, and they regularly discuss mathematical education and general policy, and mathematics and society (e.g. math and nazism), and mathematics outreach (Numb3rs, blogging, mathoverflow).

    Scott #53:

    Thanks for the clarification.

    Actually the choice of the prisoner’s dilemma puzzled me a little, because I associated it with negative payoffs for all strategies, but I thought there had to be similar games with positive payoffs, and even if the choice of game was not ideal, just introducing the game concept allowed mathematical variations, putting numbers, and calculating, testing our intuition.

    I procrastinated going to wikipedia, I have now and I was again surprised by the quality of the following articles:

    http://en.wikipedia.org/wiki/Prisoner's_dilemma
    http://en.wikipedia.org/wiki/Stag_hunt

    The prisoner’s dilemma examples in economics section (the part on advertising) is perhaps the most relevant to the current discussion.

    I hope you find them interesting too. I plan to read more of them and their references -apparently those topics are still researched, and I guess any particular application has its own issues requiring further thinking.

  59. Rocky Says:

    The best reaction to negative and judgmental types is to feel compassion for their problems with anxiety. It’s not worth feeling any negative emotion in response.

  60. Slipper.Mystery Says:

    I accept this blog as one person’s opinion about what’s fun or interesting, nothing more nor less, and will eagerly be among those who beg the blogger to continue after every periodic threat to shut down, because it remains both entertaining and informative to read.

    In the interests of accuracy, however, it is important to correct the following (oft-repeated) misapprehension:
    As an example, Sagan was famously denied membership in the National Academy of Sciences, apparently because of a few vocal NAS members who were jealous and resentful of Sagan’s outreach activities.

    NAS membership is typically granted not on the basis of outreach activities, it is granted for research activities. Sagan did a great service to science and to the public, but his core research record was not very impressive. If you were on the subcommittee making the recommendation and recognized this as the case, how would you have voted? Even your terminology “denied membership” suggests this was some inalienable right, or perhaps that he was being excluded from some country club because of his ethnicity.

    Suppose your senior colleagues assessing your tenure case in a year or two conclude that your research is not sufficiently substantive (we hope that won’t be the case of course), and someone points out that perhaps your time spent doing public outreach via this blog took away from time you could have been doing research. Should the subcommittee unilaterally change the guidelines to accommodate you on the faculty? And if not, should its members be accused of being jealous and resentful of your outreach activities?

    In fact, lost in all the hand-wringing about the alleged inherent bias against popularizers, is that the NAS did find a way around this impasse. Two years later, when he was awarded the Public Welfare Medal, the highest NAS award, for “distinguished contributions in the application of science to the public welfare,” it came with all the perqs of NAS membership, so indeed he was to all intents and purposes a member ever since. But this happy outcome doesn’t play as well as the version you’re repropagating, in which the mean nasty scientists were jealous of him because he was more popular, and forever shunned him.

    Apologies if this strikes yet another raw nerve…

  61. Scott Says:

    Slipper.Mystery #60: I’m well aware that NAS membership is supposed to be for research. The problem is that there have been many, many NAS members whose research records were much less distinguished than Sagan’s! Furthermore, if you read what actually happened (say, in the two Sagan biographies), it wasn’t a hardheaded evaluation of his research activities in planetary science, setting aside his popular work—there were passionate denunciations of his popular work.

    And, yes, the NAS realized afterward that it had egg all over its face—that its decision had damaged its own reputation without affecting Sagan’s—and tried to recover.

    As for “mean, nasty scientists”: well, the scientific community is large and varied, and contains the full spectrum of humanity, I would say with the good outweighing the bad. I think it’s completely unfair to judge the entire scientific community by the NAS, which (like certain blog comment threads!) has seemed to showcase some of the scientific community’s lowest, pettiest impulses in concentrated form.

  62. Slipper.Mystery Says:

    Scott #61: We agree that a) the “fixed-size pie” model is silly and false, b) that the .003 improvement was worth highlighting, that VVW wrote a beautifully clear intro, and that Stother should not have let his .002′s worth slipped through the cracks, c) being excited about one’s research and promoting it to the general public is an unmitigated positive.

    > I’m well aware that NAS membership is supposed to be for research. The problem is that there have been many, many NAS members whose research records were much less distinguished than Sagan’s!

    Easily asserted, more difficult to document. (As a thought experiment, employ that past precedent criterion to select your next research student.) Though it originally aired before you were born, there were impartial concerns that “Cosmos” crossed the line from communication of science to self-aggrandizement (and there is an issue when the presenter is remembered rather than the content).

    > Furthermore, if you read what actually happened

    Well, if you knew what actually happened … (but you were likely being forced to read USA Today in Hong Kong middle school at the time)

    > (say, in the two Sagan biographies)

    I have not read “the” Sagan biographies (Amazon lists five, so not clear which are your two most authoritative), but they may not be written from the most neutral point of view.

    > it wasn’t a hardheaded evaluation of his research activities in planetary science, setting aside his popular work – there were passionate denunciations of his popular work.

    If this is what your two biographies say, then they are not entirely accurate. Contemporaneous first-hand accounts indicated that the discussion focused on his research credentials, and that his popular work was explicitly given neither positive nor negative weight. The part of the discussion that could be construed as “denunciation” involved his highly problematic role in the debate over “nuclear winter”, and abuse of the sloppy TTAPS modeling in the realm of public policy (the same bad science that produced his acknowledged erroneous global cooling prediction for the Gulf War fires). This was common knowledge at the time (e.g., Nuclear Winter Theorists Pull Back), so his public role and political activities were a double-edged sword, helping him through the section and class stages of the elaborate NAS process, but making his election a referendum on potential misuse of science in the public sphere; and perhaps you too would have been given pause. Although we can agree that it was for a noble goal, letting political considerations cloud scientific judgment can be seen in retrospect as having set the wrong stage for current debates on global warning, in which accurate climate models are equally dismissed as scientific overreach.

    So Sagan was very influential and well-intentioned, but may not have been the scientific saint portrayed in bibliography — sorry if this punctures some illusions (just as many schooled in the U.S. are surprised to learn [if they ever do] that the story of the Spanish cardinals laughing at Columbus for thinking the world was round was a 19th century fabrication; that not only was the prevailing belief at the time that the world was round, unlike Columbus sailors knew the actual circumference [since Eratosthenes], so knew exactly how long it would take to reach India from the other direction and hence that he was underprovisioned for the intended destination …)

    > And, yes, the NAS realized afterward that it had egg all over its face – that its decision had damaged its own reputation without affecting Sagan’s – and tried to recover.

    Or one might more charitably recognize an artful compromise for an already impossible situation, for which they’re not given credit anyway, since popular myth has him forever denied membership.

    > As for “mean, nasty scientists”: well, the scientific community is large and varied, and contains the full spectrum of humanity, I would say with the good outweighing the bad. I think it’s completely unfair to judge the entire scientific community by the NAS, which (like certain blog comment threads!) has seemed to showcase some of the scientific community’s lowest, pettiest impulses in concentrated form.

    The “mean, nasty scientists” were intended as a caricature only of your “few vocal NAS members who were jealous and resentful”. But now your characterization has evidently been extended to all of NAS? Let’s see, here are a few of the current computer scientist NAS members whom you’ve so casually indicted (am trying to pick names you might know): Leonard Adleman, Charles Bennett, Stephen Cook, Robert Griffiths, Richard Karp, Donald Knuth, John Mccarthy, Robert Tarjan, Andrew Viterbi, Shmuel Winograd, Jacob Ziv, …; the list also includes some of your MIT colleagues in case you haven’t met them yet: Robert Fano, Robert Gallager, Shafi Goldwasser, Ronald Rivest, Peter Shor (never join a club that would have you as member?). Some may even have been present at meetings 20 years ago, and could help you to interpret the popular mythology.

    The gist of your earier argument remains accurate, and Sagan remains the popular example, just not the best example for your argument.

  63. Scott Says:

    Slipper.Mystery #61: Thanks for the interesting response! I only wish everyone who disagreed with me here did so as reasonably.

    The two biographies I had in mind were Carl Sagan: A Life in the Cosmos by William Poundstone, and Carl Sagan: A Life by Keay Davidson. (It’s been 11 years since I read them, but I just reread the relevant part of the latter and it’s consistent with what I remember: a number of people who were there were absolutely disgusted and felt sure that jealousy was a major factor. And this from a biography that’s often very unsympathetic to Sagan. Go to “Look Inside” and read pages 390-392.)

    Look, it’s obvious that there are many, many fine people in NAS, and I’m proud to count some of them as colleagues and friends. On the other hand, everything I know about that organization makes it understandable to me why Richard Feynman resigned from it. (In doing so, he compared NAS to the “Honor Society” at his high school, whose only purpose turned out to be debating who was worthy of being invited to join the Honor Society.)

  64. Slipper.Mystery Says:

    Scott #63:

    > The two biographies I had in mind were Carl Sagan: A Life in the Cosmos by William Poundstone, and Carl Sagan: A Life by Keay Davidson.

    Pages 389-392 of the latter are informative.

    >
    (It’s been 11 years since I read them, but I just reread the relevant part of the latter and it’s consistent with what I remember: a number of people who were there were absolutely disgusted and felt sure that jealousy was a major factor.

    But let’s read from the prospective of a decade since of professional experience rather than as credulous student (that was the point of the Columbus parable — that it’s difficult to disabuse oneself of misconceptions acquired at too impressionable an age). Does it really make sense that 200 of the roughly 400 accomplished researchers present voted thumbs down simply because they were jealous of his “communication skills, charm, good looks…”? (about as plausible as S.A. not receiving junior faculty offer from hypothetical institution X because 50% of the faculty were jealous of his larger-than-life blog persona and ostensibly witty repartee)

    Indeed this “often very unsympathetic” treatment offers “jealousy” as the only explanation, with the above from Margulis (whose supposed impartiality is attested by “her personal anger at her former husband”, though their rapproachement was described pages earlier), and ditto from Hoffmann and Miller. The excerpt also describes his support from some serious people: Bahcall, Ehrlich, Smale, Chandrasekhar, Rubin, Cicerone, Hoffmann, but it comes through clearly that the nomination came via a non-standard route, and Miller was both politically naive and ill-prepared to support it, leading to an outcome equivalent to a set of independent coin flips.

    Margulis does however continue with “… and outspoken attitude especially on nuclear winter”, so that at least did register as part of the discussion, a “miserable half hour” in its entirety. But even in his quoted comments, Miller is almost comically unable to understand the potential danger in giving NAS imprimatur to some of Sagan’s more irresponsible misuse of scientific authority and exaggerated results in public policy debates (foreshadowed on p.122 that even early on he too frequently “spoke with a self-confidence not always justified by the data”). So the candidacy was far from the slam-dunk of legend, and the outcome not quite the egregious miscarriage of fairness used since to exemplify the stereotypical bias against popularizers from within the research community.

    > On the other hand, everything I know about that organization makes it understandable to me why Richard Feynman resigned from it. (In doing so, he compared NAS to the “Honor Society” at his high school, whose only purpose turned out to be debating who was worthy of being invited to join the Honor Society.)

    Not to be picayune, but according to two biographies Richard Feynman A Life In Science by John and Mary Gribbon, and Genius: The Life and Science of Richard Feynman by James Gleick, (see p.383 available via “Look Inside”), and various other sources, while he did liken NAS activities to a “self-perpetuating honorary society”, he didn’t make connection to his or any other “high school honor society”. The NAS of 1954-1959 when he was elected and first tried to resign was a somewhat different organization, described as having a second rate journal and no other functions. PNAS is now a first rate journal and NAS panels play a more formal government advisory role. (Perhaps you would accept membership if elected, but have somewhat less difficulty than Feynman if you later chose to resign.)

  65. Communicating Science, Physics, and Mathematics « euler cycle Says:

    [...] faster than going over all the limitations or qualifications on a discovery. (Just look at how pissed off internet commenters got at the fact that computer scientists announced a lowering of a fundamental constant as a [...]

  66. Shtetl-Optimized » Blog Archive » Quantum Complexity Theory Student Project Showcase 2! Says:

    [...] and “phenomenal” too often in that last sentence, thereby triggering the wrath of the theoretical computer science excitement police?  Well then, come over to my apartment and friggin’ arrest [...]

  67. Dorie Lyken Says:

    http://www.youtube.com/watch?v=TNH_n-C7hmg

Leave a Reply