Good news, everyone! Anindya De, Oded Regev, and my postdoc Thomas Vidick are launching an online theoretical computer science seminar series called TCS+, modeled after the successful Q+ quantum information seminars run by Daniel Burgarth and Matt Leifer. The inaugural TCS+ lecture will be on Wednesday Feb. 6, at noon Eastern Standard Time. Ronald de Wolf, longtime friend both of this blog and of its author, will be speaking on Exponential Lower Bounds for Polytopes in Combinatorial Optimization, his STOC’2012 Best Paper with Samuel Fiorini, Serge Massar, Sebastian Pokutta and Hans Raj Tiwary. This is the paper that used ideas originally from quantum communication complexity to solve a 20-year-old problem in classical optimization: namely, to rule out the possibility of proving P=NP by reducing the Traveling Salesman Problem to certain kinds of linear programs. Ronald previously gave the talk at MIT, and it rocked. See Thomas’s blog for details about how to watch.
Archive for the ‘Complexity’ Category
A month and a half ago, I gave a 45-minute lecture / attempted standup act with the intentionally-nutty title above, for my invited talk at the wonderful NIPS (Neural Information Processing Systems) conference at Lake Tahoe. Video of the talk is now available at VideoLectures net. That site also did a short written interview with me, where they asked about the “message” of my talk (which is unfortunately hard to summarize, though I tried!), as well as the Aaron Swartz case and various other things. If you just want the PowerPoint slides from my talk, you can get those here.
Now, I could’ve just given my usual talk on quantum computing and complexity. But besides increasing boredom with that talk, one reason for my unusual topic was that, when I sent in the abstract, I was under the mistaken impression that NIPS was at least half a “neuroscience” conference. So, I felt a responsibility to address how quantum information science might intersect the study of the brain, even if the intersection ultimately turned out to be the empty set! (As I say in the talk, the fact that people have speculated about connections between the two, and have sometimes been wrong but for interesting reasons, could easily give me 45 minutes’ worth of material.)
Anyway, it turned out that, while NIPS was founded by people interested in modeling the brain, these days it’s more of a straight machine learning conference. Still, I hope the audience there at least found my talk an amusing appetizer to their hearty meal of kernels, sparsity, and Bayesian nonparametric regression. I certainly learned a lot from them; while this was my first machine learning conference, I’ll try to make sure it isn’t my last.
(Incidentally, the full set of NIPS videos is here; it includes great talks by Terry Sejnowski, Stanislas Dehaene, Geoffrey Hinton, and many others. It was a weird honor to be in such distinguished company — I wouldn’t have invited myself!)
If you have opinions about quantum computing, and haven’t yet read through the discussion following my “response to Dyakonov” post, you’re missing out. The comments—by QC researchers (Preskill, Kuperberg, Gottesman, Fitzsimons…), skeptics (Dyakonov, Kalai, …), and interested outsiders alike—are some of the most interesting I’ve seen in this two-decade-old debate.
At the risk of crass immodesty, I just posted a comment whose ending amused me so much, I had to promote it to its own post. My starting point was an idea that several skeptics, including Dyakonov, have articulated in this debate, and which I’ll paraphrase as follows:
Sure, quantum computing might be “possible in principle.” But only in the same sense that teaching a donkey how to read, transmuting large amounts of lead into gold, or doing a classical computation in the center of the Sun are “possible in principle.” In other words, the task is at the same time phenomenally difficult, and fundamentally arbitrary and quixotic even if you did somehow achieve it.
Since I considered this argument an important one, I wrote a response, which stressed how quantum computing is different both because it strives to solve problems that flat-out can’t feasibly be solved any other way if standard complexity conjectures are correct, and because the goal—namely, expanding the human race’s computational powers beyond classical polynomial time—is not at all an arbitrary one. However, I then felt the need to expand on the last point, since it occurred to me that it’s both central to this debate and almost never discussed explicitly.
How do I know that the desire for computational power isn’t just an arbitrary human quirk?
Well, the reason I know is that math isn’t arbitrary, and computation is nothing more or less than the mechanizable part of solving math problems.
Let me put it this way: if we ever make contact with an advanced extraterrestrial civilization, they might have three sexes and five heads. But they, too, will have encountered the problem of factoring integers into primes. Indeed, because they’ll inhabit the same physical universe as we do, they’ll even have encountered the problem of simulating quantum physics. And therefore, putting the two together, they’ll almost certainly have discovered something like Shor’s algorithm — though they’ll call it “Zork’s bloogorithm” or whatever.
A couple weeks ago M. I. Dyakonov, a longtime quantum computing skeptic, published a new paper setting out his arguments (maybe “grievances” is a more accurate word) against quantum computing research. Looking for a way to procrastinate from other work I have to do, I decided to offer some thoughts in response.
To me, perhaps the most striking aspect of Dyakonov’s paper is what it doesn’t claim. Unlike Leonid Levin, Oded Goldreich, and several other quantum computing skeptics I’ve engaged, Dyakonov never seriously entertains the possibility of a general principle that would explain why scalable quantum computing is not possible. (Thus, my $100K prize presumably isn’t relevant to him.) He even ridicules discussion of such a principle (see the end of this post). The unwillingness to say that scalable QC can’t work, or to articulate a reason why, saves Dyakonov from the need to explore what else would need to be true about the physical world if scalable QC were impossible. For example, would there then be an efficient algorithm to simulate arbitrary quantum systems on a classical computer—or at least, all quantum systems that can plausibly arise in Nature? Dyakonov need not, and does not, evince any curiosity about such questions. In his game, it’s only the quantum computing proponents who are on trial; there’s no need for examination of the other side.
That being so, Dyakonov focuses on what he sees as unrealistic assumptions in known versions of the Quantum Fault-Tolerance Theorem, covering well-trodden ground but with some strange twists. He accuses quantum computing researchers of a “widespread belief that the |0〉 and |1〉 states ‘in the computational basis’ are something absolute, akin to the on/off states of an electrical switch, or of a transistor in a digital computer.” He then follows with a somewhat-patronizing discussion of how no continuous quantity can be manipulated perfectly, and how |0〉 and |1〉 are just arbitrary labels whose meanings could change over time due to drift in the preparation and measurement devices. Well, yes, it’s obvious that |0〉 and |1〉 don’t have absolute meanings, but is it not equally obvious that we can give them meanings, through suitable choices of initial states, gates, and measurement settings? And if the meanings of |0〉 and |1〉 drift over time, due to the imprecision of our devices … well, if the amount of drift is upper-bounded by some sufficiently small constant, then we can regard it as simply yet another source of noise, and apply standard fault-tolerance methods to correct it. If the drift is unbounded, then we do need better devices.
(Fault-tolerance mavens: please use the comments for more detailed discussion! To my inexpert eyes, Dyakonov doesn’t seem to engage the generality of the already-known fault-tolerance theorems—a generality traceable to the fact that what powers those results is ultimately just the linearity of quantum mechanics, not some fragile coincidence that one expects to disappear with the slightest change in assumptions. But I’m sure others can say more.)
Anyway, from his discussion of fault-tolerance, Dyakonov concludes only that the possibility of scalable quantum computing in the real world should be considered an open question.
Surprisingly—since many QC skeptics wouldn’t be caught dead making such an argument—Dyakonov next turns around and says that, well, OK, fine, even if scalable QCs can be built, they still won’t be good for much. Shor’s factoring algorithm is irrelevant, since people would simply switch to other public-key cryptosystems that appear secure even against quantum attack. Simulating quantum physics “would be an interesting and useful achievement, but hardly revolutionary, unless we understand this term in some very narrow sense.” And what about Grover’s algorithm? In an endnote, Dyakonov writes:
Quantum algorithms that provide (with an ideal quantum computer!) only polynomial speed-up compared to digital computing, like the Grover algorithm, became obsolete due to the polynomial slow-down imposed by error correction.
The above is flat-out mistaken. The slowdown imposed by quantum error-correction is polylogarithmic, not polynomial, so it doesn’t come close to wiping out the Grover speedup (or the subexponential speedups that might be achievable, e.g., with the adiabatic algorithm, which Dyakonov doesn’t mention).
But disregarding the polylog/polynomial confusion (which recurs elsewhere in the article), and other technical issues about fault-tolerance, up to this point many quantum computing researchers could happily agree with Dyakonov—and have said similar things many times themselves. Dyakonov even quotes Dorit Aharonov, one of the discoverers of quantum fault-tolerance, writing, “In a sense, the question of noisy quantum computation is theoretically closed. But a question still ponders our minds: Are the assumptions on the noise correct?”
(And as for QC researchers coming clean about limitations of quantum computers? This is just hearsay, but I’m told there’s a QC researcher who actually chose “Quantum computers are not known to be able to solve NP-complete problems in polynomial time” as the tagline for his blog!)
Dyakonov fumes about how popular articles, funding agency reports, and so forth have overhyped progress in quantum computing, leaving the conditions out of theorems and presenting incremental advances as breakthroughs. Here I sadly agree. As readers of Shtetl-Optimized can hopefully attest, I’ve seen it as my professional duty to spend part of my life battling cringeworthy quantum computing claims. Every week, it feels like I talk to another journalist who tries to get me to say that this or that QC result will lead to huge practical applications in the near future, since that’s what the editor is looking for. And every week I refuse to say it, and try to steer the conversation toward “deeper” scientific questions. Sometimes I succeed and sometimes not, but at least I never hang up the phone feeling dirty.
On the other hand, it would be interesting to know whether, in the history of science, there’s ever been a rapidly-developing field, of interest to large numbers of scientists and laypeople alike, that wasn’t surrounded by noxious clouds of exaggeration, incomprehension, and BS. I can imagine that, when Isaac Newton published his Principia, a Cambridge University publicist was there to explain to reporters that the new work proved that the Moon was basically an apple.
But none of that is where Dyakonov loses me. Here’s where he does: from the statements
A) The feasibility of scalable quantum computing in the physical world remains open, and
B) The applications of quantum computing would probably be real but specialized,
he somehow, unaided by argument, arrives at the conclusion
C) Quantum computing is a failed, pathological research program, which will soon die out and be of interest only to sociologists.
Let me quote from his conclusion at length:
I believe that, in spite of appearances, the quantum computing story is nearing its end, not because somebody proves that it is impossible, but rather because 20 years is a typical lifetime of any big bubble in science, because too many unfounded promises have been made, because people get tired and annoyed by almost daily announcements of new “breakthroughs”, because all the tenure positions in quantum computing are already occupied, and because the proponents are growing older and less zealous, while the younger generation seeks for something new …
In fact, quantum computing is not so much a scientific, as a sociological problem which has expanded out of all proportion due to the US system of funding scientific research (which is now being copied all over the world). While having some positive sides, this system is unstable against spontaneous formation of bubbles and mafia-like structures. It pushes the average researcher to wild exaggerations on the border of fraud and sometimes beyond. Also, it is much easier to understand the workings of the funding system, than the workings of Nature, and these two skills only rarely come together.
The QC story says a lot about human nature, the scientific community, and the society as a whole, so it deserves profound psycho-sociological studies, which should begin right now, while the main actors are still alive and can be questioned.
In case the message isn’t yet clear enough, Dyakonov ends by comparing quantum computing to the legend of Nasreddin, who promised the Sultan that he could teach a donkey how to read.
Had he [Nasreddin] the modern degree of sophistication, he could say, first, that there is no theorem forbidding donkeys to read. And, since this does not contradict any known fundamental principles, the failure to achieve this goal would reveal new laws of Nature. So, it is a win-win strategy: either the donkey learns to read, or new laws will be discovered.
Second, he could say that his research may, with some modifications, be generalized to other animals, like goats and sheep, as well as to insects, like ants, gnats, and flies, and this will have a tremendous potential for improving national security: these beasts could easily cross the enemy lines, read the secret plans, and report them back to us.
Dyakonov chose his example carefully. Turnabout: consider the first person who had the idea of domesticating a wild donkey, teaching the beast to haul people’s stuff on its back. If you’d never seen a domestic animal before, that idea would sound every bit as insane as donkey literacy. And indeed, it probably took hundreds of years of selective breeding before it worked well.
In general, if there’s no general principle saying that X can’t work, the truth might be that X can probably never work, but the reasons are too messy to articulate. Or the truth might be that X can work. How can you ever find out, except by, y’know, science? Try doing X. If you fail, try to figure out why. If you figure it out, share the lessons with others. Look for an easier related problem Y that you can solve. Think about whether X is impossible; if you could show its impossibility, that might advance human knowledge even more than X itself would have. If the methods you invented for X don’t work, see if they work for some other, unrelated problem Z. Congratulations! You’ve just reinvented quantum computing research. Or really, any kind of research.
But there’s something else that bothers me about Dyakonov’s donkey story: its specificity. Why fixate on teaching a donkey, only a donkey, how to read? Earlier in his article, Dyakonov ridicules the diversity of physical systems that have been considered as qubits—electron spin qubits, nuclear spin qubits, Josephson superconducting qubits, cavity photon qubits, etc.—seeing the long list as symptomatic of some deep pathology in the field. Yet he never notices the tension with his donkey story. Isn’t it obvious that, if Nasreddin had been a quantum computing experimentalist, then after failing to get good results with donkeys, he’d simply turn his attention to teaching cows, parrots, snakes, elephants, dolphins, or gorillas how to read? Furthermore, while going through the zoo, Nasreddin might discover that he could teach gorillas how to recognize dozens of pictorial symbols: surely a nice partial result. But maybe he’d have an even better idea: why not build his own reading machine? The machine could use a camera to photograph the pages of a book, and a computer chip to decode the letters. If one wanted, the machine could be even be the size and shape of a donkey, and could emit braying sounds. Now, maybe Nasreddin would fail to build this reading machine, but even then, we know today that it would have been a noble failure, like those of Charles Babbage or Ted Nelson. Nasreddin would’ve failed only by being too far ahead of his time.
(Note: The “2!” in the title of this post really does mean “2 factorial,” if you want it to.)
With the end of the semester upon us, it’s time for a once-every-two-year tradition: showcasing student projects from my 6.845 Quantum Complexity Theory graduate course at MIT. For my previous showcase, in 2010, I chose six projects that I thought were especially outstanding. This year, however, there were so many great projects—and so many, in particular, that could actually be useful to people in quantum computing—that I decided simply to open up the showcase to the whole class. I had 17 takers; their project reports and 10-minute presentation slides are below.
Let me mention a few projects that tried to do something new and audacious. Jenny Barry generalizes the notion of Partially Observable Markov Decision Processes (POMDPs) to the quantum case, and uses a recent result of Eisert et al., showing that certain problems in quantum measurement theory are undecidable (like, literally Turing-undecidable), to show that goal state reachability for “QOMDPs” is also Turing-undecidable (despite being decidable for classical POMDPs). Matt Falk suggests a novel quantum algorithm for spatial search on the 2D grid, and gives some numerical evidence that the algorithm finds a marked item in O(√n) time (which, if true, would be the optimal bound, beating the previous runtime of O(√(n log n))). Matt Coudron and Henry Yuen set out to prove that the Vazirani-Vidick protocol for quantum randomness expansion is optimal, and achieve some interesting partial results. Mohammad Bavarian (well, jointly with me) asks whether there’s a fast quantum algorithm for PARITY that gets the right answer on just slightly more than 50% of the inputs—and shows, rather surprisingly, that this question is closely related to some of the hardest open problems about Boolean functions, like sensitivity versus block sensitivity.
This year, though, I also want to call special attention to the survey projects, since some of them resulted in review articles that could be of real use to students and researchers in quantum computing theory. Notably, Adam Bookatz compiled the first list of essentially all known QMA-complete problems, analogous to (but shorter than!) Garey and Johnson’s listing of known NP-complete problems in 1979. Chris Graves surveyed the known quantum fault-tolerance bounds. Finally, three projects took on the task of understanding and explaining some of the most important recent results in quantum complexity theory: Travis Hance on Thomas Vidick and Tsuyoshi Ito’s NEXP in MIP* breakthrough; Emily Stark on Mark Zhandry’s phenomenal results on the security of classical cryptographic constructions against quantum attack; and Max Zimet on Jordan-Lee-Preskill’s major work on simulation of quantum field theories.
(Oops, sorry … did I use words like “important,” “breakthrough,” and “phenomenal” too often in that last sentence, thereby triggering the wrath of the theoretical computer science excitement police? Well then, come over to my apartment and friggin’ arrest me.)
Anyway, thanks so much to all the students for making 6.845 such an awesome class (at least on my end)! Without further ado, here’s the complete project showcase:
If the world ends today, at least it won’t do so without three identical photons having been used to sample from a probability distribution defined in terms of the permanents of 3×3 matrices, thereby demonstrating the Aaronson-Arkhipov BosonSampling protocol. And the results were obtained by no fewer than four independent experimental groups, some of whom have now published in Science. One of the groups is based in Brisbane, Australia, one in Oxford, one in Vienna, and one in Rome; they coordinated to release their results the same day. That’s right, the number of papers (4) that these groups managed to choreograph to appear simultaneously actually exceeds the number of photons that they so managed (3). The Brisbane group was even generous enough to ask me to coauthor: I haven’t been within 10,000 miles of their lab, but I did try to make myself useful to them as a “complexity theory consultant.”
Here are links to the four experimental BosonSampling papers released in the past week:
- Experimental BosonSampling by Broome et al. (Brisbane)
- Experimental Boson Sampling by Tillmann et al. (Vienna)
- Experimental Boson Sampling by Walmsley et al. (Oxford)
- Experimental boson sampling in arbitrary integrated photonic circuits by Crespi et al. (Italy)
For those who want to know the theoretical background to this work:
- My and Alex’s original 100-page BosonSampling paper (to appear soon in the journal Theory of Computing)
- The 10-page STOC’2011 version of our paper
- My PowerPoint slides
- Alex’s slides
- Theoretical Computer Science StackExchange question and answer
- Gil Kalai’s blog post
- Old Shtetl-Optimized post
For those just tuning in, here are some popular-level articles about BosonSampling:
- Larry Hardesty’s MIT News article (from last year)
- University of Queensland press release
- Victorian counting device gets speedy quantum makeover (this week, from New Scientist; the article is not bad except that it ought to credit Alex Arkhipov)
- New Form of Quantum Computation Promises Showdown with Ordinary Computers, by Adrian Cho (from Science)
I’ll be happy to answer further questions in the comments; for now, here’s a brief FAQ:
Q: Why do you need photons in particular for these experiments?
A: What we need is identical bosons, whose transition amplitudes are given by the permanents of matrices. If it were practical to do this experiment with Higgs bosons, they would work too! But photons are more readily available.
Q: But a BosonSampling device isn’t really a “computer,” is it?
A: It depends what you mean by “computer”! If you mean a physical system that you load input into, let evolve according to the laws of physics, then measure to get an answer to a well-defined mathematical problem, then sure, it’s a computer! The only question is whether it’s a useful computer. We don’t believe it can be used as a universal quantum computer—or even, for that matter, as a universal classical computer. More than that, Alex and I weren’t able to show that solving the BosonSampling problem has any practical use for anything. However, we did manage to amass evidence that, despite being useless, the BosonSampling problem is also hard (at least for a classical computer). And for us, the hardness of classical simulation was the entire point.
Q: So, these experiments reported in Science this week have done something that no classical computer could feasibly simulate?
A: No, a classical computer can handle the simulation of 3 photons without much—or really, any—difficulty. This is only a first step: before this, the analogous experiment (called the Hong-Ou-Mandel dip) had only ever been performed with 2 photons, for which there’s not even any difference in complexity between the permanent and the determinant (i.e., between bosons and fermions). However, if you could scale this experiment up to about 30 photons, then it’s likely that the experiment would be solving the BosonSampling problem faster than any existing classical computer (though the latter could eventually solve the problem as well). And if you could scale it up to 100 photons, then you might never even know if your experiment was working correctly, because a classical computer would need such an astronomical amount of time to check the results.
Last Friday, I was at a “Symposium on the Nature of Proof” at UPenn, to give a popular talk about theoretical computer scientists’ expansions of the notion of mathematical proof (to encompass things like probabilistic, interactive, zero-knowledge, and quantum proofs). This really is some of the easiest, best, and most fun material in all of CS theory to popularize. Here are iTunes videos of my talk and the three others in the symposium: I’m video #2, logician Solomon Feferman is #3, attorney David Rudovsky is #4, and mathematician Dennis DeTurck is #5. Also, here are my PowerPoint slides. Thanks very much to Scott Weinstein at Penn for organizing the symposium.
In other news, the Complexity Zoo went down yet again this week, in a disaster that left vulnerable communities without access to vital resources like nondeterminism and multi-prover interaction. Luckily, computational power has since been restored: with help from some volunteers, I managed to get the Zoo up and running again on my BlueHost account. But while the content is there, it looks horrendously ugly; all the formatting seems to be gone. And the day I agreed to let the Zoo be ported to MediaWiki was the day I lost the ability to fix such problems. What I really need, going forward, is for someone else simply to take charge of maintaining the Zoo: it’s become painfully apparent both that it needs to be done and that I lack the requisite IT skills. If you want to take a crack at it, here’s an XML dump of the Zoo from a few months ago (I don’t think it’s really changed since then). You don’t even need to ask my permission: just get something running, and if it looks good, I’ll anoint you the next Zookeeper and redirect complexityzoo.com to point to your URL.
Update (Nov. 18): The Zoo is back up with the old formatting and graphics!! Thanks so much to Charles Fu for setting up the new complexity-zoo.net (as well as Ethan, who set up a slower site that tided us over). I’ve redirected complexityzoo.com to point to complexity-zoo.net, though it might take some time for your browser cache to clear.
Over at Theoretical Computer Science StackExchange, an entertaining debate has erupted about the meaning and validity of the Church-Turing Thesis. The prompt for this debate was a question asking for opinions about Peter Wegner and Dina Goldin’s repetitive diatribes claiming to refute “the myth of the Church-Turing Thesis”—on the grounds that, you see, Turing machines can only handle computations with static inputs and outputs, not interactivity, or programs like operating systems that run continuously. For a demolition of this simple misunderstanding, see Lance Fortnow’s CACM article. Anyway, I wrote my own parodic response to the question, which generated so many comments that the moderators started shooing people away. So I decided to repost my answer on my blog. That way, after you’re done upvoting my answer over at CS Theory StackExchange :-), you can come back here and continue the discussion in the comments section.
Here’s my favorite analogy. Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science’s dogma, the Church-Turing Thesis fails to capture all of computation, because Turing machines can’t toast bread. Therefore, you need my revolutionary new model, the Toaster-Enhanced Turing Machine (TETM), which allows bread as a possible input and includes toasting it as a primitive operation.
You might say: sure, I have a “point”, but it’s a totally uninteresting one. No one ever claimed that a Turing machine could handle every possible interaction with the external world, without first hooking it up to suitable peripherals. If you want a Turing machine to toast bread, you need to connect it to a toaster; then the TM can easily handle the toaster’s internal logic (unless this particular toaster requires solving the halting problem or something like that to determine how brown the bread should be!). In exactly the same way, if you want a TM to handle interactive communication, then you need to hook it up to suitable communication devices, as Neel discussed in his answer. In neither case are we saying anything that wouldn’t have been obvious to Turing himself.
So, I’d say the reason why there’s been no “followup” to Wegner and Goldin’s diatribes is that theoretical computer science has known how to model interactivity whenever needed, and has happily done so, since the very beginning of the field.
Update (8/30): A related point is as follows. Does it ever give the critics pause that, here inside the Elite Church-Turing Ivory Tower (the ECTIT), the major research themes for the past two decades have included interactive proofs, multiparty cryptographic protocols, codes for interactive communication, asynchronous protocols for routing, consensus, rumor-spreading, leader-election, etc., and the price of anarchy in economic networks? If putting Turing’s notion of computation at the center of the field makes it so hard to discuss interaction, how is it that so few of us have noticed?
Another Update: To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question. What is it that lets all those high-level languages existin the first place, that ensures they can always be compiled down to machine code? Could it be … err … THE CHURCH-TURING THESIS, the very same one you’ve been ragging on? To clarify, the Church-Turing Thesis is not the claim that “TURING MACHINEZ RULE!!” Rather, it’s the claim that any reasonable programming language will be equivalent in expressive power to Turing machines — and as a consequence, that you might as well think in terms of the higher-level languages if it’s more convenient to do so. This, of course, was a radical new insight 60-75 years ago.
Update (Sept. 6): Check out this awesome comment by Lou Scheffer, describing his own tale of conversion from a Church-Turing skeptic to believer, and making an extremely apt comparison to the experience of conversion to the belief that R, R2, and so on all have the same cardinality (an experience I also underwent!).
Update (August 5): Sorry for the delay! Now that the Zoo is back up, my sense of urgency has decreased, but we still do need a long-term solution. Thanks so much to everyone who offered hosting. Alas, I was persuaded by the argument that it’s too complicated to have a wiki mirrored at multiple locations, so I should really choose one—and ideally it should be someplace where I retain control of the files, in case anything goes wrong again. Following the helpful directions of Eric Price, I set up a MediaWiki installation at http://scottaar.scripts.mit.edu/zoo. Is anyone interested in helping me transfer over the content from the qwiki Zoo?
Update (August 1): Thanks to the efforts of Gopal Sarma at Stanford, the Zoo is back up and running!! However, I believe the only long-term solution is to get the Zoo mirrored at other locations. I can then direct the domain complexityzoo.com to point to any of them that are currently up. So, to all of those who volunteered to mirror the Zoo: thanks so much, and please go ahead and do so! Let me know what you need for that (I can ask Gopal to get the source files).
As some of you have noticed, the Complexity Zoo (well, don’t bother clicking the link!) has been down for the past couple weeks. Some Stanford students volunteered to host the Zoo years ago but then graduated, and these sorts of outages have been a frustrating reality since then. So my co-zookeeper Greg Kuperberg and I are looking for a volunteer to help us get the Zoo back online. The reward? Eternal gratitude and a co-zookeeper title for yourself. In principle, I could host the Zoo on my Bluehost account, but I don’t know how to set up the wiki software, and I’m not even sure how to retrieve the Zoo pages prior to its going down (Google Cache?). If you’re interested or have ideas, leave a comment or send me an email.
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).