Shtetl-Optimized

A few months ago, I got a surprise call from Subra Suresh, director of the National Science Foundation, who told me I was going to share this year’s Alan T. Waterman Award with Robert Wood of Harvard.  (At first I assumed it was a telemarketing call, since pretty much no one calls my office phone; I use my iPhone exclusively and have trouble even operating my desk phone.)  Dr. Suresh explained that this was the first time the Waterman would ever be awarded to two people the same year, but that the committee was unanimous in supporting both me and Rob.  Looking up my co-winner, I quickly learned that Rob was a leader in the field of robot bees (see here for video)—and that his work, despite having obvious military applications, had been singled out by Sean Hannity as the latter’s #1 example of government waste (!).  That fact, alone, made me deeply honored to share the award with Rob, and eager to meet him in person.

Happily, I finally got to do that this past Thursday, at the Waterman award ceremony in Washington DC.  The festivities started in the morning, with talks by me and Rob to the National Science Board.  (I just performed my usual shtick.  I was hoping Rob would bring some actual RoboBees, but he said he no longer does that due to an unfortunate run-in with airport security.)  Then, after lunch and meetings at the NSF, it was back to the hotel to change into a tux, an item I’d never worn before in my life (not even at my wedding).  Fortunately, my dad was there to help me insert the cufflinks and buttons, a task much more complicated than anything I was allegedly getting the award for.  Then Dana and I were picked up by a limo, to begin the arduous mile-long journey from Dupont Circle to the State Department for the awards dinner.

Besides me and Rob, there were three other awardees that night:

• Leon Lederman, the 89-year-old Nobel physicist whose popular book (The God Particle) I enjoyed as a kid, received the Vannevar Bush Award.
• Lawrence Krauss, physicist and popular science writer, and National Public Radio’s science desk shared the National Science Board Public Service Award.  Some readers of science blogs might recognize Lawrence Krauss from his recent brouhaha over literally nothing with the philosopher of science David Albert.  (For whatever it’s worth, I have little to add to Sean Carroll’s diplomatic yet magisterial summary of the issues over on Cosmic Variance.)

Speaking of diplomacy, the awards dinner was held in the “diplomatic reception rooms” on the top floor of the State Department’s Harry S. Truman Building.   These were pretty awesome rooms: full of original portraits of George Washington, Ben Franklin, etc., as well as antique furniture pieces like a desk that Thomas Jefferson allegedly used while writing the Declaration of Independence.  I could easily eat dinner there on a regular basis.

Carl Wieman, the Nobel physicist and Associate Director for Science at the White House Office of Science and Technology Policy, read out a congratulatory message from President Obama.  I feel certain the President remembered I was the same dude he shook hands with a while back.

Anyway, cutting past dinner and dessert, here was my short acceptance speech:

Thanks for this honor, and huge congratulations to my co-winners, wherever in the alphabet they might lie [a reference to my getting called up before Rob Wood, simply because Aaronson<Wood lexicographically].  I like to describe my research, on the limits of quantum computers, as the study of what we can’t do with computers we don’t have.  Why would I or anyone else study such a bizarre thing?  Mostly because we’re inspired by history.  In the 1930s, before electronic computers even existed, a few people like Alan Turing were already trying to understand mathematically what such devices would or wouldn’t be able to do.  Their work ultimately made possible the information age.  Today, we don’t know exactly where curiosity about (say) quantum computers or the P versus NP question is going to lead, but I’m grateful to live in a country that’s able to support this kind of thing.  I thank the NSF and the Obama administration for supporting basic science even in difficult times.  I thank Subra Suresh (my former dean at MIT), and my phenomenal program officer Dmitry Maslov.  I thank the teachers and mentors to whom I owe almost everything, including Chris Lynch, Bart Selman, Avi Wigderson, and Umesh Vazirani.  I thank my wonderful colleagues at MIT—including my department head Anantha Chandrakasan, who’s here now—and my students and postdocs.  I thank my collaborators, and the entire theory of computing and quantum information communities, which I’m so proud to be part of.  I thank my students in 6.045 for understanding why I had to miss class today.  Most of all, I thank four people who are here with me now—my mom, dad, and my brother David, who’ve always believed in me, whether justified or not, and my wife, Dana Moshkovitz Aaronson, who’s enriched my life ever since she came into it three years ago.  Thank you.

