## Archive for the ‘Announcements’ Category

### Twitl-Optimized

Tuesday, August 13th, 2013

Today I experiment with “tweeting”: writing <=140-character announcements, but posting them to my blog.  Like sending lolcat videos by mail

Last week at QCrypt in Waterloo: http://2013.qcrypt.net This week at CQIQC in Toronto: http://tinyurl.com/kfexzv6 Back with Lily in between

While we debate D-Wave, ID Quantique et al. quietly sold ~100 quantum crypto devices. Alas, market will remain small unless RSA compromised

One speaker explained how a photon detector works by showing this YouTube video: http://tinyurl.com/k8x4btx Couldn’t have done better

Luca Trevisan asks me to spread the word about a conference for LGBTs in technology: www.outforundergrad.org/technology

Steven Pinker stands up for the Enlightenment in The New Republic: “Science Is Not Your Enemy” http://tinyurl.com/l26ppaf

Think Pinker was exaggerating?  Read Leon Wieseltier’s defiantly doofusy Brandeis commencement speech: http://tinyurl.com/jwhj8ub

Black-hole firewalls make the New York Times, a week before the firewall workshop at KITP (I’ll be there): http://tinyurl.com/kju9crj

You probably already saw the Schrodinger cat Google doodle: http://tinyurl.com/k8et44p For me, the ket was much cooler than the cat

While working on BosonSampling yesterday, (1/6)pi^2 and Euler-Mascheroni constant made unexpected unappearances.  What I live for

### The SuperScott and Morgan Freeman FAQ

Monday, August 5th, 2013

Update (Sept. 3): When I said that “about 5000 steps” are needed for the evolutionary approach to color an 8×8 chessboard, I was counting as a step any examination of two random adjacent squares—regardless of whether or not you end up having to change one of the colors.  If you count only the changes, then the expected number goes down to about 1000 (which, of course, only makes the point about the power of the evolutionary approach “stronger”).  Thanks very much to Raymond Cuenen for bringing this clarification to my attention.

Last week I appeared on an episode of Through the Wormhole with Morgan Freeman, a show on the Science Channel.  (See also here for a post on Morgan Freeman’s Facebook page.)  The episode is called “Did God Create Evolution?”  The first person interviewed is the Intelligent Design advocate Michael Behe.  But not to worry!  After him, they have a parade of scientists who not only agree that Chuck Darwin basically had it right in 1859, but want to argue for that conclusion using ROBOTS!  and MATH!

So, uh, that’s where I come in.  My segment features me (or rather my animated doppelgänger, “SuperScott”) trying to color a chessboard two colors, so that no two neighboring squares are colored the same, using three different approaches: (1) an “intelligent design” approach (which computer scientists would call nondeterminism), (2) a brute-force, exhaustive enumeration approach, and (3) an “evolutionary local search” approach.

[Spoiler alert: SuperScott discovers that the local search approach, while not as efficient as intelligent design, is nevertheless much more efficient than brute-force search.  And thus, he concludes, the arguments of the ID folks to the effect of "I can't see a cleverer way to do it, therefore it must be either brute-force search or else miraculous nondeterminism" are invalid.]

Since my appearance together with Morgan Freeman on cable TV raises a large number of questions, I’ve decided to field a few of them in the following FAQ.

Q: How can I watch?

