Archive for the ‘Self-Referential’ Category

Three things that I should’ve gotten around to years ago

Tuesday, October 15th, 2013

Updates (11/8): Alas, video of Eliezer’s talk will not be available after all. The nincompoops who we paid to record the talk wrote down November instead of October for the date, didn’t show up, then stalled for a month before finally admitting what had happened. So my written summary will have to suffice (and maybe Eliezer can put his slides up as well).

In other news, Shachar Lovett has asked me to announce a workshop on complexity and coding theory, which will be held at UC San Diego, January 8-10, 2014.

Update (10/21): Some readers might be interested in my defense of LessWrongism against a surprisingly-common type of ad-hominem attack (i.e., “the LW ideas must be wrong because so many of their advocates are economically-privileged but socially-awkward white male nerds, the same sorts of people who might also be drawn to Ayn Rand or other stuff I dislike”). By all means debate the ideas—I’ve been doing it for years—but please give beyond-kindergarten arguments when you do so!

Update (10/18): I just posted a long summary and review of Eliezer Yudkowsky’s talk at MIT yesterday.

Update (10/15): Leonard Schulman sent me the news that, according to an article by Victoria Woollaston in the Daily Mail, Google hopes to use its D-Wave quantum computer to “solve global warming,” “develop sophisticated artificial life,” and “find aliens.”  (No, I’m not making any of this up: just quoting stuff other people made up.)  The article also repeats the debunked canard that the D-Wave machine is “3600 times faster,” and soberly explains that D-Wave’s 512 qubits compare favorably to the mere 32 or 64 bits found in home PCs (exercise for those of you who aren’t already rolling on the floor: think about that until you are).  It contains not a shadow of a hint of skepticism anywhere, not one token sentence.  I would say that, even in an extremely crowded field, Woollaston’s piece takes the cake as the single most irresponsible article about D-Wave I’ve seen.  And I’d feel terrible for my many friends at Google, whose company comes out of this looking like a laughingstock.  But that’s assuming that this isn’t some sort of elaborate, Sokal-style prank, designed simply to prove that media outlets will publish anything whatsoever, no matter how forehead-bangingly absurd, as long as it contains the words “D-Wave,” “Google,” “NASA,” and “quantum”—and thereby, to prove the truth of what I’ve been saying on this blog since 2007.

1. I’ve added MathJax support to the comments section!  If you want to insert an inline LaTeX equation, surround it with\( \backslash(  \backslash) \), while if you want to insert a displayed equation, surround it with \(\text{\$\$ \$\$}\).  Thanks very much to Michael Dixon for prodding me to do this and telling me how.

2. I’ve also added upvoting and downvoting to the comments section!  OK, in the first significant use of comment voting, the readers have voted overwhelmingly, by 41 – 13, that they want the comment voting to disappear.  So disappear it has!

3. Most importantly, I’ve invited Eliezer Yudkowsky to MIT to give a talk!  He’s here all week, and will be speaking on “Recursion in Rational Agents: Foundations for Self-Modifying AI” this Thursday at 4PM in 32-123 in the MIT Stata Center.  Refreshments at 3:45.  See here for the abstract.  Anyone in the area who’s interested in AI, rationalism, or other such nerdy things is strongly encouraged to attend; it should be interesting.  Just don’t call Eliezer a “Singularitarian”: I’m woefully out of the loop, but I learned yesterday that they’ve dropped that term entirely, and now prefer to be known as machine intelligence researchers talk about the intelligence explosion.

(In addition, Paul Christiano—former MIT undergrad, and my collaborator on quantum money—will be speaking today at 4:30 at the Harvard Science Center, on “Probabilistic metamathematics and the definability of truth.”  His talk will be related to Eliezer’s but somewhat more technical.  See here for details.)

Update (10/15): Alistair Sinclair asked me to post the following announcement.

The Simons Institute for the Theory of Computing at UC Berkeley invites applications for Research Fellowships for academic year 2014-15.

Simons-Berkeley Research Fellowships are an opportunity for outstanding junior scientists (up to 6 years from PhD by Fall 2014) to spend one or two semesters at the Institute in connection with one or more of its programs. The programs for 2014-15 are as follows:

* Algorithmic Spectral Graph Theory (Fall 2014)
* Algorithms and Complexity in Algebraic Geometry (Fall 2014)
* Information Theory (Spring 2015)

Applicants who already hold junior faculty or postdoctoral positions are welcome to apply. In particular, applicants who hold, or expect to hold, postdoctoral appointments at other institutions are encouraged to apply to spend one semester as a Simons-Berkeley Fellow subject to the approval of the postdoctoral institution.

Further details and application instructions can be found at Information about the Institute and the above programs can be found at

Deadline for applications: 15 December, 2013.

The tightrope of truth and courtesy

Thursday, June 6th, 2013

A reader calling him- or herself “A Merry Clown” left a comment on my previous post which was so wise, I decided it had to be promoted to a post of its own.

Scientific discourse is the art of juggling decorum, truth and humor. A high-wire feat, attempted under imposing shadows cast by giants and above the distraction of merry dancing clowns.

The “appropriate” tone for scientific discourse seems to be:
(a) Cordial. Always credit others for their hard work and good intentions (allow or at least pretend that others are basically well-intentioned, except in rare situations where there is proof of egregious misconduct).
(b) Biting, merciless and hard-nosed on the substantive issues. The truth deserves no less.

Perhaps the harsher (b) is, the gentler and more thorough (a) should be. After-all, human beings are what they are.

Certainly, provided one adequately treads through the niceties in (a), there’s no reason to worry about hurting anyone’s feelings in (b). Anyone who makes scientific claims in a professional or public arena should be prepared to put on their big boy pants or their big girl pants and have their claims face the brutal gauntlet of scientific scrutiny. All attempts should be made to avoid even the appearance that any part of (b) contains personal barbs or insults (unless these barbs happen to be to be hilarious.)

Outside of science the rule is: whoever flings the horseshit the hardest wins.

Essentially, what Shtetl-Optimized readers got to see this past week was me falling off the high wire (with tenure the safety net below? :-) ).  I failed at a purely human level—though admittedly, while attempting a particularly difficult tightrope walk, and while heavily distracted by the taunts of both giants and clowns.  I’ve already apologized to Cathy McGeoch for insulting her, but I reiterate my apology now, and I extend the apology to any colleagues at MIT who might have been offended by anything I said.  I’ll strive, in future posts, to live up to a higher standard of cordiality, composure, and self-control.

At the scientific level—i.e., at level (b)—I stand by everything I wrote in the previous post and the comments therein.

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

Thanks, everyone, for your patience, and your numerous complaints about the Technology Review site! Currently, the folks at TR say they can do all the minor things people asked for, like adding permalinks to the titles and letting people include their URL’s with their comments. On the other hand, they can’t make it so you can post comments without logging in, and they can’t decrease the size of the ad bar. (I suggested that they at least turn my sidebar into drop-down menus, thereby increasing the screen width available for the entries; they said they’d look into that.) Also, they can’t provide the full text in RSS (since God forbid, that might let people read the blog without seeing ads), although they can give the first 150 words or so.

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


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 and let me know in the comments section, here or there, if anything is amiss. (Note: You have to register at 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 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:
  • 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. 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!