Archive for the ‘Complexity’ Category

NSA: Possibly breaking US laws, but still bound by laws of computational complexity

Sunday, September 8th, 2013

Update (Sept. 9): Reading more about these things, and talking to friends who are experts in applied cryptography, has caused me to do the unthinkable, and change my mind somewhat.  I now feel that, while the views expressed in this post were OK as far as they went, they failed to do justice to the … complexity (har, har) of what’s at stake.  Most importantly, I didn’t clearly explain that there’s an enormous continuum between, on the one hand, a full break of RSA or Diffie-Hellman (which still seems extremely unlikely to me), and on the other, “pure side-channel attacks” involving no new cryptanalytic ideas.  Along that continuum, there are many plausible places where the NSA might be.  For example, imagine that they had a combination of side-channel attacks, novel algorithmic advances, and sheer computing power that enabled them to factor, let’s say, ten 2048-bit RSA keys every year.  In such a case, it would still make perfect sense that they’d want to insert backdoors into software, sneak vulnerabilities into the standards, and do whatever else it took to minimize their need to resort to such expensive attacks.  But the possibility of number-theoretic advances well beyond what the open world knows certainly wouldn’t be ruled out.  Also, as Schneier has emphasized, the fact that NSA has been aggressively pushing elliptic-curve cryptography in recent years invites the obvious speculation that they know something about ECC that the rest of us don’t.

And that brings me to a final irony in this story.  When a simpleminded complexity theorist like me hears his crypto friends going on and on about the latest clever attack that still requires exponential time, but that puts some of the keys in current use just within reach of gigantic computing clusters, his first instinct is to pound the table and shout: “well then, so why not just increase all your key sizes by a factor of ten?  Sweet Jesus, the asymptotics are on your side!  if you saw a killer attack dog on a leash, would you position yourself just outside what you guesstimated to be the leash’s radius?  why not walk a mile away, if you can?”  The crypto experts invariably reply that it’s a lot more complicated than I realize, because standards, and efficiency, and smartphones … and before long I give up and admit that I’m way out of my depth.

So it’s amusing that one obvious response to the recent NSA revelations—a response that sufficiently-paranoid people, organizations, and governments might well actually take, in practice—precisely matches the naïve complexity-theorist intuition.  Just increase the damn key sizes by a factor of ten (or whatever).

Another Update (Sept. 20): In my original posting, I should also have linked to Matthew Green’s excellent post.  My bad.

Last week, I got an email from a journalist with the following inquiry.  The recent Snowden revelations, which made public for the first time the US government’s “black budget,” contained the following enigmatic line from the Director of National Intelligence: “We are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.”  So, the journalist wanted to know, what could these “groundbreaking” capabilities be?  And in particular, was it possible that the NSA was buying quantum computers from D-Wave, and using them to run Shor’s algorithm to break the RSA cryptosystem?

I replied that, yes, that’s “possible,” but only in the same sense that it’s “possible” that the NSA is using the Easter Bunny for the same purpose.  (For one thing, D-Wave themselves have said repeatedly that they have no interest in Shor’s algorithm or factoring.  Admittedly, I guess that’s what D-Wave would say, were they making deals with NSA on the sly!  But it’s also what the Easter Bunny would say.)  More generally, I said that if the open scientific world’s understanding is anywhere close to correct, then quantum computing might someday become a practical threat to cryptographic security, but it isn’t one yet.

That, of course, raised the extremely interesting question of what “groundbreaking capabilities” the Director of National Intelligence was referring to.  I said my personal guess was that, with ~99% probability, he meant various implementation vulnerabilities and side-channel attacks—the sort of thing that we know has compromised deployed cryptosystems many times in the past, but where it’s very easy to believe that the NSA is ahead of the open world.  With ~1% probability, I guessed, the NSA made some sort of big improvement in classical algorithms for factoring, discrete log, or other number-theoretic problems.  (I would’ve guessed even less than 1% probability for the latter, before the recent breakthrough by Joux solving discrete log in fields of small characteristic in quasipolynomial time.)

Then, on Thursday, a big New York Times article appeared, based on 50,000 or so documents that Snowden leaked to the Guardian and that still aren’t public.  (See also an important Guardian piece by security expert Bruce Schneier, and accompanying Q&A.)  While a lot remains vague, there might be more public information right now about current NSA cryptanalytic capabilities than there’s ever been.

So, how did my uninformed, armchair guesses fare?  It’s only halfway into the NYT article that we start getting some hints:

The files show that the agency is still stymied by some encryption, as Mr. Snowden suggested in a question-and-answer session on The Guardian’s Web site in June.