Amazon Instant Video has the episode here for $1.99. (No doubt you can also find it on various filesharing sites, but let it be known that I’d never condone such nefarious activity.) My segment is roughly from 10:40 until 17:40. Q: Given that you’re not a biologist, and that your research has basically nothing to do with evolution, why did they ask to interview you? Apparently they wanted a mathematician or computer scientist who also had some experience spouting about Big Ideas. So they first asked Greg Chaitin, but Chaitin couldn’t do it and suggested me instead. Q: Given how little relevant expertise you have, why did you agree to be interviewed? To be honest, I was extremely conflicted. I kept saying, “Why don’t you interview a biologist? Or at least a computational biologist, or someone who studies genetic algorithms?” They replied that they did have more bio-oriented people on the show, but they also wanted me to provide a “mathematical” perspective. So, I consulted with friends like Sean Carroll, who’s appeared on Through the Wormhole numerous times. And after reflection, I decided that I do have a way to explain a central conceptual point about algorithms, complexity, and the amount of time needed for natural selection—a point that, while hardly “novel,” is something that many laypeople might not have seen before and that might interest them. Also, as an additional argument in favor of appearing, MORGAN FREEMAN! So I agreed to do it, but only under two conditions: (1) At least one person with a biology background would also appear on the show, to refute the arguments of intelligent design. (2) I would talk only about stuff that I actually understood, like the ability of local search algorithms to avoid the need for brute-force search. I’ll let you judge for yourself to what extent these conditions were fulfilled. Q: Did you get to meet Morgan Freeman? Alas, no. But at least I got to hear him refer repeatedly to “SuperScott” on TV. Q: What was the shooting like? Extremely interesting. I know more now about TV production than I did before! It was a continuing negotiation: they kept wanting to say that I was “on a quest to mathematically prove evolution” (or something like that), and I kept telling them they weren’t allowed to say that, or anything else that would give the misleading impression that what I was saying was either original or directly related to my research. I also had a long discussion about the P vs. NP problem, which got cut for lack of time (now P and NP are only shown on the whiteboard). On the other hand, the crew was extremely accommodating: they really wanted to do a good job and to get things right. The most amusing tidbit: I knew that local search would take O(n4) time to 2-color an nxn chessboard (2-coloring being a special case of 2SAT, to which Schöning’s algorithm applies), but I didn’t know the constant. So I wrote a program to get the specific number of steps when n=8 (it’s about 5000). I then repeatedly modified and reran the program during the taping, as we slightly changed what we were talking about. It was the first coding I’d done in a while. Q: How much of the segment was your idea, and how much was theirs? The chessboard was my idea, but the “SuperScott” bit was theirs. Luddite that I am, I was just going to get down on hands and knees and move apples and oranges around on the chessboard myself. Also, they wanted me to speak in front of a church in Boston, to make a point about how many people believe that God created the universe. I nixed that idea and said, why not just do the whole shoot in the Stata Center? I mean, MIT spent$300 million just to make the building where I work as “visually arresting” as possible—at the expense of navigability, leakage-resilience, and all sorts of other criteria—so why not take advantage of it?  Plus, that way I’ll be able to crack a joke about how Stata actually looks like it was created by that favorite creationist strawman, a tornado passing through a junkyard.

Needless to say, all the stuff with me drawing complexity class inclusion diagrams on the whiteboard, reading my and Alex Arkhipov’s linear-optics paper, walking around outside with an umbrella, lifting the umbrella to face the camera dramatically—that was all just the crew telling me what to do.  (Well, OK, they didn’t tell me what to write on the whiteboard or view on my computer, just that it should be something sciencey.  And the umbrella thing wasn’t planned: it really just happened to be raining that day.)

Q: Don’t you realize that not a word of what you said was new—indeed, that all you did was to translate the logic of natural selection, which Darwin understood in 1859, into algorithms and complexity language?

Yes, of course, and I’m sorry if the show gave anyone the impression otherwise.  I repeatedly begged them not to claim newness or originality for anything I was saying.  On the other hand, one shouldn’t make the mistake of assuming that what’s obvious to nerds who read science blogs is obvious to everyone else: I know for a fact that it isn’t.

Q: Don’t you understand that you can’t “prove” mathematically that evolution by natural selection is really what happened in Nature?

Of course!  You can’t even prove mathematically that bears crap in the woods (unless crapping in the woods were taken as part of the definition of bears).  To the writers’ credit, they did have Morgan Freeman explain that I wasn’t claiming to have “proved” evolution.  Personally, I wish Freeman had gone even further—to say that, at present, we don’t even have mathematical theories that would explain from first principles why 4 billion years is a “reasonable” amount of time for natural selection to have gotten from the primordial soup to humans and other complex life, whereas (say) 40 million years is not a reasonable amount.  One could imagine such theories, but we don’t really have any.  What we do have is (a) the observed fact that evolution did happen in 4 billion years, and (b) the theory of natural selection, which explains in great detail why one’s initial intuition—that such evolution can’t possibly have happened by “blind, chance natural processes” alone—is devoid of force.

Q: Watching yourself presented in such a goony way—scribbling Complicated Math Stuff on a whiteboard, turning dramatically toward the camera, etc. etc.—didn’t you feel silly?

Some of it is silly, no two ways about it!  On the other hand, I feel satisfied that I got across at least one correct and important scientific point to hundreds of thousands of people.  And that, one might argue, is sufficiently worthwhile that it should outweigh any embarrassment about how goofy I look.

### Three announcements