The next day, I had the privilege of giving a quantum computing talk to more than 100 students at the Thomas Jefferson High School for Science and Technology in nearby Alexandria, VA.  Visiting TJ had special meaning for me, since while I was suffering through high school, TJ was my “dream school”: I wished my parents lived in the DC area so that I could go there.  I told the TJ students never to forget just how good they had it.  (To this day, when I meet fellow American-raised scientists, and they tell me they’re surprised I had such an unhappy time in high school, since they themselves had a great time, I always ask them which high school they went to.  In a large fraction of cases, the answer turns out to be TJ—and when it isn’t, it’s often the Bronx High School of Science or another similar place.)  As should surprise no one, the students had vastly more detailed questions about my talk than did the National Science Board (for example, they wanted to know whether I thought progress in group theory would lead to new quantum algorithms).

Without doubt, the most surreal aspect of this trip was the contrast between what was going on in my “real” and “virtual” lives.  Again and again, I’d be shaking hands with the Undersecretary of Defense, Director of the National Institute of Prestigiousness, etc. etc., and warmly accepting these fine people’s congratulations.  Then I’d sneak away for a minute to moderate my blog comments on my iPhone, where I’d invariably find a fresh round of insults about my “deeply ignorant lesser brain” from entanglement denier Joy Christian.

Perhaps the funniest contrast had to do with a MathOverflow question that I posted just before I left for DC, and which was quickly answered, just as I had hoped.  During the limo ride back from the dinner, I got the following polite inquiry from a blog commenter calling himself “Mike”:

Hey Scott, I’m wondering how you got the courage to post that question on [MathOverflow]. In truth it wasn’t that hard of a question and if you have trouble solving it then…well, no offense, but you see what I mean. Reputation matters.

As I contemplated Mike’s question, a profound sense of peace came over me.  Probably for the first time in my life, I realized just how lucky I really am.  I’m lucky that I feel free to ask naïve, simpleminded questions, toss out speculations, and most importantly, admit when I don’t know something or made a mistake, without worrying too much about whether those actions will make me look foolish before the “Mikes” of the world.  If I want to work on a problem myself, I can do that; if I prefer giving the problem out to others, I can do that as well.  Let Mike, with his greater wisdom, sit in judgment of me for my failure to see all the answers that no doubt are obvious to him.  I don’t mind.  In science, like in everything else, I’ll continue being an unabashed doofus—partly because it seems to work OK, but mostly just because it’s the only way I know.

Thanks so much to all of you for your support.

Follow

Joy Christian is the author of numerous papers claiming to disprove Bell’s theorem.  Yes, that Bell’s theorem: the famous result from the 1960s showing that no local hidden variable theory can reproduce all predictions of quantum mechanics for entangled states of two particles.  Here a “local hidden variable theory” means—and has always meant—a theory where Alice gets some classical information x, Bob gets some other classical information y (generally correlated with x), then Alice and Bob choose which respective experiments to perform, and finally Alice sees a measurement outcome that’s a function only of her choice and of x (not of Bob’s choice or his measurement outcome), and Bob sees a measurement outcome that’s a function only of his choice and of y.  In modern terms, Bell, with simplifications by Clauser et al., gave an example of a game that Alice and Bob can win at most 75% of the time under any local hidden variable theory (that’s the Bell inequality), but can win 85% of the time by measuring their respective halves of an entangled state (that’s the Bell inequality violation).  The proofs are quite easy, both for the inequality and for its violation by quantum mechanics.  Check out this problem set for the undergrad course I’m currently teaching if you’d like to be led through the proof yourself (it’s problem 7).

In case you’re wondering: no, Bell’s Theorem has no more been “disproved” than the Cauchy-Schwarz Inequality, and it will never be, even if papers claiming otherwise are stacked to the moon.  Like Gödel’s and Cantor’s Theorems, Bell’s Theorem has long been a lightning rod for incomprehension and even anger; I saw another “disproof” at a conference in 2003, and will doubtless see more in the future.  The disproofs invariably rely on personal reinterpretations of the perfectly-clear concept of “local hidden variables,” to smuggle in what would normally be called non-local variables.  That smuggling is accompanied by mathematical sleight-of-hand (the more, the better) to disguise the ultimately trivial error.

While I’d say the above—loudly, even—to anyone who asked, I also declined several requests to write a blog post about Joy Christian and his mistakes.  His papers had already been refuted ad nauseam by others (incidentally, I find myself in complete agreement with Luboš Motl on this one!), and I saw no need to pile on the poor dude.  Having met him, at the Perimeter Institute and at several conferences, I found something poignant and even touching about Joy’s joyless quest.  I mean, picture a guy who made up his mind at some point that, let’s say, √2 is actually a rational number, all the mathematicians having been grievously wrong for millennia—and then unironically held to that belief his entire life, heroically withstanding the batterings of reason.  Show him why 2=A²/B² has no solution in positive integers A,B, and he’ll answer that you haven’t understood the very concept of rational number as deeply as him.  Ask him what he means by “rational number,” and you’ll quickly enter the territory of the Monty Python dead parrot sketch.  So why not just leave this dead parrot where it lies?

