(While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here. Our slogan: Complexity Blog: You heard it here THIRD.)
Let w be the exponent for matrix mult. A very brief history of Matrix Multiplication (years given are years of publication, though it is odd to say Pan in 1978 showed that w < 2.796 since, for all I know, he did it in 1977 or even earlier.)
- The obvious way to do this shows w ≤ 3. This is obvious to us; however, I wonder when it was first stated.
- Strassen in 1969 showed w ≤ 2.808. This is important since it shows that Gaussian Elimination is not optimal (that is the name of the paper) and also because it is a cautionary tale for lower bounds- w=3 seems optimal... but its not!
- Pan in 1978 showed that w < 2.796.
- Bini, Capovani, Romani, Lotti in 1979 showed w < 2.78.
- Schonhage in 1981 showed w < 2.522 This was significant since it used a brand new technique.
- Romani in 1982 showed w < 2.517.
- Coppersmith and Winograd in 1981 obtained w < 2.496. This was significant in that it broke the 2.5 barrier.
- Strassen in 1986, using a very diff technique, obtained w < 2.479.
- Coppersmith and Winograd in 1987 obtained w < 2.376. (See here for the Journal Version.) This paper uses the large 3-free sets of Behrend. (See here for Behrends article (it might now work- its the Proceedings of Nat Academy of Sciences website and I don't know if its free to ALL or just to some schools.) or here for my survey of large 3-free sets.)
- Cohn and Umans in 2003 proposed a group theoretic approach which had the potential for new algorithms. Kleinberg and Szegedy in 2005 obtained new algorithms using the approach, but couldn't beat 2.376.
- Elkin in 2008 (here) obtained larger 3-free sets than Behrends. Elkin in 2010 (here) used these sets to get a logv improvement over CW for some v > 0.
- Andy Stothers 2010 PhD thesis (here) claims to have w ≤ 2.374. The result was not stated in the abstract. He didn't post a preprint or email a blogger so this work was relatively unknown. He did tell some experts in the field. (See the comments on Scott's blog for what might be the full story on that).
- This is clearly a breakthrough! There had been NO improvement in two decades!
- The improvement is small; however, it may lead to more improvements (this seems to be common in this field).
- Can Elkin's 3-free sets be used to get a log improvement over Virginia's result? Not sure we care- from what I understand (which is not much) (1) the current techniques can likely be pushed further, and (2) Elkin's 3-free sets will only give a log-ish improvement, no more. (Is log-ish a new word? Should it be?)
- Is the algorithm practical? I suspect not.
- Two breakthroughs in theory within a year from the same family. Impressive!
I can't not notice how the complexity horde likes to abuse the word "breakthrough".
ReplyDeletePeter: In your field, what do they call improving a bound that hundreds of people tried to improve, but none of them succeeded for the last 24 years? Maybe you have a problem with the relevance of the field, not with the importance of the result for the given field.
ReplyDeleteThe breakthrough is due to Stothers (he had the first improvement in 20 years), but all the bloggers are trying hard to now minimize his contribution.
ReplyDeleteStothers did not popularize it in 2010.
Why was the reaction of the three blogers to dismiss his result instead of appropriately popularizing it now? All this does not look very scientific.
If Stothers had posted his result or publicized it in some way then the bloggers would have blogged about it.
ReplyDeleteHe didn't. And now they are punishing him for not posting
and also sending a message to other non-posters.
If a tree falls in a forest and the event is not reported on arXiv then did it make sound. No.
Well, the bloggers found out about it now. Why are they trying to dismiss it? Why isn't his result a breakthrough and only Williams's result is considered a breakthrough (according to our bloggers)?
ReplyDeleteIt is something really strange going on here...
Re: trees et al.
ReplyDeleteYeah, well, if that's the way we're going to argue: http://data.whicdn.com/images/3683633/comicifatreefallsinthewoods1_large.png
I am trying to understand something that I saw in multiple blogs. Why was there a "2.5 barrier" that Coppersmith-Winograd broke? Why is it a barrier and where does 2.5 come from? Perhaps someone here can enlighten me?
ReplyDelete(Here is my take on the 2.5 though I INVITE those more knowledgable to comment as I may be off base).
ReplyDeleteNobody thought that w=2.81 or any other funny looking number. Same with w=2.517. But w=2.5 is plausible.
So showing that w < 2.5 is interesting.
This is clearly a breakthrough! There had been NO improvement in two decades!
ReplyDelete``This'' meaning Stother's result? Otherwise, the second sentence is false.
Congratulations to both!
There are other problems where the best known algorithm can be improved by a complicated computer search, essentially what Stothers has achieved. I do not see this as a breakthrough. Can you say anything about the conceptual contributions of Stothers or Williams' papers?
ReplyDeleteShallow blog posts that list numbers without even considering concepts remind me of Claire's http://teachingintrotocs.blogspot.com/2011/11/conferences-and-arxiv-utilitarian.html
Peter 2:21:
ReplyDeleteI can't thank you enough for your courage and selflessness, in being one of only about 15 blog-commenters to have spoken out these past few days against the terrible, much-overlooked societal scourge of theoretical computer scientists getting too excited about the solutions to longstanding open problems in their own field. So please, whatever you do, don't start your own blog to talk about the research YOU find exciting. The complexity horde needs you right here, continuing to speak "truth" to "power".
Anonymous #3: Nobody is trying to minimize Stothers contribution. In fact, it is the exact opposite. Everyone is trying to finally give Stothers the credit that he deserves after the experts he told, did not give much attention or credit to what he did.
ReplyDeleteAnonymous #6: Your cartoon is offensive and terrible and I hope someone removes it.
Hopefully someone will soon enough come up with an O(n^2.371) algorithm, and this whole discussion will be over.
ReplyDeleteThe question is: should we call this the Strothers-Vassilevska or the Strothers-Williams improvement over CW?
ReplyDeleteIs this the average ethic standard in TCS?
ReplyDeleteDisgusting!
This is a great result for Strother, and also a strong advancement for Virginia, of course.
ReplyDeleteSince the result of Strother was published (in his PhD) just last year, I don't think it's fair to accuse him of failing to communicate it to the public. Moreover, who precisely is the "public" here? This blog?
Getting a blog-post about your result is certainly not, or at least should not be, considered as a mean for publicizing your work. So, up to this point in time, both results are still unpublished, except that Strother did defend his thesis and made it available on the web, so he has priority.
Conclusions:
ReplyDelete1. To be acknowledged for your result it is not sufficient that the experts in the area know about it, these eccentric bloggers should be informed.
2. If you prove a result and experts know about it it is still possible for someone else to lock himself in a room and claim that they find the same result independently after a year.
3. If you use computers to optimize an already known results without any increase in our understanding of the problem and according to experts is not going to go much further and it is a non-essential improvement over a result from last year then it is still possible to have people call a break-through if you know the right people.
An advice to young researcher, before trying to make a break-through please ask an expert in the topic to make sure you are up to date.
Scott, I am a complexity theorist, you are entitled to your opinions but not everyone working in complexity theory shares them. It has nothing to do with "others" being against complexity theorists announcing nice results or break-troughs. It is about the amount of advertisement that is going on in branding what would not be considered a break-through by mathematical standards.
ReplyDeleteIn recent years there have been people who have done very nice work and have developed interesting mathematics to use computers in solving several problems in combinatorics and graph theory, problems which were open for more than half a century, problems that many combinatorics have worked on and failed to solve. But they don't announce them as break-throughs. It seems that we disagree on what constitutes a break-through result. Maybe you and others who claim these results to be break-through should clarify what you mean by a break-through and then demonstrate that these results satisfy the criteria. As I understand, both results improve the analysis of the previously known methods using computers to lower the constant in the exponent slightly. You may say that people have tried to lower the consent for more than 2 decades, but I am not sure that was the case. I would guess most people would think it might be possible to lower the constant slightly by optimizing CW but thought that it is not significant enough to worse the time to be carried out and might also have lacked the computer skills needed. Is there any other reason you brand these results as break-through?
Another thing that annoys people about these announcements is that there is too much selling going on in theoretical computer science. It is not the way mathematicians are used to work. Although we continue to claim to be mathematicians culturally we have moved from it towards more applied computer science.
To understand the reactions, remember how you felt every time you read about D-Wave and people trying to sell it as more than what it was.
I commend both researchers but the herd-mentality self-promotion on the part of some TCS bloggers is indeed breathtaking.
ReplyDeleteAnon 12:08AM: Let me clarify that when I wrote "Getting a blog-post about your result is certainly not, or at least should not be, considered as a mean for publicizing your work",
ReplyDeleteI meant only that blog-posts describing your work should not be considered as a formal mean of publication for the sake of getting academic credits, etc. Of course, it is a completely legitimate way to get your work known to the world, otherwise.
I'm a computer scientist but not a theoretical computer scientist. I love the TCS blogs, but goodness do they attract some bad comments. Probably the worst of any subject-focused blog I read regularly (even worse than the comments on political blogs!).
ReplyDeleteMaybe you guys can go post your negative comments on YouTube or somewhere else they'd fit and leave the rest of us to enjoy learning about TCS.
The way I see why getting below 2.5 was a breakthrough is that I believe (by some unjustified faith) that the answer to simple questions should be simple. More justified, though, is that the answer to simple questions whose answer is a number is an easy to state algebraic number.
ReplyDeleteFor example, the stretch factor of the Delaunay triangulation was known to be between pi/2 and 2.something. I thought that either the right answer was pi/2 or 2. It was recently shown that neither is the case (it is more than pi/2 and less than 2).
In the case of matrix multiplication, we are improving upper bounds on w. My question is: are there convincing arguments that w is not 2 or 2+eps for arbitrarily small eps?
Anonymous 2:23, let me try one more time.
ReplyDeleteAt the simplest level, I see Andrew's and Virgi's results as a "breakthrough" because ~2.376 was one of the tiny handful of constants in all of math, CS, and physics that I'd actually needed to memorize---alongside ~3.1415, ~2.718, and ~0.85 (the success probability in the CHSH game). In TCS, omega shows up in so many different contexts and papers that lowering it is almost like lowering the value of pi (whatever that would mean). I'd get similarly excited by other work---in combinatorics, graph theory, whatever---that similarly redrew one or more of the "gross features" of the TCS landscape. (And no, redrawing such a gross feature isn't the only way to achieve a "breakthrough," but I think it's a sufficient condition.)
The idea, constantly repeated by anonymous commenters, that "all Virgi and Andrew did was to use computer search to optimize CW" seems to me to leave out the most interesting part of the story. Namely, people had already tried to optimize CW by taking the third tensor power, and it had given no improvement whatsoever. Given that, it would be completely reasonable to guess that you've already passed the point of diminishing returns---that taking higher tensor powers would make things worse. So it was a genuine surprise that taking the 4th tensor power did give an improvement, and that taking the 8th tensor power gave a better improvement still. And new ideas were needed to make those calculations manageable; otherwise, given the importance of the problem, they would've already been carried out a long time ago.
Finally, regarding D-Wave: if Andrew and Virgi were trying to pitch their improvements to CW as a commercial product, if their claims to do so were being admiringly and uncritically reported by major news outlets, and if they'd offered no serious evidence that they'd even improved on CW in the first place, then you'd have yourself a decent analogy. :-)
Anonymous 1:27, probably no use trying to reason with you, but:
ReplyDelete1. Many experts in the subject (such as Henry Cohn) did not know about Stothers' result---in some cases, not even after looking at Stothers' thesis (!).
2. While I don't think this is really Stothers' fault (more likely the fault of bad advice he got, or good advice he didn't get), the fact remains that this sort of situation is very detrimental to science, and that it essentially never happens when a result is communicated effectively. To communicate a result like this effectively, it would more than suffice to post a preprint to ECCC or arXiv, or submit a paper to any conference, that stated the result in the abstract. Not that hard, and doesn't require "knowing the right people."
3. While not detracting from Andrew's accomplishment, the facts above are the reasons why Virgi's accomplishment needs to be considered independent, and why I expect the community will consider it independent.
Come on Scott, I agree with much of what you said in the comments. But put w at the level of \pi and e,
ReplyDeletethat is a little off.
Anonymous on 1:27 AM, December 01, 2011: The experts were told about Stothers attempt, but thought it was a failed attempt based on the way he wrote his thesis. (See Henry Cohn's comments on Scott's blog). It wasn't until Virginia wrote her paper that they realized Stothers idea really did work.
ReplyDeleteScott mentions that not communicating a result effectively is detrimental to science. It really seems as though these sorts of nasty/sarcastic comment threads also seem detrimental to science.
Scott asserts: "This sort of situation is very detrimental to science, and it essentially never happens (Scott's italics) when a result is communicated effectively."
ReplyDelete-------------------------
Lol ... the amusing opposite to Scott's Great Truth is illustrated by the answers to the Math Overflow question: What are examples of mathematical concepts named after the wrong people?
Q: Who proved the Cayley-Hamilton Theorem?
A: Frobenius!
This phenomenon is so ubiquitous as to have several names, including Stigler's Law, Boyer's Law, and Arnol'd's Law.
There is also Whitehead's Law: "Everything of importance has been said before by someone who did not discover it." :)
From a wonderful comment on my Anti-Complexitism post a year ago, which I strongly recommend that everyone who's following the current matrix multiplication saga read:
ReplyDeleteThe final criticism 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?”
The experts were told about Stothers attempt, but thought it was a failed attempt based on the way he wrote his thesis.
ReplyDeleteThis is incorrect. Marcus Blasser says a different thing at http://www.scottaaronson.com/blog/?p=839#comment-34668.
previous anon, yes Marcus Blasser did know about the result since he was an external reader, but he thought that the result was not that significant.
ReplyDeleteIf you do read Henry Cohn's comments it is clear that the sentence I wrote applies to him. We cannot speculate about what Shokrollahi and Strassen thought and did.
Scott,
ReplyDeleteI concede. :)
Anonymous 2:23
I'm also working in complexity, unfortunately.
ReplyDeleteI will reiterate what Anonymous 2:23 said:
"Scott, I am a complexity theorist, you are entitled to your opinions but not everyone working in complexity theory shares them."
This also answers the following question:
"If you don’t like complexity theorists being excited about their area why are you reading these blogs?"
Hi, in #10, second sentence: this was a joint paper by Cohn, Kleinberg, Szegedy and Umans, rather than just Kleinberg and Szegedy. Also, in #12, it seems Stothers likes being called Andrew rather than Andy (see Scott's blog comments).
ReplyDeleteScott, 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.
ReplyDeleteThis 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?
Anonymous (2:47 PM, Dec 01)
ReplyDeleteI'm not an academic so maybe this is all going over my head, but are you saying that by writing *blog posts* about results that excite them in their field, people like Scott are taking funding away from other researchers?
1. That sounds far fetched.
2. Even if true, so what? Should they also write blog posts about results in physics and anthropology so they can make sure funding gets spread around fairly?
3. Is this really what you spend your day worrying about?
To Anonymous 1:27 AM, Dec 01.
ReplyDeleteI completely agree to your conclusions. Unlike many people who are calling it a breakthrough even without looking at the paper, I have at least looked at the paper and have tried to understand the main conceptual message there! More, I see how a class of TCS people react and behave, more I feel, I should leave this area and do something else. disgusting!
doesn't "breakthrough" mean that a well established barrier has been broken for the first time? If so, at best the adjective breakthrough applies to stothers. the next progress down to 2.373 is indeed an excellent contribution but not a breakthrough.
ReplyDeleteAnonymous asserts: It's not about excitement, it's about researchers competing for scarce resources ... [and] the prisoners dilemma-type game scientists are playing.
ReplyDelete----------------------
Anonymous, your post reflects a 20th century framework for appreciating the human condition that (IMHO) didn't work out so well. And so, may I commend to your attention the in-press (and cutting-edge) survey How does the social environment 'get into the mind'? Epigenetics at the intersection of social and psychiatric epidemiology.
At their best — similarly to a lucid mathematical lecture or a well-crafted article/monograph — weblogs like Fortnow/GASARCH, Gödel's Lost Letter, and Shtetl Optimized (and many more) perform the invaluable service of methylating readers' neural epigenomes to enduringly increase the production of "happy good-humored" chemicals.
Needless to say, I am very disinclined to criticize any person, or any forum, that tries to accomplish this noble goal! :)
In reading the comments (and having followed this blog forever) I am struck by something: for whatever reason, right or wrong, a vocal group within TCS feels some sort of animosity toward (TCS | TCS bloggers | "TCS insiders" | the TCS "community"). Instead of trying to convince those people are wrong (as Scott's blog post about Anti-Complexitism does), we should instead be trying to understand why there is so much animosity in the first place.
ReplyDeleteAfter reading these blogs and comments, i start to understand why Stothers wants to leave TCS.
ReplyDeleteIt's not the nature of TCS, I don't think. It's the nature of blogs (and open internet forums, in general)
ReplyDeleteIt's not the nature of TCS, I don't think. It's the nature of blogs
ReplyDeleteI'm not so sure. Could it have something to do with the fact that TCS is so competitive. By this I don't mean that the nature of the work is hard, but that the community/group is extremely competitive compared to other areas of CS (I originally started outside TCS and have been surprised by how competitive people are in TCS).
This high level of competition is probably due to the fact that so few good jobs are available for TCS researchers but nonetheless it might also play a part in the animosity towards members of the community that are better connected.
Anonymous 2:47: Scott, you are missing the larger socio-economical context: it's not about excitement. It's about researchers competing for scarce resources, primarily funding.
ReplyDeleteLet me see whether I understand. On this view, other scientists shouldn't have lauded Carl Sagan for getting millions of people excited about science; rather, they should've despised him for using hype to divert millions of funding dollars from their own fields to the ones Sagan favored. Assuming, of course, that the other scientists didn't want to sink to Sagan's level, and perform the loathed task of communicating their own excitement about their own fields.
Actually, there were other scientists who drew exactly that conclusion: for example, Carl Sagan was famously denied membership in the National Academy of Sciences, because of a few vocal NAS members who were jealous and resentful of his 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.
Let me thank you, Anonymous 2:47: it's rare for anyone to state the the motivation for anti-complexitism with this much candor.
Now that the true motivation has (apparently) crawled out from underneath its rock, I can examine it and refute it. The central point is that this 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 get diverted to their own areas. Ultimately, the SSC was cancelled, and none of the money was ever diverted to other areas of physics.
So, if you see people using blogs to talk about the research results that excite them, then instead of resenting it, consider setting up your own blog to talk about the research results that excite YOU. If it's well-written and interesting, I'll even add it to my blogroll. Go to WordPress.com -- it's free, and it takes just a few minutes to set one up.
Let me add another point.
ReplyDeleteSome of the Anonymous people seem to dismiss this work as "just a computer search." (by the way, why don't you diverse Anonymouses get a pseudonym? It takes a few minutes to get one, and clearly not all Anonymous are equal. Aren't you upset for being taken for each other?)
There was another controversial computer search some time ago: the proof of the Four-Color Theorem. The underlying mathematics was well known. "All" that was needed was to look at a number of cases... Why is the exponent of the multiplication conceptually different?
Another correction: the Goedel Prize is not a Complexity Prize. It is all of TCS. Besides Complexity Theory, past winners' research included Algorithms, Automata Theory, Distributed Computing, Semantics, etc.
@Scott 4:08am. I completely agree with you on the funding vs popularization/excitement about our own field(s). There some comments I'd like to make though.
ReplyDeleteTo those feeling deflated about complexity research: complexity will be around whether we like it or not, and with a fast increasing need to actually do something about it. I do talk to various program managers and they are increasingly desperate on this issue. Now it could very well be that in order to make major advances in this regard we need to *radically* change at least some aspects about how we think about these problems...great, the more attractive the challenge! Nature never really cared about our taste in scientific approaches: we eat her cooking whether we like it or not :-).
On (C)Science blogging and popularizing: there can't be enough of it. However, childish resentments will do more disservice to one's field than an honest scientific discourse (perhaps program managers don't read blogs?). Naturally, if something is wrong/fishy, it has to be expressed and uncovered promptly with science-based arguments, of course. That said, we are all entitled to our opinions, even though that might not be the majority one. If someone feels that the recent results on matrix multiplication are a breakthrough, great! I personally don't feel that way, (I probably would if I have been working on this question) but I am curious and willing to listen and certainly respect those that feel otherwise.
Science-based discussion and popularization is quite important also as a checking mechanism, here is why: Unfortunately there are trends in science where research is not done for the purpose of understanding/solving a problem but for chasing the spotlight; that would still be ok if the quality of research would match the hype, but tends not to. And that's rather dangerous for all, because failed promises reflect back on the whole field rather than just on those making them. Here is an interesting read along these directions by Peter A. Lawrence: "The mismeasurement of science", Current Biology, vol. 17, R583-R585 (2007).
As a point of correction, the original anonymous reference to the "Prisoner's Dilemma" (a reference that was echoed by subsequent posts) might more relevantly have referenced the competitive dynamic that evolutionary biologists call "The Red Queen's Race", that is, one-way evolutionary ratchets trending toward displays of fitness that are increasingly specialized and costly (e.g., Bird-of-Paradise displays).
ReplyDeleteWithout taking sides either way, deploring the dynamics of the Red Queen's Race is an honorable tradition in the mathematical literature, e.g., in von Neumann's essay "The Mathematician" we read:
-----------------
As a mathematical discipline travels far from its empirical source, or still more, if it is a second and third generation only indirectly inspired by ideas coming from "reality" it is beset with very grave dangers. It becomes more and more purely aestheticizing, more and more purely I'art pour I'art.
This need not be bad, if the field is surrounded by correlated subjects, which still have closer empirical connections, or if the discipline is under the influence of men with an exceptionally well-developed taste. But there is a grave danger that the subject will develop along the line of least resistance, that the stream, so far from its source, will separate into a multitude of insignificant branches, and that the discipline will become a disorganized mass of details and complexities.
In other words, at a great distance from its empirical source, or after much "abstract" inbreeding, a mathematical subject is in danger of degeneration. At the inception the style is usually classical; when it shows signs of becoming baroque, then the danger signal is up.
Whenever this stage is reached, the only remedy seems to me to be the rejuvenating return to the source: the re-injection of more or less directly empirical ideas. I am convinced that this was a necessary condition to conserve the freshness and the vitality of [mathematics] and that this will remain equally true in the future.
-------------------------
Perhaps the point is that in mathematics (or any other academic profession) fitness displays are an evolutionary necessity, and yet the health of the obevall ecosystem requires that these fitness displays *not* be judged by a single rating measure, lest the resulting Red Queen's Race lead to an evolutionary dead-end.
In which case, everyone posting on this topic is saying something sensible. Good! :)
Some time ago, when Ryan Williams showed NEXP is not in ACC^0, I've read the paper and found its message very interesting: prove lower bounds by proving upper bounds. But then I've saw "breakthrough in circuit complexity", "best result in 20 years", "Razborov's lower bound is nothing compared with this", etc. I was confused. I wrote several comments asking people to be bit more reserved. In estimation. Time will show, not our current excitement. Received many aggressive (surprisingly aggressive!) replays. Also in Scott's blog.
ReplyDeleteNo comes the "second round". But now I know what's going on. One should distinguish results from their advertising. Distinguish blogs from papers. Excitement of bloger's from a healthy scientific skepticism. Just distinguish. Time will show.
People do not like it when bloggers do public relations for their friends. Andrew didn't have any blogger friends and his result was thus not considered a breakthrough by those experts who were exposed to it. From the little I know about math and TCS, it is usually new ideas which are coined as breakthroughs. When you can describe something in a simpler way which is closer to its true description, by observing it from a different angle - then a breakthrough has been made. Not when you have a computer aided 71 page long super complex way to reduce a constant three digits beyond the decimal point.
ReplyDeletePeople don't like it when achievements are not judged by the merits of what was achieved, but by the people the achiever happens to be friends with.
clearly some people don't like actual computers being used to get new results in theoretical computer science
ReplyDeleteand clearly others do like actual computers being used to get new results in theoretical computer science.
ReplyDeletehttp://www.wisdom.weizmann.ac.il/~oded/MC/083.html
Scott,
ReplyDeleteOn one hand, in pure mathematics seem to be doing fine without such standard practice of enormous bragging in the introduction, even when a true breakthrough is made.
On the other hand, in order to match the level of hype to make sure that TCS/Complexity remains competitive against other area, say biology or economics, impact factor is the norm, therefore are we also supposed to also start citing every single paper in the area?
Some people here, like Scott, seem not to understand "where this animosity within complexity" comes from. So let me try to explain at least the reasons why some people within complexity object to the over-hype happening on certain blogs. There are at least three (related) reasons I can think of.
ReplyDeleteThe first is that indeed it highers the standards of required promotion *within* the TCS community itself. So Scott's story about Sagan is irrelevant: it's not about getting
money from outside sources, rather what is at stake here is getting credit, acknowledgment, respect (and hence, job offers, paper acceptance, etc.) for your work from the TCS community itself. If some parties invest lots of efforts in self-promoting themselves, or their close circle of friends, then everyone else now needs to play according to a higher promotional bar. So in this case, naturally, people will object, because they might be incapable for it or they have no talent for self-promotion or they just don't like it, or they feel it's humiliating, or time consuming, or on purely principled grounds they're against it (see below), etc.
The second reason is this: if self-promotional hype continues in TCS, then from the *outside* people will start consider us as non-serious scientists. Here, I'm referring to *academics* outside TCS who would laugh at "these clowns that claim breakthroughs every second week, and use self-promotional tactics in blog posts to communicate their research"-a behavior which might be considered as "non-scientific" to some. So this goes to show that for *certain levels* of over-popularization (e.g., when it's high, but not high enough), you might not get financial benefits from the public and governments, but on the contrary, receive you'll less money, credit and respect.
The third, and possibly the most important, reason to object over-hyped popular blog posts is for ideological and aesthetically reasons. These kind of things are simply not something that is appropriate to do. Because it is not honest. In some cultures or sub-cultures, or even groups of sensitive individuals, any kind of promotion is unethical to a certain degree. Yes, there are some market-oriented cultures that are all about PR, business and salesmanship. But there are other cultures that look down on these things. So there's a natural "culture" clash here.
Now, the point I'm trying to make is this: I'm not saying that any hype or promotion is bad. I'm saying that some is good, and some is bad, and that these things should be examined on a case by case basis. On the other hand, people like Scott seem to claim that *any* criticism against over-promotional-hyped blog-posts is inappropriate and wrong. I have explained above, why it is in fact not always wrong or inappropriate.
If you want an example, look at Terry Tao's blog. It is both popular, and serious. Excited, but always measured. Never hyped, but honest. Other blogs are not.
On one hand, in pure mathematics seem to be doing fine without such standard practice of enormous bragging in the introduction, even when a true breakthrough is made.
ReplyDeleteIf by fine you mean the lowest level of funding of all the hard sciences as well as the lowest enrollments, then we agree, they are doing fine.
There is much we can learn (and have learned) from math, including its rigor and powerful techniques, but there is also much we should avoid, in particular acting as if applications (either within the field itself or to other areas) didn't matter.
p.s. Tim Gowers (heard of him?) agrees in Scott's blog that the result was a breakthrough for some reasonable definition of breakthrough. He also wisely points out that the word breakthrough can be interpreted differently by various people, e.g. type 1: life changing event; type 2: first progress in twenty years; etc.
Something just occurred to me: all the commenters who are scandalized by my knowing Virgi and Ryan (in Ryan's case, since long before either of us was a member of any "clique"!) seem to be missing a strange irony.
ReplyDeleteIn my entire blogging career, no one ever complained once about my blogging MY OWN research, even though that intuitively seemed much more problematic to me, and I therefore avoided doing it for years. It stood to reason, I thought, that if no one had any problem with my blogging my own work when it excited me, then far less should they have a problem with my blogging anyone else's.
That just goes to show how poor a model I have for (some) other people's thought processes---a problem I fear I'll carry with me my entire life.
I feel like I did on various occasions when I was bitten by an angry dog, whereupon the owner calmly explained to me that, oh, this dog is the gentlest dog in the entire world, and would never bite anyone, but perhaps I should've known that the dog does get enraged at people who are wearing sunglasses, or people who approach the owner while the dog is sitting in the owner's lap ... "why of course, won't make THAT mistake again!"
So, is it something about academia, or something about the internet, that causes people to write multi-paragraph comments about why other people shouldn't express excitement about things they find cool? Cuz I'm pretty sure in real life, people don't do that.
ReplyDelete--Anonymous who wouldn't say this in real life
Scott, the problem is that people who didn't know about your friendship with ryan and virgi might have had the wrong impression that the first lowerbound for acc0 or the first lowering of the matrix multiplication exponent in 20 years are scientific achievements worth posting about. (Rather than some meager incremental improvements which you and all the other blogger-mafia only posted about because you're all college buddies.)
ReplyDeleteBoaz Barak
More seriously, perhaps its because I haven't read blgs in a while, but I was disapppointed in the lack of colleagiality displayed by the anonymous comment. Scientists worked hard and made some progress on an important question, and they deserve congratulations.
ReplyDeleteI am also surprised by the implied premise that a blog mention is some great honor that should be distributed "fairly". Personal blogs just reflect the writer's personal opinion about things he/she happened to hear about, nothing more. I can assue you that people sitting in program comittees, hiring comittees, and nsf panels are well aware of that (and many of them don't read blogs at all..)
Boaz Barak
@Boaz, I think you might have been misreading the posts and comments. It was the anonymous commenters who showed collegiality, by insisting that prior works lowering the w constant would be credited appropriately, and not dismissed.
ReplyDeleteVery interesting point!
ReplyDeleteI totally admit that as a complexity theorist it's our lack of collegiality that we chose not to endorse people from our own field.
However what is concerned here is HONESTY: it's our moral duty to counter Scott's effort to downplay Stothers' result!
There are so many different anonymous here, I was referring to those complaining about posting about this result at all, rather than attribution issues, which seem to have resulted from lack of knowledge rather than malice. It seems to me (and more importantly, apparently also to Stothers himself) that Scott's current post is very fair about attribution to both Stothers and Williams.
ReplyDeleteBoaz Barak
Boaz Barak
For those who read Scott’s original post, some of them certainly will *say* that he downplayed Stothers’ result due to “lack of knowledge”, although I doubt too many people actually *believe* this is the case.
ReplyDeleteThis reminds me of the following quotes by Perelman, who Scott despised as being eccentric…
"I can't say I'm outraged. Other people do worse. Of course, there are many mathematicians who are more or less honest. But almost all of them are conformists. They are more or less honest, but they tolerate those who are not honest."
Yet it’s pathetic that instead of the proof of the Poincare conjecture, this time, some complexity theorists had been collaborating, in the holy spirit of “collegiality”, to fight for the credit for a 0.001 improvement of matrix multiplication, and to ensure that matrix multiplication is marketed as a “complexity problem”.
In either this blog or Scotts blog when did we ever say that matrix mult was a complexity result?
ReplyDeleteWe all posted on it since we all thought it was interesting. Thats all.
http://www.scottaaronson.com/blog/?p=853#comment-35000
ReplyDeleteI second Boaz: "Personal blogs just reflect the writer's personal opinion about things he/she happened to hear about, nothing more." Indeed, nothing more. Albeit we take them too seriously. Nobody from NSF or similar make decisions based on blogs or similar "noise". The whole discussion here was only about honesty. About who has done what, and when. Not about WHAT was done.
ReplyDeleteThough nobody from NSF or similar make decisions based on blogs or similar "noise", they often "cite" their main massages - it is simple true.
ReplyDelete