## Archive for the ‘Self-Referential’ Category

### Keeping cool

Sunday, October 26th, 2008

Update (10/27): Peter Norvig at Google points me to his Election FAQ, for those who feel they haven’t yet spent enough time reading about the election.  I’ve just been perusing it, and it’s an unbelievably good source of information—reaching the same conclusions as I did on just about every particular, yet also calm, reasoned, and professional.

1. That’s my mom at an Obama office in Sarasota, FL.  For once, I find myself kvelling to strangers about her.

2. I’m at FOCS’2008 in Philadelphia right now.  Yesterday morning I gave a tutorial on The Polynomial Method in Quantum and Classical Computing, and was delighted by how many people showed up — I wouldn’t have woken up for my talk.  (And before you ask: yes, the PowerPoint slides for this talk include photographs of both Bill Ayers and Joe the Plumber.)

3. Here’s the FOCS conference program — tons of good stuff, as you can see for yourself.  If there’s a talk you want to know more about, say so in the comments section and I’ll try to find someone who attended it.

Note: I was a program committee member, and therefore know much more than usual about the talks—but my objectivity and license as a “journalist” are also severely compromised.  If unvarnished opinion is what you seek, ask my friend and roommate Rahul Santhanam, who’s also reporting live from the conference over at Lance’s blog.  (As you can see, we CS theorists manage our conflicts of interest roughly as well as the Alaska governor’s office…)

4. I apologize that I haven’t had much to say recently.  Against my better judgment, I find myself transfixed by the same topic everyone else is transfixed by, and it’s hard to find anything to say about it that hasn’t been said better by others.  If you want to enter my world, don’t read Shtetl-Optimized; read Andrew Sullivan or FiveThirtyEight.com.  Following the election is, of course, not all that different from following a football game, except for the added dash of excitement that the future of civilization might hinge on the outcome.

(Years congruent to 0 mod 4 are pretty much the only times when I understand what it’s like to be a sports fan.  Speaking of which, I heard there was some sort of “World’s Series” in Philadelphia last night—probably in basketball—and something called the “Phillies” won?  I might be wrong, though.  Maybe it was the “Flyers” … or is that a volleyball team?  Keep in mind, I only lived in this area for the first 15 years of my life.)

5. For a congenital pessimist like me, I confess it’s been difficult to deal with the fact that my team (I mean the Democrats, not the Eagles or whatever they’re called) is winning.  I simply don’t know how to react; it’s so far outside my emotional range.  Since when has the universe worked this way?  When did reason and levelheadedness start reaping earthly rewards, or incompetence start carrying a cost?  I’m sure Nov. 4 will bring something to console me, though: maybe Al Franken will lose the Senate race in Minnesota, or the homophobe proposition will pass in California…

6. Writing blog posts in numbered lists is easier; I should do it more often.  I don’t have to pretend all the little things I want to say are part of an overarching narrative, rather than standing in the relation “and that reminds me of … which in turn reminds me of…”

7. There’s another psychological question inspired by the election that’s fascinated me lately: how does one become more obamalike in temperament?

I’ve written before about Obama’s penchant for introspection and respect for expertise, which of course are qualities with which I strongly identify.  But Obama also has a crucial quality I lack: as the whole world has marveled, nothing rattles him.  Placed for two years under the brightest glare on earth, besieged by unexpected events, he simply sticks to a script, Buddha-like in his emotional control (although not in his quest for power in the temporal world).  His nerves are of carbon nanotube fiber.

When he briefly slipped behind after the Republican convention, I panicked: I felt sure he’d lose if he didn’t completely change his approach.  Sean Carroll recommended chilling out.  I now face the indignity of admitting that I was wrong while a physicist was right.

What struck me most, during the debates, was how again and again Obama would pass up the chance to score points—choosing instead to let his opponent impale himself with his own words, and use his time to hammer home his message for the benefit of any voters just emerging from their caves.  (As an example, consider his pointed refusal in the third debate to say anything bad about Palin—the subtext being, “isn’t it obvious?”)  It’s almost as if he thought his goal was winning the election, not proving the other guy wrong.

I have (to put it mildly) not always exhibited the same prudent restraint, least of all on this blog.  So for example, whenever there’s been bait dangling in front of me in the comments section, I’ve tended to bite, often ending up with a hook through my cheek.

But no more.  As the first exercise in my newfound quest for the Zen-like equanimity and balance of our soon-to-be-president, I now present to you two excerpts from the comments on my previous post, with no reaction whatsoever from me.

Have you considered the possibility that, in the same way a logical deduction is being equated with truth, understanding a thing is just an illusion? If a thing is logical, that only means that it appeals to the reasoning facility of the brain, not that it’s the truth.

Mathematics is just a place where it becomes clear how a human may think. Computers only go for the calculable. And the mathematical truths a computer can produce are at most countable infinite. But there are uncountable infinite truths.

### Barriers to proving P!=NP and moving this blog

Sunday, September 16th, 2007

As you can imagine, TR’s response has put me in a difficult position. From their perspective, they’ve been bending over backwards to accommodate me; from my perspective (and I gather from most readers’), their offer still falls short of acceptable. When I originally agreed to let them host me, I imagined that the blog would look just as it does now, with maybe a few unobtrusive ads here or there. I didn’t even think to ask about the RSS feed or the screen width available for entries.

And so, after weeks of introspection (well, mostly being tied up with other work), I’ve reached a decision: I will continue to host my blog right here, on Bluehost, until TR comes up with something that both parties can live with. I like the TR people and appreciate their interest, but I’m not in any particular hurry to move, especially if it means crippling this blog so that no will read it. It’s true that Bluehost sucks, and that I no longer have time to be a webmaster — but once I get grant money, maybe I can pay someone to take care of these things for me.