Saturday, August 3rd, 2013

1. As many of you probably know, this week my EECS colleague Hal Abelson released his 180-page report on MIT’s involvement in the Aaron Swartz case.  I read the whole thing, and I recommend it if you have any interest in the case.  My take is that, far from being the “whitewash” that some people described it as, the report (if you delve into it) clearly and eloquently explains how MIT failed to live up to its own standards, even as it formally followed the rules.  The central insight here is that the world expects MIT to behave, not like some other organization would behave if someone hid a laptop in its supply closet to download the whole JSTOR database, insulted and then tried to flee from its security officers when questioned, etc. etc., but rather with perspective and imagination—worrying less about the security of its facilities than about the future of the world.  People expect MIT, of all places, to realize that the sorts of people who pull these sorts of shenanigans in their twenties sometimes become Steve Jobs or Richard Feynman (or for that matter, MIT professor Robert Morris) later in their lives, and therefore to speak up in their defense.  In retrospect, I wish Swartz’s arrest had sparked a debate about the wider issues among MIT’s students, faculty, and staff.  I think it’s likely that such a debate would have led to pressure on the administration to issue a statement in Swartz’s support.  As it was (and as I pointed out in this interview), most people at MIT, even if they’d read about the arrest, weren’t even aware of the issue’s continued existence, let alone of MIT’s continued role in it, until after Swartz had already committed suicide.  For the MIT community—which includes some prominent supporters of open access—to have played such a passive role is one of the many tragedies that’s obvious with hindsight.

2. Shafi Goldwasser has asked me to announce that the fifth Innovations in Theoretical Computer Science (ITCS) conference will be held in Princeton, a town technically in New Jersey, on January 12-14, 2014.  Here’s the conference website; if you want to submit a paper, the deadline is coming up soon, on Thursday, August 22.

3. As the summer winds to a close, I’m proud to announce my main goals for the upcoming academic year.  Those goals are the following:

(a) Take care of Lily.

(b) Finish writing up old papers.

It feels liberating to have no higher aspirations for an entire year—and for the aspirations I have to seem so modest and so achievable.  On the other hand, it will be all the more embarrassing if I fail to achieve even these goals.

### The Tenured Toll-Taker

Sunday, May 5th, 2013

Update (5/6): In “honor” of the news below, Boaz Barak has written a beautiful blog post on the reasons to care about the P vs. NP question, offering his responses to several of the most common misconceptions.  Thank you so much, Boaz — this is one of the best presents I’ve ever gotten from anyone!

On Friday afternoon—in the middle of a pizza social for my undergrad advisees—I found out that I’ve received tenure at MIT.

Am I happy about the news?  Of course!  Yet even on such a joyous occasion, I found myself reflecting on a weird juxtaposition.  I learned about MIT’s tenure decision at the tail end of a fierce, weeks-long comment war over on Luboš Motl’s blog, in which I assumed the task of defending theoretical computer science and quantum information science as a whole: explaining why these fields could have anything whatsoever to contribute to our understanding of the universe.  Indeed, I took the title of this post from a comment Luboš made to me in the middle of the melee: that compared to string theorists, quantum computing researchers have as much to say about the nature of reality as toll-takers on the Golden Gate Bridge.  (Even though the Golden Gate tolls are apparently all-electronic these days, I still found Luboš’s analogy striking.  I could imagine that staring all day at the breathtaking San Francisco Bay would lead to deep thoughts about the nature of reality.)

Now, some people will ask: why should I even waste my time this way—arguing with Luboš, a blogger infamous for describing the scientists he disagrees with as garbage, worms, fungi, etc., and even calling for their “elimination”?  If I find the limits of computation in the physical universe to be a rich, fascinating, worthwhile subject; if I have hundreds of wonderful colleagues with whom to share the thrill of surprising new discoveries; if a large, growing fraction of the wider scientific community follows this field with interest; if my employer seems to want me doing it for the long haul … then why should I lose sleep just because someone, somewhere, declared that the P vs. NP problem is a random puzzle, of no deeper significance than the question of whether chess is a draw?  Or because he characterized the entire fields of quantum computing and information as trivial footnotes to 1920s physics, fit only for mediocre students who couldn’t do string theory?  Or because, on the “other side,” a persistent minority calls quantum computers an absurd fantasy, and the quest to build them a taxpayer boondoggle bordering on fraud?  Or because some skeptics, going even further, dismiss quantum mechanics itself as nonsensical mumbo-jumbo that physicists made up to conceal their own failure to find a straightforward, mechanical description of Nature?  Likewise, why should it bother me if some anti-complexites dismiss the quest to prove P≠NP as a fashionable-but-irrelevant journey to formalize the obvious—even while others denounce the Soviet-style groupthink that leads the “CS establishment” to reject the possibility that P=NP?  After all, these various naysayers can’t all be right!  Doesn’t it comfort me that, of all the confidently-asserted reasons why everything my colleagues and I study is dead-end, cargo-cult science, so many of the reasons contradict each other?