“Properly implemented strong crypto systems are one of the few things that you can rely on,” he said, though cautioning that the N.S.A. often bypasses the encryption altogether by targeting the computers at one end or the other and grabbing text before it is encrypted or after it is decrypted…

Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency’s success depends on working with Internet companies — by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware…

Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members.

Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

So, in pointing to implementation vulnerabilities as the most likely possibility for an NSA “breakthrough,” I might have actually erred a bit too far on the side of technological interestingness.  It seems that a large part of what the NSA has been doing has simply been strong-arming Internet companies and standards bodies into giving it backdoors.  To put it bluntly: sure, if it wants to, the NSA can probably read your email.  But that isn’t mathematical cryptography’s fault—any more than it would be mathematical crypto’s fault if goons broke into your house and carted away your laptop.  On the contrary, properly-implemented, backdoor-less strong crypto is something that apparently scares the NSA enough that they go to some lengths to keep it from being widely used.

I should add that, regardless of how NSA collects all the private information it does—by “beating crypto in a fair fight” (!) or, more likely, by exploiting backdoors that it itself installed—the mere fact that it collects so much is of course unsettling enough from a civil-liberties perspective.  So I’m glad that the Snowden revelations have sparked a public debate in the US about how much surveillance we as a society want (i.e., “the balance between preventing 9/11 and preventing Orwell”), what safeguards are in place to prevent abuses, and whether those safeguards actually work.  Such a public debate is essential if we’re serious about calling ourselves a democracy.

At the same time, to me, perhaps the most shocking feature of the Snowden revelations is just how unshocking they’ve been.  So far, I haven’t seen anything that shows the extent of NSA’s surveillance to be greater than what I would’ve considered plausible a priori.  Indeed, the following could serve as a one-sentence summary of what we’ve learned from Snowden:

Yes, the NSA is, in fact, doing the questionable things that anyone not living in a cave had long assumed they were doing—that assumption being so ingrained in nerd culture that countless jokes are based around it.

(Come to think of it, people living in caves might have been even more certain that the NSA was doing those things.  Maybe that’s why they moved to caves.)

So, rather than dwelling on civil liberties, national security, yadda yadda yadda, let me move on to discuss the implications of the Snowden revelations for something that really matters: a 6-year-old storm in theoretical computer science’s academic teacup.  As many readers of this blog might know, Neal Koblitz—a respected mathematician and pioneer of elliptic curve cryptography, who (from numerous allusions in his writings) appears to have some connections at the NSA—published a series of scathing articles, in the Notices of the American Mathematical Society and elsewhere, attacking the theoretical computer science approach to cryptography.  Koblitz’s criticisms were varied and entertainingly-expressed: the computer scientists are too sloppy, deadline-driven, self-promoting, and corporate-influenced; overly trusting of so-called “security proofs” (a term they shouldn’t even use, given how many errors and exaggerated claims they make); absurdly overreliant on asymptotic analysis; “bodacious” in introducing dubious new hardness assumptions that they then declare to be “standard”; and woefully out of touch with cryptographic realities.  Koblitz seemed to suggest that, rather than demanding the security reductions so beloved by theoretical computer scientists, people would do better to rest the security of their cryptosystems on two alternative pillars: first, standards set by organizations like the NSA with actual real-world experience; and second, the judgments of mathematicians with … taste and experience, who can just see what’s likely to be vulnerable and what isn’t.

Back in 2007, my mathematician friend Greg Kuperberg pointed out the irony to me: here we had a mathematician, lambasting computer scientists for trying to do for cryptography what mathematics itself has sought to do for everything since Euclid!  That is, when you see an unruly mess of insights, related to each other in some tangled way, systematize and organize it.  Turn the tangle into a hierarchical tree (or dag).  Isolate the minimal assumptions (one-way functions?  decisional Diffie-Hellman?) on which each conclusion can be based, and spell out all the logical steps needed to get from here to there—even if the steps seem obvious or boring.  Any time anyone has tried to do that, it’s been easy for the natives of the unruly wilderness to laugh at the systematizing newcomers: the latter often know the terrain less well, and take ten times as long to reach conclusions that are ten times less interesting.  And yet, in case after case, the clarity and rigor of the systematizing approach has eventually won out.  So it seems weird for a mathematician, of all people, to bet against the systematizing approach when applied to cryptography.

The reason I’m dredging up this old dispute now, is that I think the recent NSA revelations might put it in a slightly new light.  In his article—whose main purpose is to offer practical advice on how to safeguard one’s communications against eavesdropping by NSA or others—Bruce Schneier offers the following tip:

Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can.