Anyway, that’s what I was perfectly content to do, until Monday, when Joy left the following comment on my “Whether or not God plays dice, I do” post:

Scott,
You owe me 100,000 US Dollars plus five years of interest. In 2007, right under your nose (when you and I were both visiting Perimeter Institute), I demonstrated, convincing to me, that scalable quantum computing is impossible in the physical world.

He included a link to his book, in case I wanted to review his arguments against the reality of entanglement.  I have to confess I had no idea that, besides disproving Bell’s theorem, Joy had also proved the impossibility of scalable quantum computing.  Based on his previous work, I would have expected him to say that, sure, quantum computers could quickly factor 10,000-digit numbers, but nothing about that would go beyond ordinary, classical, polynomial-time Turing machines—because Turing himself got the very definition of Turing machines wrong, by neglecting topological octonion bivectors or something.

Be that as it may, Joy then explained that the purpose of his comment was to show that

there is absolutely nothing that would convince you to part with your 100,000. You know that, and everyone else knows that … The whole thing is just a smug scam to look smarter than the rest of us without having to do the hard work. Good luck with that.

In response, I clarified what it would take to win my bet:

As I’ve said over and over, what would be necessary and sufficient would be to convince the majority of the physics community. Do you hope and expect to do that? If so, then you can expect my $100,000; if not, then not. If a scientific revolution has taken place only inside the revolutionary’s head, then let the monetary rewards be likewise confined to his head.

Joy replied:

[L]et us forget about my work. It is not for you. Instead, let me make a counter offer to you. I will give you 200,000 US dollars the day someone produces an actual, working, quantum computer in a laboratory recognizable by me. If I am still alive, I will send you 200,000 US Dollars, multiplied by an appropriate inflation factor. Go build a quantum computer.

I’m grateful to Joy for his exceedingly generous offer.  But let’s forget about money for now.  Over the past few months, I’ve had a real insight: the most exciting potential application of scalable quantum computers is neither breaking RSA, nor simulating quantum physics, nor Grover’s algorithm, nor adiabatic optimization.  Instead, it’s watching the people who said it was impossible try to explain themselves.  That prospect, alone, would more than justify a Manhattan-project-scale investment in this field.

Postscript. If you want something about quantum foundations and hidden-variable theories of a bit more scientific interest, check out this MathOverflow question I asked on Monday, which was answered within one day by George Lowther (I then carefully wrote up the solution he sketched).

Updates (May 6). Depending on what sort of entertainment you enjoy, you might want to check out the comments section, where you can witness Joy Christian becoming increasingly unhinged in his personal attacks on me and others (“our very own FQXi genius” – “biased and closed-minded” – “incompetent” – “Scott’s reaction is a textbook case for the sociologists” – “As for Richard Gill, he is evidently an incompetent mathematician” – “I question your own intellectual abilities” – “your entire world view is based on an experimentally unsupported (albeit lucrative) belief and nothing else” – “You have been caught with your pants down and still refusing to see what is below your belly” – “let me point out that you are the lesser brain among the two of us. The pitiful flatness of your brain would be all too painful for everyone to see when my proposed experiment is finally done” – etc., etc).  To which I respond: the flatness of my brain?  Also notable is Joy’s Tourette’s-like repetition of the sentence, “I will accept judgement from no man but Nature.”  Nature is a man?

I just posted a comment explaining the Bell/CHSH inequality in the simplest terms I know, which I’ll repost here for convenience:

Look everyone, consider the following game. Two players, Alice and Bob, can agree on a strategy in advance, but from that point forward, are out of communication with each other (and don’t share quantum entanglement or anything like that). After they’re separated, Alice receives a uniformly-random bit A, and Bob receives another uniformly-random bit B (uncorrelated with A). Their joint goal is for Alice to output a bit X, and Bob to output a bit Y, such that

X + Y = AB (mod 2)

or equivalently,

X XOR Y = A AND B.

They want to succeed with the largest possible probability. It’s clear that one strategy they can follow is always to output X=Y=0, in which case they’ll win 75% of the time (namely, in all four of the cases except A=B=1).

Furthermore, by enumerating all of Alice and Bob’s possible pure strategies and then appealing to convexity, one can check that there’s no strategy that lets them win more than 75% of the time.  In other words, no matter what they do, they lose for one of the four possible (A,B) pairs.

Do you agree with the previous paragraph? If so, then you accept the Bell/CHSH inequality, end of story.

Of all the papers pointing out the errors in Joy Christian’s attempted refutations of the simple arithmetic above, my favorite is Richard Gill’s.  Let me quote from Gill’s eloquent conclusion:

There remains a psychological question, why so strong a need is felt by so many researchers to “disprove Bell” in one way or another? At a rough guess, at least one new proposal comes up per year. Many pass by unnoticed, but from time to time one of them attracts some interest and even media attention. Having studied a number of these proposals in depth, I see two main strategies of would-be Bell-deniers.

The first strategy (the strategy, I would guess, in the case in question) is to build elaborate mathematical models of such complexity and exotic nature that the author him or herself is the probably the only person who ever worked through all the details. Somewhere in the midst of the complexity a simple mistake is made, usually resulting from suppression of an important index or variable. There is a hidden and non-local hidden variable.

The second strategy is to simply build elaborate versions of detection loophole models. Sometimes the same proposal can be interpreted in both ways at the same time, since of course either the mistake or the interpretation as a detection loophole model are both interpretations of the reader, not of the writer.

According to the Anna Karenina principle of evolutionary biology, in order for things to succeed, everything has to go exactly right, while for failure, it suffices if any one of a myriad factors is wrong. Since errors are typically accidental and not recognized, an apparently logical deduction which leads to a manifestly incorrect conclusion does not need to allow a unique diagnosis. If every apparently logical step had been taken with explicit citation of the mathematical rule which was being used, and in a specified context, one could say where the first misstep was taken. But mathematics is almost never written like that, and for good reasons. The writer and the reader, coming from the same scientic community, share a host of “hidden assumptions” which can safely be taken for granted, as long as no self-contradiction occurs. Saying that the error actually occurred in such-and-such an equation at such-and-such a substitution depends on various assumptions.

The author who still believes in his result will therefore claim that the diagnosis is wrong because the wrong context has been assumed.

We can be grateful for Christian that he has had the generosity to write his one page paper with a more or less complete derivation of his key result in a more or less completely explicit context, without distraction from the author’s intended physical interpretation of the mathematics. The mathematics should stand on its own, the interpretation is “free”.  My finding is that in this case, the mathematics does not stand on its own.

Update (5/7): I can’t think of any better illustration than the comment thread below for my maxim that computation is clarity.  In other words, if you can’t explain how to simulate your theory on a computer, chances are excellent that the reason is that your theory makes no sense!  The following comment of mine expands on this point:

The central concept that I find missing from the comments of David Brown, James Putnam, and Thomas Ray is that of the sanity check.

Math and computation are simply the tools of clear thought. For example, if someone tells me that a 4-by-4 array of zorks contains 25 zorks in total, and I respond that 4 times 4 is 16, not 25, I’m not going to be impressed if the person then starts waxing poetic about how much more profound the physics of zorks is than my narrow and restricted notions of “arithmetic”. There must be a way to explain the discrepancy even at a purely arithmetical level. If there isn’t, then the zork theory has failed a basic sanity check, and there’s absolutely no reason to study its details further.

Likewise, the fact that Joy can’t explain how to code a computer simulation of (say) his exploding toy ball experiment that would reproduce his predicted Bell/CHSH violation is extremely revealing. This is also a sanity check, and it’s one that Joy flunks. Granted, if he were able to explain his model clearly enough for well-intentioned people to understand how to program it on a computer, then almost certainly there would be no need to actually run the program! We could probably just calculate what the program did using pencil and paper. Nevertheless, Bram, John Sidles, and others were entirely right to harp on this simulation question, because its real role is as a sanity check. If Joy’s ideas are not meaningless nonsense, then there’s no reason at all why we shouldn’t be able to simulate his experiment on a computer and get exactly the outcome that he predicts. Until Joy passes this minimal sanity check—which he hasn’t—there’s simply no need to engage in deep ruminations like the ones above about physics or philosophy or Joy’s “Theorema Egregious.”

Follow

Update (4/27): A famous joke concerns an airplane delivered to the US Defense Department in the 1950s, which included a punch-card computer on board.  By regulation, the contractor had to provide a list of all the components of the plane—engine, wings, fuselage, etc.—along with the weight of each component.  One item in the list read, “Computer software: 0.0 kg.”

“That must be a mistake—it can’t weigh 0 kg!” exclaimed the government inspector.  “Here, show me where the software is.”  So the contractor pointed to a stack of punched cards.  “OK, fine,” said the government inspector.  “So just weigh those cards, and that’s the weight of the software.”

“No, sir, you don’t understand,” replied the contractor.  “The software is the holes.”

If the Abernathy saga proves anything, it’s the continuing relevance of this joke even in 2012.  Abernathy is the government inspector who hears that software weighs nothing, and concludes that it does nothing—or, at least, that whatever division is responsible for punching the holes in the cards, can simply be folded into the division that cuts the card paper into rectangles.