Finally, since all this self-referentiality gets tiresome, here are the PowerPoint slides for a talk I gave at MIT last week, about recent joint work with Avi Wigderson on a new barrier to proving P≠NP. (Note: The day before the talk, PowerPoint trashed my file, and I had to recreate the entire presentation from memory. Always make backup copies! Excellent advice, in my opinion.)

Abstract:

Algebrization: A New Barrier in Complexity Theory

Any proof of P≠NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory.

In this talk we present such a barrier, which we call “algebraic relativization” or “algebrization.” The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to the low-degree extension of A over a finite field or ring.

We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. We first show that all known non-relativizing results — both inclusions such as IP=PSPACE and MIP=NEXP, and separations such as MAEXP⊄P/poly — do indeed algebrize. We next show that most open problems — including P versus NP, P versus BPP, and NEXP versus P/poly — will require non-algebrizing techniques, of which we currently have not a single example. In some cases algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP.

We also exhibit a surprising connection between algebrization and communication complexity. Using this connection, we give an MA-protocol for the Inner Product function with O(√n log(n)) communication (essentially matching a lower bound of Klauck), and describe a pure communication complexity conjecture whose truth would imply P≠NP.

Comments welcome. We’ll hopefully have a writeup soon.

### Sellin’ out to the Man

Monday, September 3rd, 2007

Alright, it’s time to tell you: in a couple of days, Shtetl-Optimized will cease its two-year independent existence, and become a part of MIT Technology Review. Please check out the new shtetl at technologyreview.com and let me know in the comments section, here or there, if anything is amiss. (Note: You have to register at technologyreview.com before you can post a comment there, but that should be pretty quick and painless.) If everything’s OK, then we’ll start redirecting the scottaaronson.com URL’s to point to the new location.

Naturally, selling out to an MIT subsidiary is not a step I took lightly. The following considerations are what finally induced me to say “yes”:

• I’d already sold my soul to MIT, so why not my blog too?
• As explained earlier, Bluehost (my current hosting provider) sucks: the sites they host routinely stop working, and when they do it’s always your fault and never theirs. Indeed, every webhosting company I’ve dealt with strikes me as basically a scam operation that does a tiny bit of hosting on the side. So when TR told me that they would be that at which the buck stops — and that if anything went wrong I could walk the two blocks to their East Cambridge office and yell at them in person — their pitch fell on receptive ears.
• From now on, TR’s expert staff will manage all technical aspects of the blog for me, leaving me free to concentrate on deeper, biting-vagina-related matters. This will be particularly welcome as the demands on my time shift from the “severe” to “ludicrous” range.
• “The Benjamins.” As explained earlier, as a matter of principle I accept bribes and kickbacks from absolutely anyone, trusting that the money from competing groups will cancel each other out, thereby leaving my overall judgment unbiased. Plus I can actually use the dough, now that I have a mortgage to pay.
• I’ll now be under contractual obligation to blog “at least twice a week on average.” I actually welcome this change, since it’s the only remedy I can think of for the blog-procrastination (i.e., work) that’s often afflicted me in the past.
• If this experiment doesn’t work, I’m allowed to back out on two weeks’ notice, retaining all the “rights” to my blog. Of course, I hope and expect that it’ll work.
• Most importantly, Jason Pontin, the editor-in-chief and publisher of Technology Review, has personally assured me that I will have complete intellectual freedom to blog about anything I want, exactly as I did when the blog was independent. You can rest assured that Jason will come to regret his guarantee in the days and weeks ahead. (TR does have a policy of fact-checking blog entries, but as I explained to them, the very concept of “fact-checking” is not particularly relevant to Shtetl-Optimized.)

Indeed, the only real disadvantage I could see to hosting the blog on TR was the amount of screen space taken up by ads. Sorry about that! Fortunately, the ads look pretty ignorable to me.

### Bluehost sucks

Wednesday, June 6th, 2007

I apologize for my website being down all morning. Back in the heyday of Bell Labs, they used to engineer telecommunications systems for “five-nines availability” (that is, 99.999% uptime). In our vastly more sophisticated Internet age, I’d gladly settle for two and a half nines.

So, can anyone recommend a webhosting service that doesn’t suck? If such a service exists, I’ll dump Bluehost and encourage others to do the same.

### New comment policy

Tuesday, April 10th, 2007

If you reject an overwhelming consensus on some issue in the hard sciences — whether it’s evolution, general relativity, climate change, or anything else — this blog is an excellent place to share your concerns with the world. Indeed, you’re even welcome to derail discussion of completely unrelated topics by posting lengthy rants against the academic orthodoxy — the longer and angrier the better! However, if you wish to do this, I respectfully ask that you obey the following procedure:

1. Publish a paper in a peer-reviewed journal setting out the reasons for your radical departure from accepted science.
2. Reference the paper in your rant.

If you attempt to skip to the “rant” part without going through this procedure, your comments may be deleted without warning. Repeat offenders will be permanently banned from the blog. Life is short. I make no apologies.

Scott Aaronson
Rebel for the Scientific Consensus

Update (4/11): I am, of course, under no illusions whatsoever that my requirement of having published a relevant peer-reviewed paper will eliminate all tinfoil-hat rants from the comments section. My hope, rather, is that it will make those rants that I do receive more interesting and original.

### 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:
$NEE^{S_{2}^{p}} \cap coC_{=}P^{{Mod_{3}P}^{EE}}$
• 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.