Here Schneier is pointing out a specific issue with ECC, which would be solved if we could “merely” ensure that NSA or other interested parties weren’t providing input into which elliptic curves to use.  But I think there’s also a broader issue: that, in cryptography, it’s unwise to trust any standard because of the prestige, real-world experience, mathematical good taste, or whatever else of the people or organizations proposing it.  What was long a plausible conjecture—that the NSA covertly influences cryptographic standards to give itself backdoors, and that otherwise-inexplicable vulnerabilities in deployed cryptosystems are sometimes there because the NSA wanted them there—now looks close to an established fact.  In cryptography, then, it’s not just for idle academic reasons that you’d like a publicly-available trail of research papers and source code, open to criticism and improvement by anyone, that takes you all the way from the presumed hardness of an underlying mathematical problem to the security of your system under whichever class of attacks is relevant to you.

Schneier’s final piece of advice is this: “Trust the math.  Encryption is your friend.”

“Trust the math.”  On that note, here’s a slightly-embarrassing confession.  When I’m watching a suspense movie (or a TV show like Homeland), and I reach one of those nail-biting scenes where the protagonist discovers that everything she ever believed is a lie, I sometimes mentally recite the proof of the Karp-Lipton Theorem.  It always calms me down.  Even if the entire universe turned out to be a cruel illusion, it would still be the case that NP ⊂ P/poly would collapse the polynomial hierarchy, and I can tell you exactly why.  It would likewise be the case that you couldn’t break the GGM pseudorandom function without also breaking the underlying pseudorandom generator on which it’s based.  Math could be defined as that which can still be trusted, even when you can’t trust anything else.

Microsoft: From QDOS to QMA in less than 35 years

Friday, July 19th, 2013

This past week I was in Redmond for the Microsoft Faculty Summit, which this year included a special session on quantum computing.  (Bill Gates was also there, I assume as our warmup act.)  I should explain that Microsoft Research now has not one but two quantum computing research groups: there’s Station Q in Santa Barbara, directed by Michael Freedman, which pursues topological quantum computing, but there’s also QuArC in Redmond, directed by Krysta Svore, which studies things like quantum circuit synthesis.

Anyway, I’ve got two videos for your viewing pleasure:

  • An interview about quantum computing with me, Krysta Svore, and Matthias Troyer, moderated by Chris Cashman, and filmed in a studio where they put makeup on your face.  Just covers the basics.
  • A session about quantum computing, with three speakers: me about “what quantum mechanics is good for” (quantum algorithms, money, crypto, and certified random numbers), then Charlie Marcus about physical implementations of quantum computing, and finally Matthias Troyer about his group’s experiments on the D-Wave machines.  (You can also download my slides here.)

This visit really drove home for me that MSR is the closest thing that exists today to the old Bell Labs: a corporate lab that does a huge amount of openly-published, high-quality fundamental research in math and CS, possibly more than all the big Silicon-Valley-based companies combined.  This research might or might not be good for Microsoft’s bottom line (Microsoft, of course, says that it is, and I’d like to believe them), but it’s definitely good for the world.  With the news of Microsoft’s reorganization in the background, I found myself hoping that MS will remain viable for a long time to come, if only because its decline would leave a pretty gaping hole in computer science research.

Unfortunately, last week I also bought a new laptop, and had the experience of PowerPoint 2013 first refusing to install (it mistakenly thought it was already installed), then crashing twice and losing my data, and just generally making everything (even saving a file) harder than it used to be for no apparent reason.  Yes, that’s correct: the preparations for my talk at the Microsoft Faculty Summit were repeatedly placed in jeopardy by the “new and improved” Microsoft Office.  So not just for its own sake, but for the sake of computer science as a whole, I implore Microsoft to build a better Office.  It shouldn’t be hard: it would suffice to re-release the 2003 or 2007 versions as “Office 2014″!  If Mr. Gates took a 2-minute break from curing malaria to call his former subordinates and tell them to do that, I’d really consider him a great humanitarian.

The Collision Lower Bound After 12 Years

Sunday, July 7th, 2013

Streaming video is now available for the talks at the QStart conference, a couple weeks ago at Hebrew University in Jerusalem.  If you’re the sort of person who likes watching quantum information talks, then check out the excellent ones by Ray Laflamme, John Martinis, Umesh Vazirani, Thomas Vidick, Jacob Bekenstein, and many others.

