Thursday, October 07, 2010

Noble and Ig Noble Prizes

What is the Ig Nobel prize? To quote the website:
The Ig Nobel Prizes honor achievements that first make people laugh, and then make them think. The prizes are intended to celebrate the unusual, honor the imaginative --- and spur people's interest in science, medicine, and technology.
Some science seems real, though odd: In 2006 the Ig Nobel in Mathematics went to (quoting the website)
Nic Svenson and Piers Barnes of the Australian Commonwealth Scientific and Research Organization, for calculating the number of photographs you must take to (almost) ensure that nobody in a group photo will have their eyes closed.
Some science does not seem real: In 1993 the Ig Nobel in Mathematics went to (quoting the website)
Robert Faid of Greenville, South Carolina, farsighted and faithful seer of statistics, for calculating the exact odds (710,609,175,188,282,000 to 1) that Mikhail Gorbachev is the Antichrist.
There is no specific Ig Nobel prize in computer science. What computer science work deserves an Ig Nobel? What complexity work deserves an Ig Nobel?

Has anyone every won BOTH an IG NOBEL PRIZE and a NOBEL PRIZE? YES! It just happened! Andre Geim won the 2010 Nobel Prize for Physics and had previously won 2000 Ig Nobel Prize for Physics. I describe the equipment used in both, but I will not say which one won the Nobel prize and which one won the Ig Nobel prize.
  1. One used Magnets and Frogs.
  2. One used Scotch Tape and Pencils.


  1. I was surprised when Erik Demaine and his coauthors didn't win the Ig Nobel for proving Tetris is NP-hard.

  2. It is spelled "Nobel." Alfred Nobel was a noble man.

  3. Golly ... the Conway's Life community is fully deserving of a Ig Noble lifetime achievement award.

    For example, Canadian computer programmer Andrew Wade just this month demonstrated the first fully programmable Life self-replicator (the replicator is named "Gemini; thus a Google search for "Wade AND Gemini" will find it).

    The replication cycle of Gemini is 33,699,586 generations ... and yes, the shareware program GOLLY will compute Gemini's full replication cycle within a few minutes.

    Even a brief academic publication on Gemini would make Andrew a contender for an Ig Nobel award ... hopefully he will write one.

  4. I think that at the time, the Eliza program got a lot of laughs but was sometimes uncanny in its answers to reveal something about ourselves.

  5. I nominate Knuth for his TUG 2010 talk on iTeX :

  6. Ig Turing wouldn't sound very nice I guess... Ig Goedel?

  7. I think GASARCH mispelled Nobel on purpose,
    though with him its hard to tell.

    Some of the results on cake cutting where you need to cut a cake into a gazillion pieces to ensure fairness could win an Ig Nobel in either math or economics.

  8. Given that the paper should make people think, in addition to laugh, I nominate the following two:

    1) Aaronson's paper on P=PSPACE given time-travel

    2) Any of the O(1) property testers that use Szemeredi lemma. Sure, they're constant time, but your graph would have to exceed the size of the universe before it outperformed a naive exponential algorithm.

  9. Jeremy, the tower-of-exponential bounds in property testing might just be because the tools we have for analysis are not strong enough.

  10. IgNoble prize to be awarded to Indian-born charlatan Vinay Deolalikar for pulling around TCS comunity for a full week, until few blog guest mathematicians explained to TCS comunity that his "proof" is undiluted trash, something TCS people couldn't properly figure out on their own, apart from offering bogus house money in publicity stunts.

  11. To Anonymous: 2:48pm, October 07:

    From "Indian-born charlatan" to
    "pulling around TCS comunity for a full week" and then on to "few blog guest mathematicians" who explained to "TCS comunity" who offered "bogus house money in publicity stunts" you do cover a wide range of interesting English usage. But it is not your poor English [I could be uncharitable and ask which hole you crawled out of] which is offensive.

    It is your rude and ignorant rant [many months late] which manages to offend not just the owner of the claimed proof but the people who took a similar view to yours about the proof but with much more nous and humor, instead of the extreme ill-will that you display which has probably won you a prize much more embarrassing than an IgNobel in most readers' eyes.

    Just step back and think, science progresses through mistakes and is [usually, eventually] self-correcting.

    Deolalikar had the courage of his convictions that he had a valid proof, and put it out to be dissected and analyzed. A "charlatan" refers to academic misconduct and cannot be bandied around lightly, the way you do, without any real evidence or proof. Many great mathematicians
    have made errors, so nothing new there.

    PS: I am not Indian, neither am I from the "TCS comunity" you bag, just an interested observer of this blog.

  12. Deolalikar is indeed a crank - his refusal to retract his "proof" has showed that he does not deserve to be taken seriously. His attitude has been criticized many times on many blogs, by quite a lot of people including authors of this blog. His role is indeed shameful, and way he handled himself is real unethical misconduct. I do not think he deserves IgNoble prize, which is done for real but strange results. Rather, he is more like "kook of the year".

  13. "kook of the year" seems like it should be reserved for someone trying to push a wacky Kleene-Rosser paradox P/NP "proof"

  14. Deolalikar is indeed a crank - his refusal to retract his "proof" has showed that he does not deserve to be taken seriously

    It is possible he doesn't understand the seriousness of the objections. I have been "lucky" with my own submissions, in that whenever I've had something rejected, I agreed with the referees that what they mentioned as problems were, in fact, real problems that I needed to address. So far, I've never had anything close to a drive-by "no" of the kind I see other blog commenters complain about. But my own work is focused, so I've been able to understand reviewers' concerns quickly. In D's case, the discussion was broad-ranging and technically deep in multiple areas. I bet there's only a handful of people in the world who fully understand all points on the wiki, even today. If he doesn't "get" all the issues -- or just wants something more formal than a wiki -- it hurts nothing for him to submit and wait-and-see. It doesn't make someone a charlatan to wait for an official referee's report.

  15. The points in Serdar's post were good (IMHO), and I would like to extend them.

    If we consider the converse problem, we are led to ask, what avenues in academia are suited to the expression of anger, frustration, dislike, and even hatred?

    Really, there is only one avenue: post anonymously. And that is why I disregard anonymous posts (except posts from self-identified students, who comprise a privileged case).

  16. For the IgTuring award, there is no one more deserving than D. He managed what no IgNoble prize winner managed ever before: to have an unpublished, fatally flawed proof grab attention of not only the experts, but major media, who reported his "work" like no result in the field ever before. What is even more ironic, his undeserved fame served as a vehicle for popularization of the entire field. There are crook proofs of P vs NP every month, but no one else managed to gain that attention. He created more hype than any of the 2010 Fields medalists, Nevanlinna or Gauss award winners. As a result, his inflated ego exploded, and blinded him completely. While he can be criticized for lack of modesty, it is understandable that he is now in a state of delusional nirvana, apparently still a hero to many kooks who never got this level of fame using his dirty bag of tricks. His is a brave victory of sensationalist self-promotional crookery over honest work, and many seem to support him.

  17. Do we have any evidence that Deo planned all this or is a bad guy as he has been
    painted by some. As GASARCH would say:
    I ask this nonrheotically.

    If he retracts tommorow and then proves something weaker but interesting from his paper, then all of the negative comments about him will seem silly.

    Now- surely there are other Ig Nobles in
    Comp Sci or math worth talking about, lets get back to that.

    Here is one type of result: proving that a game has a winning strategy for player I but the proof gives you no idea of how to actually win (CHOMP is one such game).
    This is really funny, but alas we are too used to it.

  18. Liu Xiaobo has been awarded the Nobel Peace Prize.

    Posting this fact on popular math weblogs makes state censorship more difficult ...

    ... and this is yet another reason why math weblogs are great! :) :) :)

  19. does the Nobel so-called Peace Prize mean anything anymore?

    last year it went to a man who hadn't done anything to advance peace at all

    does 刘晓波 winning it attempt to reward actions towards peace or try to stir up unrest?

  20. Anonymous says: Does (winning a Nobel Peace Prize) reward actions towards peace OR (?) try to stir up unrest?

    LOL .. assuming GASARCH-style that your question was posed non-rhetorically ... why ... the verdict of history is clear ... peace-making and trouble-making have always been concomitant.

    Therefore, anonymous, one word of your question requires a minor repair ... simply replace "OR" with "AND".

    Obviously, both last year's Peace Prize and this year's Peace Prize satisfy the resulting criterion. Good!

  21. Osama bin Laden should win Turing peace prize, for subverting corrupt order of a global police state. Liu Xiaobo:China = Osama bin Laden:USA,
    Nobel=Turing, IgNobel=IgTuring,
    P=NP iff P<>NP, ZFC is contradictory, Deolalikar=Genius, Peace=War, Freedom=Slavery, Osama=Obama, Sidles=Swindles,Sterling=Euro,arnab=holy cow,serdar=gandhi,kamouna=riemann,english=chinglish,frenchfries=freedomfries, Turkey=World Power, Kurds=Animals, flying frogs=flying pigs, Arabs=Devils, Aaronson=Aalcapone, Lance=GASARCH.

    That is this sorry blog in a nutshell.

  22. Deolalikar should win the lg Nobel. Not for his latest paper but for his previous research, leading to the proof of P neq NP for infinite time turing machines.

  23. I think that the Chinese dissident winning the Nobel prize was the best decision made by the Nobel prize committee this year. Frankly, the world ought to do more to expose the deplorable state of human rights in China. For it's part, the TCS community can do something too: boycott Chinese-sponsored conferences, such as ICS, and ensure that they are a massive flop (not that it is a massive success anyway).

  24. hey, thanks to Vinay Deolalikar your field wont stagnate in terms of general public interest and maybe, just maybe, your profession as TCS practitioneers will not vanish!

  25. I think we ought to go nucular with chinks. We mustn't allow these slant-eyed commies to get ahead of us, the all-mighty US. They have no respect for human dignity, they despise our freedoms. We should boycott all their conferences and their products, and should severe all ties with chink scientists. They steal and plagiarize from us, the mighty US, shamelessly so. Chink scientists in US are really spies for the bloody communist totalitarian regime, and they should be detained behind the barbed wire, like the nips before or sand niggers in Guantanamo. Nuke them until they say uncle, "Puleeease Uncle Sam, we will respect human rights".

    TCS pride world wide!

  26. The first Ig CS prize should be given to Selmer Bringsjord and Joshua Taylor for the soap bubble Steiner-tree algorithm.

  27. when you get angry, you are weak and funk. That always makes you keep away from humanity.

  28. can someone who posted the comment about rape plz tell us what the incentive or ill-will was all about ? I mean who in the right mind does such posts ?

    I can understand ppl frustrated about the invasion of chinese theft ranging from intellectual prop to theoretical plagiarism but not real familiar with the notion of wishing rape to anyone

  29. our own fault. why did we keep pouring money and investing into china ? it was all about profits. cheap labor, more profits. we kept investing and investing and letting reason out of our sight.

    now we complain ...

    1) we knew that whenever we set up a new factory plant in china, we will have to co-partner with a domestic chinese company who would in turn steal and abuse our trade secrets. but we kept on doing this anyways. because we believed in the short run profits. my ass that china is starting to care about proprietary trade secrets. And if so, it's only for its own interest. after we fed them with all we had, suddenly they might come up with new ideas and afraid of us stealing their ideas they start caring about prop trade secrets.

    2) why did we not take an example of how japan dealt with this matter ? ok nowadays japanese businesses are as nonsensical as our own ones by setting up factory plants in china but there was a time long long before when the mere thought of setting up anything in china would cause revolt. This sentiment was usefully put in practice by shielding away all these nifty gadget technologies and making them available only for internal/domestic consumption. Another thing that japan used to be smart about was the absolute taboo of foreinger (in particular chinese ) buying property. Now take a look at NY, how much property belongs to chinese already ?

    3) from now on we should be cautious about how much we invest into china and what we invest into china. For the short run it might be looking like a lucrative thing but err not.
    Nationalist sentiment will always prevail in the long run. If china ever catches up with the technology and is able to attach some degree of quality to products manufactured there, then that will be "the" worst nightmare for foreign companies just like a gays parents' worst nightmare is if their adopted baby's first word is: mommie.

    beware beware beware.

  30. where did the quality go ?1:51 AM, October 12, 2010

    quality, where are u these days ?

    20 yrs ago, i remember ....

    i bought a white work shirt made in the USA and it lasted for a good five years without major deterioration of the fabric. When i could afford it, i bought the luxury brands made in france, italy and england, all first choice items that lasted a good decade. I mean you spent a lot of money on them but they would last for decently long. You felt good about spending that money.

    what happened now ? My income rose, I retired. Sometimes I buy the same luxury european brands if they are still in existence. I noticed such a drop in quality u aint going to believe it. I can barely wear the same shirt for 2 months before it starts fallin apart. I launched my own small scale investigation and noticed that 99% of the time everything is manufactured over in China, then sent back to Europe where the last item to be added is the actual label. Oh dear .... where did we end up ? In an era of poor quality. Why does the consumer have to suffer from it ? I don't want my items to be produced in CHINA ...

    I want them produced in USA or Europe, Japan will also do.

    Don't u see what outsourincg has brought to the consumer ? misery, pain and poor quality. If you outsource, then do so in a country that is known for good quality.

  31. @Prev anony:
    You are both correct and wrong.
    The thing is that you can get good quality products if you are ready to pay more in the outsourced country.
    At least in India there are SW Engineers who are paid from $400 to $1000 per month (no health benefits).
    In general the poor quality software is made by people who are paid nothing.
    I am sure things would be same in China. After all Prada and others also get their things made in China.
    So yes, if you are ready to do more then you will get better thing.
    Also, these are side effects of free market aka capitalism. So, stopping this would involve changing everything this great country stands for.

  32. Lance, Bill, it's long past time to turn off anonymous comments.

    I had hoped that after the previous embarrassing episodes, your readers would be shamed into acting like professionals, or at least adults. Several comments in this post clearly show that my hope was unrealistic.

    Kudos for sticking to an uncomfortable philosophical stance, but the anonymous comments in this blog make the theoretical computer community look like a bunch of spoiled children. Despite appeals to keep comments civil and professional, a few cowards insist on posting offensive insults and slander. Kick them out!

  33. I guess the last 3 anon comments are acceptable but not the one about rape.

    all in all, lance and Bill are doing a fabulous job in maintaining integrity and protecting rights to freedom of speech and anonymity.

    Jeffe, I can't help it if you belong to the folks that support a totalitarian regime [china] which poops on human rights and annoys the hell out of everyone by saying that foreigner should not interfere with the internal matters of chinese.

    Long live USA ... Long LIVE DEMOCRACY

  34. the anonymous comments in this blog make the theoretical computer community look like a bunch of spoiled children.

    Some of them behave like spoiled children. Some, I suspect, are secret KKK members. Fortunately, the majority are fair, objective, and respectful, even when posting anonymously.