Archive for the ‘Self-Referential’ Category

A hole in the web

Monday, March 26th, 2007

The sun rose this morning on a radically transformed blogosphere: sparser, emptier, populated by only one Cornell-educated prover of complexity class inclusions and oracle separations from the Northeast US.

To everyone in the CS theory community, I want you to know that I’m acutely aware of the central role that Lance’s weblog played for all of us; and the burden of somehow filling the void he left now weighs heavily on me. To that end, I’d like to offer you the following sneak preview of upcoming topics on Shtetl-Optimized.

  • Paper vs. Electronic Proceedings: The Debate Continues
  • Ordering of Authors: Who Should Go Third?
  • Greatest Hits of the 60’s and 70’s: Why Can One-Tape Turing Machines Polynomially Simulate Multitape Turing Machines?
  • Complexity Class of the Week:
  • Baseball and Complexity: They Might Not Seem Related, But They Are
  • Giving “The Man” His Due: Why We Should All Support Bush, Diebold, and Elsevier

Oh, who am I kidding? I can’t speak for the Establishment the way Lance could! Having me serve as a clearinghouse for the theory community would be putting one of the very worst-behaved inmates in charge of the asylum.

So maybe I should just stick to biting vagina jokes.

OK, I will. Without further ado, here’s an article sent to me by my good friend Sharon Haiduck, about a South African company that’s finally accomplished what a billion years of natural selection couldn’t.

Bending WordPress to my will

Saturday, February 17th, 2007

Comment previewing has been enabled.

A new tagline has been added at the top (did you notice it?).

To deal with the single most common question I get asked, I’ve added a list of introductory quantum computing links to the sidebar at the right.

The ability to translate into German, Spanish, Dutch, Italian, Japanese, Chinese and several other languages has also been added (Yiddish not yet supported). In my field tests, the words “meatspace,” “whippersnapper,” “doofosity,” and “booger” were left untranslated.

Look out for further improvements in the days ahead — including a total-immersion virtual-reality tour of my Waterloo office, and actual writing of blog entries turned over to the RoboShtetl3000.

complexityzoo.com finally redirects to the Complexity Zoo

Wednesday, December 20th, 2006

Check it out:

I think I’m finally getting the hang of this Internet thing!

Update (12/21): Purely because I love you guys so much, I spent much of today reinstating images that were lost in the move to WordPress, fixing broken links, and exterminating comment spam. As a result, the Shtetl-Optimized archives are now once again safe for human browsing. Happy procrastinating!

Shtetl-Optimized is dead. Long live Shtetl-Optimized!

Friday, November 24th, 2006

So, I finally had it both with Blogger, which was constantly down, and with my web hosting service, which was constantly down and inserting hidden Cialis ads into my homepage. (Yes, really.) So I ditched them both!

This morning Shtetl-Optimized finally departed the old country, and boarded a crowded ship bound for a strange new world: the world of Bluehost and WordPress. So welcome to a brand-new blog, which will feature the same name as the old one, the same topics, and the same terrible jokes. I hope you like it.

(Also this morning, I discovered a little hole-in-the-wall in Waterloo that sells hot, fresh bagels barely distinguishable from what you could get in New York. Yes, this is shaping up to be a very good day.)

(Oh, yes: Happy belated Thanksgiving to my American friends. I decided to stay in Waterloo over Thanksgiving to teach my course — is this is a sign that I’m actually becoming Canadian?)

Still fiddling on the roof

Friday, October 6th, 2006

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.

Intellectual funnel cake

Thursday, September 14th, 2006

It’s the Science Blog Carnival! Come see me hawking my wares, alongside Peter Woit, Dave Bacon, and dozens of other clowns.

Bananas

Sunday, August 27th, 2006

In the wake of my very public relativity humiliation, I’ve decided to sentence myself to a one-month punishment term of only blogging about things that I actually understand. That means, unfortunately, that from now until September 27 this blog is going to be quite boring and limited in scope. It also means that Lev R.’s prizewinning question, about the survival prospects of the human race, will need to be deferred until after the punishment term.

To be clear: No string theory. No global warming. No biting vaginas. No Mahmoud. Quantum complexity classes are probably kosher.

The remainder of today’s entry will be about the topic of bananas. Bananas are long, yellow fruits that grow in bunches on some sort of plant or other. They consist of two components: the peel, and the “meat.” Well, there are probably other components as well, but those two are the most readily identifiable. The meat is delicious when fresh, even more so if covered with chocolate. When not fresh, on the other hand, it tends to form brown spots. The peel is not so good to eat, but is reputed to good for tripping dumb, careless, unwary people. Like me.

Repentance

Friday, April 21st, 2006

This morning I got an email pointedly criticizing several aspects of this blog — including my handling of l’affaire Chad Okere, and my ridiculing (as opposed to answering) people who think that if P=NP, the major implication would be that airlines could schedule their flights better. The author summed up his critique as follows:

I like your blog. I only wish it would be a little bit more about complexity theory and things at least vaguely related. You have a knack for writing, and for making hard things easy. That’s something which separates you from the large majority of the (blogging) complexity theorists. I understand that you blog in order to procrastinate, and that you have no special obligation to write about anything you don’t want to write about, but I don’t believe I’m alone in thinking that such talent could nonetheless be used to better ends than writing about biting vaginas.

Godammit, I muttered. Though he overestimates my talent, the dude has a point. In my constant battle against predictability, I’ve become too self-absorbed — like Frank Gehry designing the MIT Stata Center, or a Playboy model discoursing on international politics. I’ve neglected the meat-and-potatoes that readers want and expect from me.

So, welcome to a reconceptualized shtetl. From now on I’ll be sure to ladle out the heaping helpings of complexity you crave. The danger, of course, is that as the earnestness and scientific-ness goes up, the sexual innuendoes, heavy-handed irony, ethnic jokes, and crass ridicule will decrease proportionately. Rest assured that I’ll guard against that possibility.

My day job

Monday, April 10th, 2006

You’ve probably spent days, or even months, wondering why I don’t update this blog more often. What could possibly be more important to my career — besides napping, web surfing, napping again, or watching Jon Stewart?

So it’s time to come clean: besides my gig at Shtetl-Optimized, I also have a “day job,” most of which is actually performed at night. Greg Kuperberg, who used to be my most regular commenter before he went M.I.A., has a similar “day job.” If you don’t already know what this day job is, it’s a little hard to explain. We barely understand it ourselves. One thing I can say is that it involves the production of documents like the following:

S. Aaronson and G. Kuperberg, Quantum Versus Classical Proofs and Advice, quant-ph/0604056.

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove two results about this question. First, we give a “quantum oracle separation” between QMA and QCMA. More concretely, we show that any quantum algorithm needs Ω(sqrt(2n/(m+1))) queries to find an n-qubit “marked state” |ψ>, even if given an m-bit classical description of |ψ> together with a quantum black box that recognizes |ψ>. We also prove a matching upper bound. Second, we show that, in the one previously-known case where quantum proofs seemed to help, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. Both of our results apply equally to the problem of quantum versus classical advice — that is, of whether BQP/qpoly equals BQP/poly. We end with some conjectures about quantum versus classical oracles, and about the problem of achieving a classical oracle separation between QMA and QCMA.

Alright, suppose you’re King Arthur. Merlin, your staff wizard, claims to have solved a very hard math problem (a “Holy Grail,” so to speak) on which your entire kingdom depends. The problem might involve, say, the speed of an African swallow, or the best kind of oil in which to boil heretics — the details aren’t important.

Being suspicious of wizards, you want to check Merlin’s solution, but being a king, you don’t have much time to do it. You do, however, have a quantum computer at hand (why not?). Here’s the question: is there anything Merlin could convince you of by giving you a quantum-mechanical superposition, that he couldn’t convince you of by just communicating classically?

QMA, which stands for “Quantum Merlin Arthur,” is (basically) the class of problems for which Merlin could feasibly convince you of the answer by giving you a quantum state. QCMA, which stands for “Quantum Classical Merlin Arthur,” is the class of problems for which Merlin could feasibly convince you of the answer by just communicating classically. (Some people have suggested changing the acronym to CMQA, for “Classical Merlin Quantum Arthur,” since Arthur has the quantum computer while Merlin has to communicate classically.)

The key question is whether QMA and QCMA are equal. So, do Greg and I answer that question in our paper? Of course not — are you nuts?! All we do is get closer to answering it than anyone before. We do so by giving two new pieces of evidence: one suggesting that QMA and QCMA are equal, and another suggesting that they’re not. You might not realize it, but this represents Progress.

To those who aren’t “in the business,” all of this medieval quantum intrigue might raise a question: why do we bother? Why do we spend months writing papers that (if we’re lucky) maybe a hundred people will ever be aware of, and ten will ever understand? Well, Greg can answer for himself. As for me, I’ve always liked the answer once given by Bertrand Russell. And no, this isn’t my “serious” or “official” answer (nor was it Bertie’s), but it’s a fine response to anyone who has to ask.

…a word of advice to such of my hearers as may happen to be professors. I am allowed to use plain English because everybody knows that I could use mathematical logic if I chose. Take the statement: “Some people marry their deceased wives’ sisters.” I can express this in language which only becomes intelligible after years of study, and this gives me freedom. I suggest to young professors that their first work should be written in a jargon only to be understood by the erudite few. With that behind them, they can ever after say what they have to say in a language “understanded of the people.”

An entry contained in a blog

Friday, April 7th, 2006

Time for a little pet peeve. I’ve gotten numerous emails that say something like, “In your last blog…” when what they mean is, “In your last blog entry…”

A blog is a collection of entries (or posts). The set of possible entries is only countably infinite, but the set of possible blogs has the cardinality of the continuum.

(In practice, the positivity of the cosmological constant does impose an upper bound of about 210^122 on the number of possible blogs. But that’s merely a contingent fact about our universe, and is not intrinsic to the notion of blog. Logically, there’s no reason for a blog ever to end — even though any particular entry, including this one, must.)