Sure, but here’s the thing.  In seven years of teaching and blogging, I’ve learned something about my own psychology.  Namely, if I meet anyone—an undergrad, an anonymous blog commenter, anyone—who claims that the P vs. NP problem is beside the point, since it’s perfectly plausible that P=NP but the algorithm takes n10000 time—or that, while quantum mechanics works fine for small systems, there’s not the slightest reason to expect it to scale up to larger ones—or that the limits of computation are plainly no more relevant to fundamental physics than the fact that cucumbers are green—trying to reason with that person will always, till the end of my life, feel like the most pressing task in the world to me.

Why?  Because, I confess, a large part of me worries: what if this other person is right?  What if I really do have to jettison everything I thought I knew about physics, computation, and pretty much everything else since I was a teenager, toss all my results into the garbage can (or at least the “amusing recreations can”), and start over from kindergarten?  But then, as I fret about that possibility, counterarguments well up in my mind.  Like someone pinching himself to make sure he’s awake, I remember all the reasons why I was led to think what I think in the first place.  And I want the other person to go through that experience with me—the experience, if you like, of feeling the foundations of the universe smashed to pieces and then rebuilt, the infinite hierarchy of complexity classes collapsing and then springing back into place, decades’ worth of books set ablaze and then rewritten on blank pages.  I want to say: at least come stand here with me—in this place that I spent twenty years of late nights, false starts, and discarded preconceptions getting to—and tell me if you still don’t see what I see.

That’s how I am; I doubt I can change it any more than I can change my blood type.  So I feel profoundly grateful to have been born into a world where I can make a comfortable living just by being this strange, thin-skinned creature that I am—a world where there are countless others who do see what I see, indeed see it a thousand times more clearly in many cases, but who still appreciate what little I can do to explore this corner or that, or to describe the view to others.  I’d say I’m grateful to “fate,” but really I’m grateful to my friends and family, my students and teachers, my colleagues at MIT and around the world, and the readers of Shtetl-Optimized—yes, even John Sidles.  “Fate” either doesn’t exist or doesn’t need my gratitude if it does.

### Quantum Computing Since Democritus now out in the US! 20% discount for Shtetl-Optimized readers

Saturday, April 27th, 2013

OK, this will be my last blog post hawking Quantum Computing Since Democritus, at least for a while.  But I do have four pieces of exciting news about the book that I want to share.

1. Amazon is finally listing the print version of QCSD as available for shipment in North America, slightly ahead of schedule!  Amazon’s price is $35.27. 2. Cambridge University Press has very generously offered readers of Shtetl-Optimized a 20% discount off their list price—meaning$31.99 instead of $39.99—if you click this link to order directly from them. Note that CUP has a shipping charge of$6.50.  So ordering from CUP might either be slightly cheaper or slightly more expensive than ordering from Amazon, depending (for example) on whether you get free shipping from Amazon Prime.
3. So far, there have been maybe 1000 orders and preorders for QCSD (not counting hundreds of Kindle sales).  The book has also spent a month as one of Amazon’s top few “Quantum Physics” sellers, with a fabulous average rating of 4.6 / 5 stars from 9 reviews (or 4.9 if we discount the pseudonymous rant by Joy Christian).  Thanks so much to everyone who ordered a copy; I hope you like it!  Alas, these sales figures also mean that QCSD still has a long way to go before it enters the rarefied echelon of—to pick a few top Amazon science sellers—Cosmos, A Brief History of TimeProof of Heaven (A Neurosurgeon’s Journey into the Afterlife), Turn On Your SUPER BRAIN, or The Lemon Book (Natural Recipes and Preparations).  So, if you believe that QCSD deserves to be with such timeless classics, then put your money where your mouth is and help make it happen!
4. The most exciting news of all?  Luboš Motl is reading the free copy of QCSD that I sent him and blogging his reactions chapter-by-chapter!  So, if you’d like to learn about how mathematicians and computer scientists simply lack the brainpower to do physics—which is why we obsess over kindergarten trivialities like the Church-Turing Thesis or the Axiom of Choice, and why we insist idiotically that Nature use only the mathematical structures that our inferior minds can grasp—then check out Luboš’s posts about Chapters 1-3 or Chapters 4-6.  If, on the other hand, you want to see our diacritical critic pleasantly surprised by QCSD’s later chapters on cryptography, quantum mechanics, and quantum computing, then here’s the post for you.  Either way, be sure to scroll down to the comments, where I patiently defend the honor of theoretical computer science against Luboš’s hilarious ad hominem onslaughts.