As many of you have heard by now, Cammy Abernathy, Dean of Engineering at the University of Florida, has targeted her school’s Computer and Information Science and Engineering (CISE) department for disembowelment: moving most faculty to other departments, and shunting any who remain into non-research positions.  Though CISE is by all accounts one of UF’s strongest engineering departments, no other department faces similar cuts, and the move comes just as UF is increasing its sports budget by more than would be saved by killing computer science. (For more, see Lance’s blog, or letters from Eric Grimson and Zvi Galil. Also, click here to add your name to the already 7000+ petitioning UF to reconsider.)

On its face, this decision seems so boneheadedly perverse that it immediately raises the suspicion that the real reasons for it, whatever they are, have not been publicly stated. The closest I could find to a comprehensible rationale came from this comment, which speculates that the UF administration might be sabotaging its CS department as a threat to the Florida State legislature: “see, keep slashing our budget, and this is the sort of thing we’ll be forced to do!”  But I don’t find that theory very plausible; UF must realize that the Republican-controlled legislature’s likely reaction would be “go ahead, knock yourselves out!”

On a personal note, my parents live part-time in beautiful Sarasota, FL, home of the Mote Marine Laboratory, which does amazing work rehabilitating dolphins, manatees, and sea turtles.  Having visited Sarasota just a few weeks ago, I can testify that, despite frequent hurricanes, a proven inability to hold democratic elections, and its reputation as a giant retirement compound, Florida has definite potential as a state.

Academic computer science as a whole will be fine.  As for Florida, may the state prove greater than its Katherine Harrises, Rick Scotts, and Cammy Abernathys.

Update: See this document for more of the backstory on Abernathy’s underhanded tactics in dismantling the UF CISE department.  Based on the evidence presented there, she really does deserve the scorn now being heaped on her by much of the academic world.

Another Update: UF’s president issued a rather mealy-mouthed statement saying that they’re going to set aside their original evisceration proposal and find a compromise, though who knows what the compromise will look like.

In another news, Greg Kuperberg posted a comment that not only says everything I was trying to say more eloquently, but also explains why I and other CS folks care so much about this issue: because what’s really at stake is the concept of Turing-universality itself.  Let me repost Greg’s comment in its entirety.

It looks like Dean Abernathy hasn’t explained herself all that well, which is not surprising if what she is doing makes no sense. Reading the tea leaves, in particular the back-story document that Scott posted, it looks like she had it in for the CS department from the beginning of her tenure as Dean at Florida. In her interview with Stanford when she had just been appointed as dean, she already said then that “we” wanted to bring EE and CS closer together, even though at the time, there had been no discussion and there was no “we”. Then during discussions with the CS department, she refused to take no for an answer, even though she sometimes pretended to, and as time went on the actual plan looked more and more punitive. She appointed an outside chair to the department, and then in the final plan she terminated the graduate program, moved half of the department to EE, and left the other half to do teaching only. The CS department was apparently very concerned about its NRC ranking, but this ranking only came out when Abernathy’s wheels were already in motion. In any case everyone knows that the NRC rankings were notoriously shabby across all disciplines and the US News rankings, although hardly deep, are much less ridiculous.

So what gives? Apparently from Abernathy’s Stanford interview, and from her actions, she simply takes computer science to be a special case of electrical engineering. Ultimately, it’s a rejection of the fundamental concept of Turing universality. In this world view, there is no such thing as an abstract computer, or at best who really cares if there is one; all that really exists is electronic devices.

Scott points out that those departments that are combined EECS are really combined in name only. This is not just empirical happenstance; it comes from Turing universality and the abstract concept of a computer. Yes, in practice modern computers are electronic. However, if someone does research in compilers, much less CS theory, then really nothing at all is said about electricity. To most people in computer science, it’s completely peripheral that computers are electronic. Nor is this just a matter of theoretical vs applied computer science. CS theory may be theoretical, but compiler research isn’t, much less other topics such as user interfaces or digital libraries.

Abernathy herself works in materials engineering and has a PhD from Stanford. I’m left wondering at what point she failed to understand, or began to misunderstand or dismiss, the abstract concept of a computer. If she were dean of letters of sciences, then I could imagine an attempt to dump half of the literature department into a department of paper and printing technology, and leave the other half only to teach grammar. It would be exactly the same mistake.

Follow

Judea Pearl has won a richly-deserved Turing Award, for his pioneering work on reasoning under uncertainty, Bayesian inference, and causality.  Much like last year’s winner Leslie Valiant, Pearl has been a perfectly-plausible candidate since the 1980s; it was really just a question of when they’d get around to him.  For those who don’t know his work, Pearl’s landmark book Causality provides a wonderful introduction to at least one major strand of his thought; I read it this summer and it inverted the way I think about lots of things in statistics.  (Pearl’s fame precedes this award, partly for a tragic reason: he’s probably best known to the public as the father of the murdered journalist Daniel Pearl.)