My own contribution—the first “backwards-facing, crusty, retrospective” talk I’ve ever given—was called The Collision Lower Bound After 12 Years (click here for the slides—and to answer the inevitable question, no, I have no idea how to open PowerPoint files in your favorite free-range, organic computing platform).  Briefly, the collision lower bound is the theorem that even a quantum computer needs at least ~n1/3 steps to find a duplicate in a long list of random numbers between 1 and n, even assuming the list is long enough that there are many, many duplicates to be found.  (Moreover, ~n1/3 steps are known to suffice, by the BHT algorithm, a clever adaptation of Grover’s search algorithm.  Also, for simplicity a “step” means a single access to the list, though of course a quantum algorithm can access multiple list elements in superposition and it still counts as one step.)

By comparison, for classical algorithms, ~√n steps are necessary and sufficient to find a collision, by the famous Birthday Paradox.  So, just like for Grover’s search problem, a quantum computer could give you a modest speedup over classical for the collision problem, but only a modest one.  The reason this is interesting is that, because of the abundance of collisions to be found, the collision problem has a great deal more structure than Grover’s search problem (though it has less structure than Shor’s period-finding problem, where there famously is an exponential quantum speedup).

One “obvious” motivation for the collision problem is that it models the problem of breaking collision-resistant hash functions (like SHA-256) in cryptography.  In particular, if there were a superfast (e.g., log(n)-time) quantum algorithm for the collision problem, then there could be no CRHFs secure against quantum attack.  So the fact that there’s no such algorithm at least opens up the possibility of quantum-secure CRHFs.  However, there are many other motivations.  For example, the collision lower bound rules out the most “simpleminded” approach to a polynomial-time quantum algorithm for the Graph Isomorphism problem (though, I hasten to add, it says nothing about more sophisticated approaches).  The collision problem is also closely related to Statistical Zero Knowledge (SZK) proof protocols, so that the collision lower bound leads to an oracle relative to which SZK is not in BQP.

Probably the most bizarre motivation to other people, but for some reason the most important one to me back in 2001, is that the collision problem is closely related to the problem of sampling the entire trajectories of hidden variables, in hidden-variable theories such as Bohmian mechanics.  The collision lower bound provides strong evidence that this trajectory-sampling problem is hard even for a quantum computer—intuitively because a QC can’t keep track of the correlations between the hidden-variable positions at different times.  The way I like to put it is that if, at the moment of your death, your entire life history flashed before you in an instant (and if a suitable hidden-variable theory were true, and if you’d performed an appropriate quantum interference experiment on your own brain during your life), then you really could solve the collision problem in only O(1) steps.  Interestingly, you still might not be able to solve NP-complete problems—I don’t know!  But you could at least do something that we think is hard for a quantum computer.

I proved the first collision lower bound in 2001 (actually, a week or so after the 9/11 attacks), after four months of sleepless nights and failed attempts.  (Well actually, I only got the weaker lower bound of ~n1/5; the ~n1/3 was a subsequent improvement due to Yaoyun Shi.  Before ~n1/5, no one could even rule out that a quantum computer could solve the collision problem with a constant number of steps (!!), independent of n—say, 4 steps.)  It was the first thing I’d proved of any significance, and probably the most important thing I did while in grad school.  I knew it was one of the favorite problems of my adviser, Umesh Vazirani, so I didn’t even tell Umesh I was working on it until I’d already spent the whole summer on it.  I figured he’d think I was nuts.

Bonus Proof Explanation!

The technique that ultimately worked was the polynomial method, which was introduced to quantum computing four years prior in a seminal paper of Beals et al.  In this technique, you first suppose by contradiction that a quantum algorithm exists to solve your problem that makes very few accesses to the input bits—say, T.  Then you write out the quantum algorithm’s acceptance probability (e.g., the probability that the algorithm outputs “yes, I found what I was looking for”) as a multivariate polynomial p in the input bits.  It’s not hard to prove that p has degree at most 2T, since the amplitudes in the quantum algorithm can be written as degree-T polynomials (each input access increases the degree by at most 1, and unitary transformations in between input accesses don’t increase the degree at all); then squaring the amplitudes to get probabilities doubles the degree.  (This is the only part of the method that uses anything specific to quantum mechanics!)

Next, you choose some parameter k related to the problem of interest, and you let q(k) be the expectation of p(X) over all inputs X with the parameter equal to k.  For example, with the collision problem, it turns out that the “right” choice to make is to set k=1 if each number appears exactly once in your input list, k=2 if each number appears exactly twice, k=3 if each number appears exactly three times, and so on.  Then—here comes the “magic” part—you show that q(k) itself is a univariate polynomial in k, again of degree at most 2T.  This magical step is called “symmetrization”; it can be traced at least as far back as the famous 1969 book Perceptrons by Marvin Minsky and Seymour Papert.  In the case of the collision problem, I still have no explanation, 12 years later, for why symmetrization works: all I can say is that you do the calculation, and you cancel lots of things from both the numerator and the denominator, and what comes out at the end is a low-degree polynomial in k.  (It’s precisely because I would never have predicted such a “zany coincidence,” that I had to stumble around in the dark for 4 months before I finally discovered by chance that the polynomial method worked.)