### QStart conference in Jerusalem, June 24-27

Sunday, April 14th, 2013

Friend-of-the-blog Dorit Aharonov asked me to advertise the QStart Conference, which will be held at Hebrew University of Jerusalem June 24-27 of this year, to celebrate the opening of Hebrew University’s new Quantum Information Science Center.  Speakers include Yakir Aharonov, Jacob Bekenstein, Hans Briegel, Ed Farhi, Patrick Hayden, Ray Laflamme, Elon Lindenstrauss, Alex Lubotzky, John Martinis, Barbara Terhal, Umesh Vazirani, Stephanie Wehner, Andrew Yao … and me, your humble blogger (who will actually be there with Lily, on her first trip abroad—or for that matter, beyond the Boston metropolitan area).  Dorit tells me that the conference should be of interest to mathematicians, physicists, chemists, philosophers, and computer scientists; that registration is open now; and that student travel support is available.  Oh, and if you’re one of the people who think quantum computing is bunk?  As displayed on the poster above, leading QC skeptic Gil Kalai is a co-organizer of the conference.

### Pigs sprouted wings, Hell froze over, and I guest-posted on Luboš Motl’s blog

Monday, April 8th, 2013

Furthermore, the last of those things actually happened.  What won’t I do to promote Quantum Computing Since Democritus?  Enjoy!

Update: I submitted the following response to the comments over on Lubos’s blog.  Since it has some bits of general interest, I thought I’d crosspost it here while it awaits Lubos’s moderation.

Since Lubos “officially invited” me to respond to the comments here, let me now do so.

1. On “loopholes” in quantum mechanics: I completely agree with Lubos’s observation that the actual contents of my book are “conservative” about the truth of QM. Indeed, I predict that, when Lubos reads his free copy, he’ll agree with (or at least, have no objections to) the vast majority of what’s in the book. On the other hand, because I was guest-blogging about “the story of me and Lubos,” I found it interesting to highlight one area of disagreement regarding QM, rather than the larger areas of agreement.

2. On Gene Day’s patronizing accusation that I don’t “get the basics of QM or even comprehend the role of mathematics in physics”: his misreading of what I wrote is so off-base that I don’t know whether a response is even necessary.  Briefly, though: of course two formulations of QM are mathematically equivalent if they’re mathematically equivalent!  I wasn’t asking why we don’t use different mathematical structures (quaternions, the 3-norm, etc.) to describe the same physical world.  I was asking why the physical world itself shouldn’t have been different, in such a way that those other mathematical structures would have described it.  In other words: if you were God, and you tried to invent a theory that was like QM but based on those other structures, would the result necessarily be less “nice” than QM?  Would you have to give up various desirable properties of QM?  Yes?  Can you prove it?  The ball’s in your court, Mr. Day — or else you can just read my book!

3. On Lord Nelson’s accusation that I’m a “poseur”: on reflection, someone who only knew me from blog stunts like this one could easily be forgiven for getting that impression! So it might be worth pointing out for the record that I also have a “day job” outside the blogosphere, whose results you can see here if you care.

4. On my political views: I wish to clarify for Tom Vonk that I despise not only “Communists,” but the ideology of Communism itself. One of the formative experiences of my life occurred when I was an 8-year-old at Wingate Kirkland summer camp, and all the campers had to relinquish whatever candy they’d brought into a communal “bunk trunk.” The theory was that all the campers, rich and poor alike, would then share the candy equally during occasional “bunk parties.” What actually happened was that the counselors stole the candy. So, during a meeting of the entire camp, I got up and gave a speech denouncing the bunk trunk as Communism. The next day, the camp director (who had apparently been a fellow-traveler in the 1950s) sat with me at lunchtime, and told me about a very evil man named Joe McCarthy who I was in danger of becoming like. But the truth was that I’d never even heard of McCarthy at that point — I just wanted to eat candy.  And I’d give exactly the same speech today.

