Shtetl-Optimized

From my inbox:

We simple folk out in the cold wastes of the internet are dying the slow and horrible death of intellectual starvation. Only you can save us, by posting the next installment of your lecture notes before we shuffle off this mortal coil. Will you help us, or will you say “Let them read slashdot”? Ok, seriously, I know you’re busy. Just wanted to make sure you knew people are enjoying the lecture notes.

And from my comments section:

You know you’ve made it, and then lost it, when you no longer publish notes on your course 🙂

Alright, alright, alright, alright, alright. Now that I’ve returned from my two-week world concert tour (which took me to Innsbruck, London, Yale, and U. of Toronto), and now that my girlfriend and I have settled into a lovely new apartment (complete with silverware, shower curtains, and a giant poster of complexity class inclusions above the fireplace), I finally have some time to resume your regularly-scheduled programming.

So won’t you join me, as I attempt to excavate the strange forgotten world of paleocomplexity, and relive an age when STOC and FOCS were held in caves and Diagonalosaurs ruled the earth?

Follow

… Lance Fortnow and Bill Gasarch perform a Talmudic exegesis of one of your blog posts, taking more time to do so than you took to write the post. Listen to Bill and Lance dissect my Ten Reasons to Believe P!=NP, and then offer their own reasons that are every bit as flaky as mine are. (Indeed, Lance’s reason turns out to be almost identical to my reason #9, which he had previously rejected.)

I’m honored, of course, but I’m also offended by Bill and Lance’s speculation that not all of my Reasons to Believe were meant completely seriously. Needless to say, everything I write on this blog carries the Official Scott Aaronson Seal of Really Meaning It. Including the last sentence. And the last one. And the last one. And the last one.

Follow

Of course, the greatest scientific flame war of all time was the calculus priority dispute between Isaac Newton and Gottfried Wilhelm Leibniz. This one had everything: intrigue, pettiness, hypocrisy, nationalism, and even hints of the physicist vs. computer scientist split that continues to this day.

In our opening talk at QIPC’2006 in London, Dave Bacon and I decided to relive the hatred — with Dave in a frilly white wig playing the part of Newton, and your humble blogger in a frilly black wig playing the part of Leibniz. We forgot to take photos, but here’s the script, and here are the slides for the … err, “serious” talk that Dave and I gave after dewigging.

Update (thanks to Dave and Viv Kendon):

Follow

The New York Times on Yau. Thanks to Hoeteck Wee.

Follow

So, it seems I’ve been written up in the Kitchener-Waterloo Record, a newspaper whose prestige and journalistic excellence make the Wall Street Journal look like the Shop-Rite coupon book. The article, by Meghan Waters, is about “nerd culture” in Waterloo, and I am the prototypical nerd who Waters found to interview.

A few corrections:

• While I said some very nice things about Mike Lazaridis, I did not compare him to God. (Sorry, Mike!)
• I did not use the phrase “create some nerd capital.” Indeed, if you find a phrase that sounds like I wouldn’t have used it, I probably didn’t use it.
• I did not confidently declare that in the future, “nerdlings will dream about” the University of Waterloo as they now do MIT and Caltech (“just give it some time”). I speculated that something like this might happen, particularly if the US were to continue its descent into medieval theocracy.

Despite these and other minor errors, I’m glad that my plan to increase the number of women in science by “nerdifying the world” has now received the wide public airing it deserves.

Follow

Whether there exist subexponential-size locally decodable codes, and sub-n^ε-communication private information retrieval (PIR) protocols, have been major open problems for a decade. A new preprint by Sergey Yekhanin reveals that both of these questions hinge on — wait for this — whether or not there are infinitely many Mersenne primes. By using the fact (discovered a month ago) that 2^32,582,657-1 is prime, Yekhanin can already give a 3-server PIR protocol with communication complexity O(n^1/32,582,658), improving the previous bound of O(n^1/5.25). Duuuuuude. If you’ve ever wondered what it is that motivates complexity theorists, roll this one up and smoke it.

Follow

I arrived yesterday in Innsbruck, Austria — a lovely medieval town set in a valley in the Tyrolean Alps. Here the Pontiff and I are sharing an office at the Institut für Quantenoptik und Quanteninformation, and will have to work out a comedy routine to be performed Friday morning, when we’re supposed to open the QIPC meeting at Ike Newton’s old stomping grounds, the Royal Society in London.

Since I’m too jetlagged to write a coherent entry, I hope you’ll be satisfied with some lists:

The three secrets of air travel (distilled from a decade of experience flying to four continents, and offered free of charge to you, my readers):

1. Bring a book. Don’t even try to work on the plane; just read read read read read. If you get stuck in the airport for hours, all the more time to read!
2. If you must work, do it with pen and paper, not a laptop.
3. Put your laptop case in the overhead bin, not under your seat. This will give you more room to stretch your legs.

The only three German words you’ll ever need to know:

1. Danke (thank you). To be said after any interaction with anyone.
2. Ein (one). As in: I will have one of those (pointing).
3. Entscheidungsproblem (decision problem). The problem of deciding whether a first-order sentence is true in every interpretation, proven to be undecidable by Church and Turing.

The two things I saw yesterday that I wish I’d taken a photo of but didn’t:

1. A jewelry store display case, proudly displaying “SCHMUCK” brand designer watches. (Important Correction: Ignorant schmuck that I am, I hadn’t realized that “schmuck” is not a brand name, but just the German word for jewelry. Apparently the meaning in Yiddish migrated from “jewels” to “family jewels” to “person being compared to the family jewels,” which is a bit ironic. “Oh my turtledove, the apple of my eye, my priceless schmuck…”)
2. A campaign poster for one of Austria’s far-right politicians, which graffiti artists had decorated with a Hitler mustache, a forehead swastika, and salutations of “Heil!” (Just what point were the graffiti artists trying to make? I wish I understood.)

Follow

This week Shtetl-Optimized celebrates its one-year anniversary!

That being the case, in the remainder of this post I thought it would be a good idea to take stock of everything this blog has achieved over the past year, and also to set concrete goals for the coming year.

Follow

Behold the PCP Theorem, one of the crowning achievements of complexity theory:

Given a 3SAT formula φ, it’s NP-hard to decide whether (1) φ is satisfiable or (2) at most a 1-ε fraction of the clauses are satisfiable, promised that one of these is the case. Here ε is a constant independent of n.

In recent weeks, I’ve become increasingly convinced that a Quantum PCP Theorem like the following will one day be a crowning achievement of quantum complexity theory:

Given a set of local measurements on an n-qubit register, it’s QMA-hard to decide whether (1) there exists a state such that all of the measurements accept with probability 1, or (2) for every state, at most a 1-ε fraction of the measurements accept with probability more than 1-δ, promised that one of these is the case. Here a “local” measurement is one that acts on at most (say) 3 qubits, and ε and δ are constants independent of n.

I’m 99% sure that this theorem (alright, conjecture) or something close to it is true. I’m 95% sure that the proof will require a difficult adaptation of classical PCP machinery (whether Iritean or pre-Iritean), in much the same way that the Quantum Fault-Tolerance Theorem required a difficult adaptation of classical fault-tolerance machinery. I’m 85% sure that the proof is achievable in a year or so, should enough people make it a priority. I’m 75% sure that the proof, once achieved, will open up heretofore undreamt-of vistas of understanding and insight. I’m 0.01% sure that I can prove it. And that is why I hereby bequeath the actual proving part to you, my readers.

Notes:

1. By analogy to the classical case, one expects that a full-blown Quantum PCP Theorem would be preceded by weaker results (“quantum assignment testers”, quantum PCP’s with weaker parameters, etc). So these are obviously the place to start.
2. Why hasn’t anyone tackled this question yet? Well, one reason is that it’s hard. But a second reason is that people keep getting hung up on exactly how to formulate the question. To forestall further nitpicking, I hereby declare it obvious that a “Quantum PCP Theorem” means nothing more or less than a robust version of Kitaev’s QMA-completeness theorem, in exactly the same sense that the classical PCP Theorem was a robust version of the Cook-Levin Theorem. Any formulation that captures this spirit is fine; mine was only one possibility.

Follow

Bigger, longer, wackier. The topic: “Minds and Machines.”

Follow