Anyway, after applying symmetrization, you’re left with a low-degree univariate polynomial q with some very interesting properties: for example, you need 0≤q(k)≤1 for positive integers k, since then q(k) represents an averaged probability that your quantum algorithm does something.  You also need q(1) to be close to 0, since if k=1 then there no collisions to be found, and you need q(2) to be close to 1, since if k=2 then there are lots of collisions and you’d like your algorithm to find one.  But now, you can appeal to a theorem of A. A. Markov from the 1890s, which implies that no low-degree polynomial exists with those properties!  Hence your original efficient quantum algorithm can’t have existed either: indeed, you get a quantitative lower bound (a tight one, if you’re careful) on the number of input accesses your algorithm must have made.  And that, modulo some nasty technicalities (e.g., what if k doesn’t evenly divide the size of your list?), is how the collision lower bound works.

So, in the first half of my QStart talk, I explain the collision lower bound and its original motivations (and a little about the proof, but no more than what I said above).  Then in the second half, I survey lots of extensions and applications between 2002 and the present, as well as the many remaining open problems.  For example, I discuss the tight lower bound of Ambainis et al. for the “index erasure” problem, Belovs’s proof of the element distinctness lower bound using the adversary method, and my and Ambainis’s generalization of the collision lower bound to arbitrary symmetric problems.  I also talk about Mark Zhandry’s recent breakthrough (sorry, am I not allowed to use that word?) showing that the GGM construction of pseudorandom functions is secure against quantum adversaries, and how Zhandry’s result can be seen—in retrospect, anyway—as yet another application of the collision lower bound.

Probably of the most general interest, I discuss how Daniel Harlow and Patrick Hayden invoked the collision lower bound in their striking recent paper on the AMPS black hole “firewall” paradox.  In particular they argued that, in order to uncover the apparent violation of local quantum field theory at the heart of the paradox, an observer falling into a black hole would probably need to solve a QSZK-complete computational problem.  And of course, the collision lower bound furnishes our main piece of evidence that QSZK-complete problems really should require exponential time even for quantum computers.  So, Harlow and Hayden argue, the black hole would already have evaporated before the observer had even made a dent in the requisite computation.

Now, the Harlow-Hayden paper, and the AMPS paradox more generally, really deserve posts of their own—just as soon as I learn enough to decide what I think about them.  For now, I’ll simply say that, regardless of how convinced you are by Harlow and Hayden’s argument (and, a bit like with my free-will essay, it’s not clear how convinced the authors themselves are!), it’s one of the most ambitious syntheses of computational complexity and physics I’ve ever seen.  You can disagree with it, but to read the paper (or watch the talk, streaming video from Strings’2013 here) is to experience the thrill of seeing black hole physics related to complexity theory by authors who really know both.

(In my own talk on the collision lower bound, the short segment about Harlow-Hayden generated more questions and discussion than the rest of the talk combined—with me being challenged to defend their argument, even with Patrick Hayden right there in the audience!  I remarked later that that portion of the talk was itself a black hole for audience interest.)

In totally unrelated news, Quantum Computing Since Democritus made Scientific American’s list of best summer books!  I can’t think of a more appropriate honor, since if there’s any phrase that captures what QCSD is all about, “sizzling summer beach read” would be it.  Apparently there will even be an online poll soon, where y’all can go and vote for QCSD as your favorite.  Vote early and often, and from multiple IP addresses!

“Closer to Truth”

Wednesday, May 1st, 2013

Two years ago, when I attended the FQXi conference on a ship from Norway to Denmark, I (along with many other conference participants) was interviewed by Robert Lawrence Kuhn, who produces a late-night TV program called “Closer to Truth.”  I’m pleased to announce (hat tip: Sean Carroll) that four videos from my interview are finally available online:

  • Is the Universe a Computer?
  • (like a politician, I steer the question toward “what kind of computer is the universe?,” then start talking about P vs. NP, quantum computing, and the holographic principle)

  • What Does Quantum Theory Mean?
  • (here I mostly talk about the idea of computational intractability as a principle of physics)

  • Quantum Computing Mysteries
  • (basics of quantum mechanics and quantum computing)

  • Setting Time Aright (about the differences between time and space, the P vs. PSPACE problem, and computing with closed timelike curves)