Like (I suppose) several billion of the world’s people, I believe in a dynamic market-based capitalist society, and also in strong environmental and other regulations to safeguard that society’s continued existence. And I don’t merely believe in that as a cynical compromise, since I can’t get the “dictatorship of the proletariat” that I want in my heart of hearts. Were I emperor of the world, progressive capitalism is precisely what I would institute. In return, perhaps, for paying a “candy tax” to keep the bunk functioning smoothly, campers could keep their remaining candy and eat or trade it to their heart’s delight.

5. On climate change: I’m not a professional climatologist, but neither is Lubos, and nor (correct me if I’m wrong) is anyone else commenting here. Accordingly, I refuse to get drawn into a debate about ice cores and tree rings and hockey sticks, since my experience is that such debates tend to be profoundly unilluminating when not conducted by experts. My position is an incredibly simple one: just like with the link between smoking and cancer, or the lack of a link between vaccines and autism, or any other issue where I lack the expertise to evaluate the evidence myself, I’ll go with what certainly looks like an overwhelming consensus among the scientists who’ve studied the matter carefully. Period. If the climate skeptics want to win me over, then the way for them to do so is straightforward: they should ignore me, and try instead to win over the academic climatology community, majorities of chemists and physicists, Nobel laureates, the IPCC, National Academies of Science, etc. with superior research and arguments.

To this, the skeptics might respond: but of course we can’t win over the mainstream scientific community, since they’re all in the grip of an evil left-wing conspiracy or delusion!  Now, that response is precisely where “the buck stops” for me, and further discussion becomes useless.  If I’m asked which of the following two groups is more likely to be in the grip of a delusion — (a) Senate Republicans, Freeman Dyson, and a certain excitable string-theory blogger, or (b) virtually every single expert in the relevant fields, and virtually every other chemist and physicist who I’ve ever respected or heard of — well then, it comes down to a judgment call, but I’m 100% comfortable with my judgment.