In other big news, playing Super Mario Bros. is now known to be NP-complete, as shown in this landmark paper by Greg Aloupis, Erik Demaine, and Alan Guo.  The sheer intuitiveness of the gadget constructions, at least to anyone who grew up playing Nintendo, makes this probably my favorite NP-completeness paper of all time (well, I guess tied with some papers by Cook, Karp, and Levin).

Follow

Check out this statement on “The Cost of Knowledge” released today, which (besides your humble blogger) has been signed by Ingrid Daubechies (President of the International Mathematical Union), Timothy Gowers, Terence Tao, László Lovász, and 29 others.  The statement carefully explains the rationale for the current Elsevier boycott, and answers common questions like “why single out Elsevier?” and “what comes next?”

Also check out Timothy Gowers’ blog post announcing the statement.  The post includes a hilarious report by investment firm Exane Paribas, explaining that the current boycott has caused Reed Elsevier’s stock price to fall, but presenting that as a great investment opportunity, since they fully expect the price to rebound once this boycott fails like all the previous ones.  I ask you: does that not want to make you boycott Elsevier, for no other reason than to see the people who follow Exane Paribas’ cynical advice lose their money?

In related news, the boycott petition now has 4600+ signatures and counting.  If you’ve already signed, great!  If you haven’t, why not?

Update (Feb. 9): There’s now a great editorial by Gareth Cook in the Boston Globe supporting the Elsevier boycott (and analogizing it to both the Tahrir Square uprising and the Boston Tea Party!).

Follow

Another Update (Feb. 7): I have a new piece up at IEEE Spectrum, explaining why I made this bet.  Thanks to Rachel Courtland for soliciting the piece and for her suggestions improving it.

Update: My $100,000 offer for disproving scalable quantum computing has been Slashdotted.  Reading through the comments was amusing as always.  The top comment suggested that winning my prize was trivial: “Just point a gun at his head and ask him ‘Convinced?'”  (For the record: no, I wouldn’t be, even as I handed over my money.  And if you want to be a street thug, why limit yourself to victims who happen to have made public bets about quantum computing?)  Many people assumed I was a QC skeptic, and was offering the prize because I hoped to spur research aimed at disproving QC.  (Which is actually an interesting misreading: I wonder how much “pro-paranormal” research has been spurred by James Randi’s million-dollar prize?)  Other people said the bet was irrelevant since D-Wave has already built scalable QCs.  (Oh, how I wish I could put the D-Wave boosters and the QC deniers in the same room, and let them duke it out with each other while leaving me alone for a while!)  One person argued that it would be easy to prove the impossibility of scalable QCs, just like it would’ve been easy to prove the impossibility of scalable classical computers in 1946: the only problem is that both proofs would then be invalidated by advances in technology.  (I think he understands the word “proof” differently than I do.)  Then, buried deep in the comments, with a score of 2 out of 5, was one person who understood precisely:

I think he’s saying that while a general quantum computer might be a very long way off, the underlying theory that allows such a thing to exist is on very solid ground (which is why he’s putting up the money). Of course this prize might still cost him since if the news of the prize goes viral he’s going to spend the next decade getting spammed by kooks.

OK, two people:

There’s some needed context.  Aaronson himself works on quantum complexity theory.  Much of his work deals with quantum computers (at a conceptual level–what is and isn’t possible).  Yet there are some people who reject the idea the quantum computers can scale to “useful” sizes–including some very smart people like Leonid Levin (of Cook-Levin Theorem fame)–and some of them send him email, questions, comments on his blog, etc. saying so.  These people are essentially asserting that Aaronson’s career is rooted in things that can’t exist.  Thus, Aaronson essentially said “prove it.”  It’s true that proving such a statement would be very difficult … But the context is that Aaronson gets mail and questions all the time from people who simply assert that scalable QC is impossible, and he’s challenging them to be more formal about it.  He also mentions, in fairness, that if he does have to pay out, he’d consider it an honor, because it would be a great scientific advance.

For better or worse, I’m now offering a US$100,000 award for a demonstration, convincing to me, that scalable quantum computing is impossible in the physical world.  This award has no time limit other than my death, and is entirely at my discretion (though if you want to convince me, a good approach would be to convince most of the physics community first).  I might, also at my discretion, decide to split the award among several people or groups, or give a smaller award for a discovery that dramatically weakens the possibility of scalable QC while still leaving it open.  I don’t promise to read every claimed refutation of QC that’s emailed to me.  Indeed, you needn’t even bother to send me your refutation directly: just convince most of the physics community, and believe me, I’ll hear about it!  The prize amount will not be adjusted for inflation.