(No, I didn’t choose the titles!)

For regular readers of this blog, there’s probably nothing new in these videos, but for those who are “just tuning in,” they provide an extremely simple and concise introduction to what I care about and why.  I’m pretty happy with how they came out.

Once you’re finished with me (or maybe even before then…), click here for the full list of interviewees, which includes David Albert, Raphael Bousso, Sean Carroll, David Deutsch, Rebecca Goldstein, Seth Lloyd, Marvin Minsky, Roger Penrose, Lenny Susskind, Steven Weinberg, and many, many others who might be of interest to Shtetl-Optimized readers.

“So You Think Quantum Computing Is Bunk?”

Friday, April 12th, 2013

On Wednesday, I gave a fun talk with that title down the street at Microsoft Research New England.  Disappointingly, no one in the audience did seem to think quantum computing was bunk (or if they did, they didn’t speak up): I was basically preaching to the choir.  My PowerPoint slides are here.  There’s also a streaming video here, but watch it at your own risk—my stuttering and other nerdy mannerisms seemed particularly bad, at least in the short initial segment that I listened to.  I really need media training.  Anyway, thanks very much to Boaz Barak for inviting me.

Two P vs. NP updates (neither of them technical)

Tuesday, April 2nd, 2013

“Meme” courtesy of my brother David

First news item: it’s come to my attention that yesterday, an MIT professor abused his power over students for a cruel April Fools’ Day prank involving the P vs. NP problem.  His email to the students is below.

I assume most of you already heard the news that a Caltech grad student, April Felsen, announced a 400-page proof of P≠NP last week.  While I haven’t yet completely digested the argument, it’s already clear that Felsen (who I actually knew back when she was an MIT undergrad) has changed theoretical computer science forever, bringing in new tools from K-theory to higher topos theory to solve the biggest problem there was.

Alas, Felsen’s proof has the “short-term” effect of making the existing 6.045 seem badly outdated.  So, after long reflection, I’ve made a decision that not all of you are going to like, but that I believe is the right one intellectually.  I’ve decided to reorient the entire course to focus on Felsen’s result, starting with tomorrow’s lecture.

And further, I decided to rewrite Thursday’s midterm to focus almost entirely on this new material.  That means that, yes, you’re going to have THREE DAYS to learn at least the basics of algebraic topology and operator algebras, as used in Felsen’s proof.  To do that, you might need to drop everything else (including sleep, unfortunately), and this might prove to be the most strenuous and intense thing you’ve ever done.  But it will also be an experience that will enrich your minds and ennoble your souls, and that you’ll be proud to tell your grandchildren about.  And of course we’ll be there to help out.  So let’s get started!

All the best,

Second news item: many of you have probably heard that Lance Fortnow’s The Golden Ticket—the first popular book about the P vs. NP problem—is now out.  (The title refers to Roald Dahl’s Charlie and the Chocolate Factory, which involved a few chocolate bars that had coveted golden tickets inside the wrappers, along with millions of chocolate bars that didn’t.)  I read it last week, and I think it’s excellent: a book I’ll happily recommend to family and friends who want the gentlest introduction to complexity theory that exists.

Some context: for more than a decade, people have been telling me that I should write a popular book about P vs. NP, and I never did, and now Lance has.  So I’m delighted to say that reading Lance’s book quickly cured me of any regrets I might have felt.  For not only is The Golden Ticket a great book, but better yet, it’s not a book that I ever could’ve written.

Here’s why: every time I would have succumbed to the temptation to explain something too complicated for the world’s journalists, literary humanists, and pointy-haired bosses—something like relativization, or natural proofs, or arithmetization, or Shannon’s counting argument, or Ladner’s Theorem, or coNP, or the reasons to focus on polynomial time—every time, Lance somehow manages to resist the temptation, and to stick to cute stories, anecdotes, and practical applications.  This is really, truly a popular book: as Lance points out himself, in 162 pages of discussing the P vs. NP question, he never even formally defines P and NP!

But it goes beyond that: in the world of The Golden Ticket, P vs. NP is important because, if P=NP, then people could design more effective cancer therapies, solve more crimes, and better predict which baseball games would be closely-matched and exciting (yes, really).  P vs. NP is also important because it provides a unifying framework for understanding current technological trends, like massively-parallel computing, cloud computing, big data, and the Internet of things.  Meanwhile, quantum computing might or might not be possible in principle, but either way, it’s probably not that relevant because it won’t be practical for a long time.