### 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 amazon.com, or here to get it from amazon.co.uk. 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! Amazon.com 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 Amazon.co.uk. 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 Amazon.com, 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. ### John Preskill: My Lodestar of Awesomeness Monday, March 18th, 2013 I got back a couple days ago from John Preskill‘s 60th birthday symposium at Caltech. To the general public, Preskill is probably best known for winning two bets against Stephen Hawking. To readers of Shtetl-Optimized, he might be known for his leadership in quantum information science, his pioneering work in quantum error-correction, his beautiful lecture notes, or even his occasional comments here (though these days he has his own group blog and Twitter feed to keep him busy). I know John as a friend, colleague, and mentor who’s done more for me than I can say. The symposium was a blast—a chance to hear phenomenal talks, enjoy the California sun, and catch up with old friends like Dave Bacon (who stepped down as Pontiff before stepping down as Pontiff was cool). The only bad part was that I inadvertently insulted John in my talk, by calling him my “lodestar of sanity.” What I meant was that, for 13 years, I’ve known plenty of physicists who can be arbitrarily off-base when they talk about computer science and vice versa, but I’ve only ever known John to be on-base about either. If you asked him a question involving, say, both Barrington’s Theorem and Majorana fermions, he’s one of the few people on earth who would know both, seem totally unfazed by your juxtaposing them, and probably have an answer that he’d carefully tailor to your level of knowledge and interest. In a polyglot field like quantum information, that alone makes him invaluable. But along with his penetrating insight comes enviable judgment and felicity of expression: unlike some of us (me), John always manages to tell the truth without offending his listeners. If I were somehow entrusted with choosing a President of the United States, he’d be one of my first choices, certainly ahead of myself. Anyway, it turned out that John didn’t like my use of the word “sane” to summarize the above: for him (understandably, in retrospect), it had connotations of being humorless and boring, two qualities I’ve never seen in him. (Also, as I pointed out later, the amount of time John has spent helping me and patiently explaining stuff to me does weigh heavily against his sanity.) So I hereby rename John my Lodestar of Awesomeness. In case anyone cares, my talk was entitled “Hidden Variables as Fruitful Dead Ends”; the PowerPoint slides are here. I spoke about a new preprint by Adam Bouland, Lynn Chua, George Lowther, and myself, on possibility and impossibility results for “ψ-epistemic theories” (a class of hidden-variable theories that was also the subject of the recent PBR Theorem, discussed previously on this blog). My talk also included material from my old paper Quantum Computing and Hidden Variables. The complete program is here. A few highlights (feel free to mention others in the comments): • Patrick Hayden spoke about a beautiful result of himself and Alex May, on “where and when a qubit can be.” After the talk, I commented that it’s lucky for the sake of Hayden and May’s induction proof that 3 happens to be the next integer after 2. If you get that joke, then I think you’ll understand their result and vice versa. • Lenny Susskind—whose bestselling The Theoretical Minimum is on my to-read list—spoke about his views on the AMPS firewall argument. As you know if you’ve been reading physics blogs, the firewall argument has been burning up (har, har) the world of quantum gravity for months, putting up for grabs aspects of black hole physics long considered settled (or not, depending on who you ask). Lenny gave a typically-masterful summary, which for the first time enabled me to understand the role played in the AMPS argument by “the Zone” (a region near the black hole but outside its event horizon, in which the Hawking radiation behaves a little differently than it does when it’s further away). I was particularly struck by Lenny’s comment that whether an observer falling into a black hole encounters a firewall might be “physics’ Axiom of Choice”: that is, we can only follow the logical consequences of theories we formulate outside black-hole event horizons, and maybe those theories simply don’t decide the firewall question one way or the other. (Then again, maybe they do.) Lenny also briefly mentioned a striking recent paper by Harlow and Hayden, which argues that the true resolution of the AMPS paradox might involve … wait for it … computational complexity, and specifically, the difficulty of solving QSZK (Quantum Statistical Zero Knowledge) problems in BQP. And what’s a main piece evidence that QSZK⊄BQP? Why, the collision lower bound, which I proved 12 years ago while a summer student at Caltech and an awestruck attendee of Preskill’s weekly group meetings. Good thing no one told me back then that black holes were involved. • Charlie Bennett talked about things that I’ve never had the courage to give a talk about, like the Doomsday Argument and the Fermi Paradox. But his disarming, avuncular manner made it all seem less crazy than it was. • Paul Ginsparg, founder of the arXiv, presented the results of a stylometric analysis of John Preskill’s and Alexei Kitaev’s research papers. The main results were as follows: (1) John and Alexei are easily distinguishable from each other, due in part to the more latter’s “Russian” use of function words (“the,” “which,” “that,” etc.). (2) Alexei, despite having lived in the US for more than a decade, is if anything becoming more “Russian” in his function word use over time. (3) Even more interestingly, John is also becoming more “Russian” in his function word use—a possible result of his long interaction with Alexei. (4) A joint paper by Kitaev and Preskill was indeed written by both of them. (Update: While detained at the airport, Paul decided to post an online video of his talk.) Speaking of which, the great Alexei Kitaev himself—the$3 million man—spoke about Berry curvature for many-body systems, but unfortunately I had to fly back early (y’know, 2-month-old baby) and missed his talk.  Maybe someone else can provide a summary.

Happy 60th birthday, John!

Two unrelated announcements.

1. Everyone who reads this blog should buy Sean Carroll’s two recent books: From Eternity to Here (about the arrow of time) and The Particle at the End of the Universe (about the Higgs boson and quantum field theory more generally).  They’re two of the best popular physics books I’ve ever read—in their honesty, humor, clarity, and total lack of pretense, they exemplify what every book in this genre should be but very few are.  If you need even more inducement, go watch Sean hit it out of the park on the Colbert Report (and then do it again).  I can’t watch those videos without seething with jealousy: given how many “OK”s and “y’know”s lard my every spoken utterance, I’ll probably never get invited to hawk a book on Colbert.  Which is a shame, because as it happens, my Quantum Computing Since Democritus book will finally be released in the US by Cambridge University Press on April 30th!  (It’s already available in the UK, but apparently needs to be shipped to the US by boat.)  And it’s loaded with new material, not contained in the online lecture notes.  And you can preorder it now.  And my hawking of Sean’s books is in no way whatsoever related to any hope that Sean might return the favor with my book.

2. Recent Turing Award winner Silvio Micali asks me to advertise the Second Cambridge Area Economics and Computation Day (CAEC’13), which will be held on Friday April 26 at MIT.  Anything for you, Silvio!  (At least for the next week or two.)

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