The impetus for this prize was a post on Dick Lipton’s blog, entitled “Perpetual Motion of the 21st Century?”  (See also this followup post.)  The post consists of a debate between well-known quantum-computing skeptic Gil Kalai and well-known quantum-computing researcher Aram Harrow (Shtetl-Optimized commenters both), about the assumptions behind the Quantum Fault-Tolerance Theorem.  So far, the debate covers well-trodden ground, but I understand that it will continue for a while longer.  Anyway, in the comments section of the post, I pointed out that a refutation of scalable QC would require, not merely poking this or that hole in the Fault-Tolerance Theorem, but the construction of a dramatically-new, classically-efficiently-simulable picture of physical reality: something I don’t expect but would welcome as the scientific thrill of my life.  Gil more-or-less dared me to put a large cash prize behind my words—as I’m now, apparently, known for doing!—and I accepted his dare.

To clarify: no, I don’t expect ever to have to pay the prize, but that’s not, by itself, a sufficient reason for offering it.  After all, I also don’t expect Newt to win the Republican primary, but I’m not ready to put $100,000 on the line for that belief.  The real reason to offer this prize is that, if I did have to pay, at least doing so would be an honor: for I’d then (presumably) simply be adding a little to the well-deserved Nobel Prize coffers of one of the greatest revolutionaries in the history of physics.

Over on Lipton’s blog, my offer was criticized for being “like offering $100,000 to anyone who can prove that Bigfoot doesn’t exist.”  To me, though, that completely misses the point.  As I wrote there, whether Bigfoot exists is a question about the contingent history of evolution on Earth.  By contrast, whether scalable quantum computing is possible is a question about the laws of physics.  It’s perfectly conceivable that future developments in physics would conflict with scalable quantum computing, in the same way that relativity conflicts with faster-than-light communication, and the Second Law of Thermodynamics conflicts with perpetuum mobiles.  It’s for such a development in physics that I’m offering this prize.

Update: If anyone wants to offer a counterpart prize for a demonstration that scalable quantum computing is possible, I’ll be happy for that—as I’m sure, will many experimental QC groups around the world.  I’m certainly not offering such a prize.

Follow

If you’re in academia and haven’t done so yet, please take a moment to sign this online petition organized by Tyler Neylon, and pledge that you won’t publish, referee, or do editorial work for any Elsevier journals.  I’ve been boycotting Elsevier (and most other commercial journal publishers—Elsevier is merely the worst) since 2004, when I first learned about their rapacious pricing policies.  I couldn’t possibly be happier with my choice: unlike most idealistic principles, this one gets you out of onerous work rather than committing you to it!  Sure, Elsevier is huge and we’re tiny, but the fight against them is finally gathering steam (possibly because of Elsevier’s support for the “Research Works Act”), years after the case against them became inarguable.  Since their entire business model depends on our donating free labor to them, all it will take to bring them down is for enough of us to decide we’re through being had.  We can actually win this one … Yes We Can.

For more information, see this wonderful recent post by Fields medalist and Shtetl-Optimized commenter Timothy Gowers, entitled “Elsevier — my part in its downfall.”  (Added: also check out this great post by Aram Harrow.)  You might also enjoy a parody piece I wrote years ago, trying to imagine how Elsevier’s “squeeze those dupes for all they’ve got” business model would work in any other industry.

Follow

Since everything I write now seems to provide an occasion for bitter controversy, I’ll be curious to learn whose sensibilities I inadvertently offended by posting the following announcement for next year’s ITCS conference. -SA

Dear Theorists:

As you know the third Innovation in Theoretical Computer Science Conference will be held in Cambridge this January:  http://research.microsoft.com/en-us/um/newengland/events/itcs2012/.

REGISTRATION IS NOW OPEN and THE PROGRAM IS ONLINE.

In addition to the program, there are going to be a few novelties that we would like to point out to you.

1. GRADUATING BITS

In one session of the conference, students graduating this academic year (as well as researchers completing their postdoc this academic year) will be given few minutes to present themselves and their work.

The presentations will be grouped by University, in alphabetic order.

We hope this will give all of us an opportunity to have a synopsis of the great work being done by the “graduating” members of our community.

In order to speak in this special session, please send an email at  silvio.itcs12@gmail.com by DECEMBER 15.

Registration fees will be waived for presenters at Graduating Bits 2012.

If you/your students are graduating this year, or you plan to hire this year, we are encourage to attend ITCS 2012!

2. COMMUNITY BUILDING

To strengthen our (legendary!) friendship and collaboration, we will treat you to a PLAY BACK show: an improvisational theater where OUR actors will bring to life YOUR stories.

3. CHAIR RANTS

In addition to the chair of each session introducing the speakers and coauthors of the session (who will then introduce themselves and their coauthors), our chairs will provide us with their insights on the papers in their sessions.