In short, Lance has written precisely the book about P vs. NP that the interested layperson or IT professional wants and needs, and precisely the book that I couldn’t have written.  I would’ve lost patience by around page 20, and exclaimed:

“You want me to justify the P vs. NP problem by its relevance to baseball??  Why shouldn’t baseball have to justify itself by its relevance to P vs. NP?  Pshaw!  Begone from the house of study, you cretinous fools, and never return!”

My favorite aspect of The Golden Ticket was its carefully-researched treatment of the history of the P vs. NP problem in the 50s, 60s, and 70s, both in the West and in the Soviet Union (where it was called the “perebor” problem).  Even complexity theorists will learn countless tidbits—like how Leonid Levin was “discovered” at age 15, and how the powerful Sergey Yablonsky stalled Soviet perebor research by claiming to have solved the problem when he’d done nothing of the kind.  The historical chapter (Chapter 5) is alone worth the price of the book.

I have two quibbles.  First, throughout the book, Lance refers to a hypothetical world where P=NP as the “Beautiful World.”  I would’ve called that world the “Hideous World”!  For it’s a world where technical creativity is mostly worthless, and where the mathematical universe is boring, flat, and incomprehensibly comprehensible.  Here’s an analogy: suppose a video game turned out to have a bug that let you accumulate unlimited points just by holding down a certain button.  Would anyone call that game the “Beautiful Game”?

My second disagreement concerns quantum computing.  Overall, Lance gives an admirably-accurate summary, and I was happy to see him throw cold water on breathless predictions about QC and other quantum-information technologies finding practical applications in the near future.  However, I think he goes beyond the truth when he writes:

[W]e do not know how to create a significant amount of entanglement in more than a handful of quantum bits.  It might be some fundamental rule of nature that prevents significant entanglement for any reasonable length of time.  Or it could just be a tricky engineering problem.  We’ll have to let the physicists sort that out.

The thing is, physicists do know how to create entanglement among many thousands or even millions of qubits—for example, in condensed-matter systems like spin lattices, and in superconducting Josephson junctions.  The problem is “merely” that they don’t know how to control the entanglement in the precise ways needed for quantum computing.  But as with much quantum computing skepticism, the passage above doesn’t seem to grapple with just how hard it is to kill off scalable QC.  How do you cook up a theory that can account for the massively-entangled states that have already been demonstrated, but that doesn’t give you all of BQP?

But let me not harp on these minor points, since The Golden Ticket has so many pleasant features.  One of them is its corny humor: even in Lance’s fantasy world where a proof of P=NP has led to a cure for cancer, it still hasn’t led to a cure for the common cold.  Another nice feature is the book’s refreshing matter-of-factness: Lance makes it clear that he believes that

(a) P≠NP,
(b) the conjecture is provable but won’t be proven in the near future, and
(c) if we ever meet an advanced extraterrestrial civilization, they’ll also have asked the P vs. NP question or something similar to it.

Of course we can’t currently prove any of the above statements, just like we can’t prove the nonexistence of Bigfoot.  But Lance refuses to patronize his readers by pretending to harbor doubts that he quite reasonably doesn’t.

In summary, if you’re the sort of person who stops me in elevators to say that you like my blog even though you never actually understand anything in it, then stop reading Shtetl-Optimized right now and go read Lance’s book.  You’ll understand it and you’ll enjoy it.

And now it’s off to class, to apologize for my April Fools prank and to teach the Cook-Levin Theorem.

Quantum Computing Since Democritus: The Buzz Intensifies

Thursday, March 21st, 2013

Update (March 22): The Kindle edition of Quantum Computing Since Democritus is now available, for the low price of $15.40!  (Not factorial.)  Click here to get it from, or here to get it from  And let me know how it looks (I haven’t seen it yet).  Another Update: Just saw the Kindle edition, and the figures and formulas came out great!  It’s a product I stand behind with pride.

In the meantime, I regret to say that the marketing for this book is getting crasser and more exploitative by the day.



It seems like wherever I go these days, all anyone wants to talk about is Quantum Computing Since Democritus—the sprawling new book by Scott Aaronson, published by Cambridge University Press and available for order now.  Among leading figures in quantum information science—many of them well-known to Shtetl-Optimized readers—the book is garnering the sort of hyperbolic praise that would make Shakespeare or Tolstoy blush:

“I laughed, I cried, I fell off my chair – and that was just reading the chapter on Computational Complexity.  Aaronson is a tornado of intellectual activity: he rips our brains from their intellectual foundations; twists them through a tour of physics, mathematics, computer science, and philosophy; stuffs them full of facts and theorems; tickles them until they cry ‘Uncle'; and then drops them, quivering, back into our skulls.  Aaronson raises deep questions of how the physical universe is put together and why it is put together the way it is.  While we read his lucid explanations we can believe – at least while we hold the book in our hands – that we understand the answers, too.” –Seth Lloyd

“Scott Aaronson has written a beautiful and highly original synthesis of what we know about some of the most fundamental questions in science: What is information? What does it mean to compute? What is the nature of mind and of free will?” –Michael Nielsen

“Not since Richard Feynman’s Lectures on Physics has there been a set of lecture notes as brilliant and as entertaining.  Aaronson leads the reader on a wild romp through the most important intellectual achievements in computing and physics, weaving these seemingly disparate fields into a captivating narrative for our modern age of information.  Aaronson wildly runs through the fields of physics and computers, showing us how they are connected, how to understand our computational universe, and what questions exist on the borders of these fields that we still don’t understand.   This book is a poem disguised as a set of lecture notes.  The lectures are on computing and physics, complexity theory and mathematical logic and quantum physics.  The poem is made up of proofs, jokes, stories, and revelations, synthesizing the two towering fields of computer science and physics into a coherent tapestry of sheer intellectual awesomeness.” –Dave Bacon

After months of overhearing people saying things like the above—in the halls of MIT, the checkout line at Trader Joe’s, the bathroom, anywhere—I finally had to ask in annoyance: “is all this buzz justified?  I mean, I’m sure the book is as deep, hilarious, and worldview-changing as everyone says it is.  But, after all, it’s based off lecture notes that have long been available for free on the web.  And Aaronson, being the magnanimous, open-access-loving saint that he is, has no plans to remove the online notes, even though he could really use the royalties from book sales to feed his growing family.  Nor does Cambridge University Press object to his principled decision.”

“No, you don’t understand,” they told me.  “Word on the street has it that the book is extensively updated for 2013—that it’s packed with new discussions of things like algebrization, lattice-based cryptography, the QIP=PSPACE theorem, the ‘quantum time travel controversy,’ BosonSampling, black-hole firewalls, and even the Australian models episode.  They say it took years of painstaking work, by Aaronson and his student Alex Arkhipov, to get the notes into book form: fixing mistakes, clarifying difficult points, smoothing out rough edges, all while leaving intact the original’s inimitable humor.  I even heard Aaronson reveals he’s changed his mind about certain things since 2006.  How could you not want such a labor of love on your bookshelf?”

Exasperated, I finally exclaimed: “But the book isn’t even out yet in North America! says it won’t ship until April 30.”

“Sure,” one gas-station attendant replied to me, “but the secret is, it’s available now from  Personally, I couldn’t wait a month, so I ordered it shipped to me from across the pond.  But if you’re a less hardcore quantum complexity theory fan, and you live in North America, you can also preorder the book from, and they’ll send it to you when it arrives.”

Much as the hype still grated, I had to admit that I’d run out of counterarguments, so I looked into ordering a copy for myself.

Silvio and Shafi win Turing Award

Wednesday, March 13th, 2013

Today I break long radio silence to deliver some phenomenal news.  Two of the people who I eat lunch with every week—my MIT CSAIL colleagues Silvio Micali and Shafi Goldwasser—have won a well-deserved Turing Award, for their fundamental contributions to cryptography from the 1980s till today.  (I see that Lance just now beat me to a blog post about this.  Dammit, Lance!)

I won’t have to tell many readers of this blog that the names Goldwasser and Micali—or more often, the initials “G” and “M”—are as ubiquitous as Alice and Bob in modern cryptography, from the GGM construction of pseudorandom functions (discussed before on this blog), to the classic GMR paper that introduced the world to interactive proofs.  Besides that, Shafi and Silvio are known as two of the more opinionated and colorful characters of theoretical computer science—and as I learned last week, Silvio is also an awesome party host, who has perfect taste in sushi (as well as furniture and many other things).

I wish I could go on right now talking about Shafi and Silvio—and even more, that I could join the celebration that will happen at MIT this afternoon.  But I’m about to board a flight to LAX, to attend the 60th birthday symposium of longtime friend, extraordinary physicist, and sometime Shtetl-Optimized commenter John Preskill.  (I’ll also be bringing you coverage of that symposium, including slides from my talk there on hidden variables.)  So, leave your congratulations, etc. in the comments section, and I’ll see them when I land!

TCS+ online seminars

Tuesday, January 29th, 2013

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.

“Quantum Information and the Brain”

Thursday, January 24th, 2013

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!)