We look forward to seeing all of you in Cambridge very soon!

All the Best

Shafi Goldwasser, Silvio Micali, and Yael Tauman Kalai

Follow

For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n^2.376) steps.   Last year, though, in his PhD thesis, Andrew Stothers gave an improvement to O(n^2.374) steps.  And today,  Virginia Vassilevska Williams of Berkeley and Stanford, released a paper that gives a general methodology for analyzing Coppersmith-Winograd-type algorithms, and that improves the matrix-multiplication time to a lightning-fast O(n^2.373) steps.  (Virgi’s work was independent of Stothers’, though she credits him and applies an idea of his to simplify her proof.)  Full disclosure: I actually knew a month ago that this was coming—I had a hell of a time keeping the secret.  I’d recommend that you get started memorizing “ω<2.373,” but as Russell Impagliazzo points out in the comments, the exponent might get lowered again in short order.  Huge congratulations to Virgi and to Andrew for this breakthrough!

Update (Nov. 30): Last night I received an extremely gracious email from Andrew Stothers, which he’s given me permission to summarize here.  In the email, Andrew expressed how excited he was about Virgi’s new result, apologized for the confusion he caused by not mentioning his improvement to ω until page 71 of his thesis (he says he doesn’t know why he did it), and said that he meant to publish a paper, but was prevented from doing so by health and job issues.  He also said that he didn’t take issue with anything I wrote here, except that I mistakenly referred to him as Andy rather than Andrew.  In response, I congratulated Andrew on his achievement; expressed how happy I was that—ironically—his work is now finally getting some of the attention that it deserves; and promised to buy him a beer when and if I’m ever in Edinburgh, a city I’ve always wanted to visit.  (On the other hand, I warned Andrew that his LinkedIn profile, which unselfconsciously mentions improvements to his Word and Excel skills as one of the benefits of his PhD research breaching the Coppersmith-Winograd barrier, might have earned him a place in scientific folklore forever!)

In summary, I now see Andrew as an extraordinarily nice fellow who had some bad luck and—most conspicuously—a lack of good advice from people around him.  I do stand by the points that I was originally trying to make:

(a) that this tangled situation shouldn’t in any way detract from Virgi’s fantastic achievement, which (except for a simplification, as she discusses) must be considered completely independent of Andrew’s, and

(b) that there’s indeed an important cautionary lesson for students here, about adequately publicizing your work (yes, there’s a happy medium, between hiring a PR firm to wage a viral marketing campaign and burying your solution to a longstanding open problem so far in the body of your PhD thesis that even world experts in the subject who read your thesis will miss it).

On the other hand, I hereby apologize for anything I said that could even be perceived as slighting Andrew, his important work, or his motives.

Another Update: On the third hand, if you’re one of the commenters whose beef is not about attribution, but about the entire concept of using a CS theory blog to “promote” major milestones in CS theory (like the breaking of the Coppersmith-Winograd barrier), then I apologize for absolutely nothing.  Go read an economics or physics blog; I understand that those are entirely hype-free.  Better yet, go to hell.

Follow

The Theory of Computation (TOC) group at the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT is seeking candidates for a post-doctoral position in the general area of the theory of computation. Applicants in all areas of theory are encouraged to apply, including (but not exclusive to) algorithms, complexity theory, combinatorial optimization, cryptography, distributed computing, game theory and computation, geometry, parallel computing, and quantum computing. This fellowship is made possible by a generous gift from the Simons Foundation.

The fellowship is a two year position, starting the summer or fall of 2012. The fellowship stipend is gauged to attract the highest caliber of applicants. Generous funds for scientific travel will be available for use at the fellow’s discretion. Fellows will be assigned a faculty member close to their research interests from the TOC group. Fellows will be encouraged (although not required) to teach a graduate seminar in their area of research.

Eligibility: Candidates must receive their PhD during the academic year immediately preceding that in which the fellowship would begin. There are no other restrictions based on nationality or any other basis.

Application Process: Candidate applications should include a description of professional interests and goals in research. Each application should include a curriculum vitae and the names and addresses of three or more individuals who will provide letters of recommendation. Letter writers should submit their letters directly to MIT to the address below. Please submit complete applications by January 6, 2012.

Address to submit application: All application materials and recommendation letters should be sent electronically to theory-postdoc@csail.mit.edu. The candidate’s name should be included in the subject line of the email. Alternatively, the materials can be also sent to the following address:
Simons Postdoctoral Fellowship, c/o Joanne Hanley
MIT Computer Science and Artificial Intelligence Laboratory
The Stata Center, Building 32-G672A
32 Vassar Street
Cambridge, MA 02139, USA.

Follow