Shtetl-Optimized

While the reasons I haven’t updated this blog for a week are complex and multifaceted, the fact that I’ve been flying to another university every 2-3 days, waking up at 7 (AM, not PM) each morning, defending quantum computing research all day including mealtimes, and collapsing in my hotel room during rare free intervals is undoubtedly one of the contributing factors.

And so it is, alas, that I don’t have time to share anything nontrivial today. Instead, in honor of Earth Day, I’ll just link to the text of the landmark US Supreme Court ruling three weeks ago, which forced Bush’s emasculated EPA to either regulate CO₂ emissions or else give scientific reasons for refusing to do so. If you the time (and who doesn’t?), I’d also recommend reading the oral arguments, wherein you can enjoy the acidic barbs of Justice Scalia, surely one of the most interesting and articulate assholes of our time.

As with intelligent design cases, it’s not the science that’s on trial here but rather the legal system itself. Is a system set up to decide which farmer was grazing his cows on which other farmer’s land capable of weighing the origin and future of eukaryotic life on Earth? In this particular case, the legal system eked out a 5-4 victory; it could easily have gone the other way.

And yes, I know that Massachusetts v. EPA wasn’t “really” about global warming: it was about whether Massachusetts had standing to sue, the definition of the word “pollutant” in the Clear Air Act, whether the EPA can decline to regulate based on foreign-policy considerations, and so on. Similarly, Plessy v. Ferguson wasn’t “really” about racism, Griswold v. Connecticut wasn’t “really” about contraception, etc. In each case, it was just a happy coincidence, p≈1/512, that all nine justices found that the legal technicalities lined up perfectly with how they felt about the underlying issue.

For those who don’t want to read the whole decision, here are a few key passages:

When a State enters the Union, it surrenders certain sovereign prerogatives. Massachusetts cannot invade Rhode Island to force reductions in greenhouse gas emissions, it cannot negotiate an emissions treaty with China or India … These sovereign prerogatives are now lodged in the Federal Government, and Congress has ordered EPA to protect Massachusetts (among others) by prescribing standards applicable to the “emission of any air pollutant… which may reasonably be anticipated to endanger public health or welfare.”

The harms associated with climate change are serious and well recognized … That these climate-change risks are “widely shared” does not minimize Massachusetts’ interest in the outcome of this litigation … According to petitioners’ unchallenged affidavits, global sea levels rose somewhere between 10 and 20 centimeters over the 20th century as a result of global warming … These rising seas have already begun to swallow Massachusetts’ coastal land … The severity of that injury will only increase over the course of the next century: If sea levels continue to rise as predicted, one Massachusetts official believes that a significant fraction of coastal property will be “either permanently lost through inundation or temporarily lost through periodic storm surge and flooding events.”

EPA does not dispute the existence of a causal connection between man-made greenhouse gas emissions and global warming. At a minimum, therefore, EPA’s refusal to regulate such emissions “contributes” to Massachusetts’ injuries. EPA nevertheless maintains that its decision not to regulate greenhouse gas emissions from new motor vehicles contributes so insignificantly to petitioners’ injuries that the agency cannot be haled into federal court to answer for them … But EPA overstates its case. Its argument rests on the erroneous assumption that a small incremental step, because it is incremental, can never be attacked in a federal judicial forum. Yet accepting that premise would doom most challenges to regulatory action.

Unlike EPA, we have no difficulty reconciling Congress’ various efforts to promote interagency collaboration and research to better understand climate change with the agency’s pre-existing mandate to regulate “any air pollutant” that may endanger the public welfare … Collaboration and research do not conflict with any thoughtful regulatory effort; they complement it.

EPA no doubt has significant latitude as to the manner, timing, content, and coordination of its regulations with those of other agencies. But once EPA has responded to a petition for rulemaking, its reasons for action or inaction must conform to the authorizing statute. Under the clear terms of the Clean Air Act, EPA can avoid taking further action only if it determines that greenhouse gases do not contribute to climate change or if it provides some reasonable explanation as to why it cannot or will not exercise its discretion to determine whether they do … To the extent that this constrains agency discretion to pursue other priorities of the Administrator or the President, this is the congressional design.

EPA has refused to comply with this clear statutory command. Instead, it has offered a laundry list of reasons not to regulate. For example, EPA said that a number of voluntary executive branch programs already provide an effective response to the threat of global warming … that regulating greenhouse gases might impair the President’s ability to negotiate with “key developing nations” to reduce emissions … and that curtailing motor-vehicle emissions would reflect “an inefficient, piecemeal approach to address the climate change issue” …

Although we have neither the expertise nor the authority to evaluate these policy judgments, it is evident they have nothing to do with whether greenhouse gas emissions contribute to climate change. Still less do they amount to a reasoned justification for declining to form a scientific judgment. In particular, while the President has broad authority in foreign affairs, that authority does not extend to the refusal to execute domestic laws.

Nor can EPA avoid its statutory obligation by noting the uncertainty surrounding various features of climate change and concluding that it would therefore be better not to regulate at this time. … If the scientific uncertainty is so profound that it precludes EPA from making a reasoned judgment as to whether greenhouse gases contribute to global warming, EPA must say so.

In short, EPA has offered no reasoned explanation for its refusal to decide whether greenhouse gases cause or contribute to climate change. Its action was therefore “arbitrary, capricious, … or otherwise not in accordance with law.”

“The debate is over. I mean, how many more thousands and thousands of scientists do we need to say, ‘We have done a study that there is global warming?’ … I am here to make businesses boom, but let’s also protect our environment. Let’s make our air clean. Let’s make our water clean. And let’s fight global warming because we know now that this is a major danger, that this is not a debate anymore.”

Addendum: Unfortunately Friedman’s NYT column on the Right’s scientific muscleman is only available to subscribers, so I’ve quoted the relevant passages in the comments section.

Hearty, nontrivial Christmas greetings from SAT-a-Clause, the patron saint of theoretical computer scientists! Tomorrow night, SAT-a-Clause will once again descend all possible chimneys in parallel, nondeterministically guess which ones lead to cookies, and fill the corresponding “STOC-ings” with loads of publishable results!

As I’ve done every year since I was about 14, I’ll spend Christmas Eve at my best friend Alex’s house (this year bringing the girlfriend along). My role at Alex’s family gathering, of course, is to wage the secular-humanist War On Christmas: sanctimoniously insisting that guests say “Happy Holidays” instead of “Merry Christmas,” belching loudly during hymns and carols, mocking the Savior as a “competent if unoriginal 1^st-century rabbi,” and just generally dampening Christian faith, fomenting impiety, and advancing the cause of Satan. After all, what Christmas Eve celebration would be complete without a JudeoGrinch?

If your idea of the Christmas spirit includes, you know, peace on Earth, goodwill to all mankind, etc., you should check out this New York Times essay by Peter Singer, which Luca blogged about previously. Singer strikes me as one of the few public intellectuals who’s actually gotten wiser with age, as opposed to yet more cranky and intransigent. In this latest piece, he shows himself to be less concerned with chicken liberation than with eradicating rotavirus and malaria, less interested in the Talmudic question of whether a billionaire who’s given away 90% of his wealth is now morally obligated to give away the rest than in the practical question of how to get people to give more. I also recommend this column from last Christmas season by Nicholas Kristof — a writer who’s occassionally mistaken, never less than a mensch — in which he compares the War on Christmas to the war in Darfur, and challenges Bill O’Reilly to join him in witnessing the latter.

Let this man’s face serve as a reminder to all my American friends, to haul your respective asses to your respective polling places with no excuses accepted. Keep in mind that this year the Democratic voting day is Tuesday November 7^th, while the Republican voting day is Wednesday November 8^th.

(Me? I couldn’t find a precinct station in Waterloo for some strange reason, so I mailed an absentee ballot back to New Hope, PA.)

O Achilles of Arkansas, O bane of Foxes and Roves, O solitary warrior among Democrats: dasher of hopes, prince of platitudes, felatee of Jewesses, belated friend of Tutsis, toothless tiger of climate change, greatest of all living Americans: how shall we summon thee back?

My friend Alex Halderman is now after bigger fish than copy-“protected” music CD’s. Watch this video, in which he, Ed Felten, and Ariel Feldman demonstrate how to rig a Diebold voting machine (and also watch Alex show off his lock-picking skills). Reading the group’s paper, one becomes painfully aware of a yawning cultural divide between nerds and the rest of the world. Within the nerd universe, that voting machines need to have a verifiable paper trail, that they need to be open to inspection by researchers, etc., are points so obvious as to be scarcely worth stating. If a company (Diebold) refuses to take these most trivial of precautions, then even without a demonstration of the sort Alex et al. provide, the presumption must be that their machines are insecure. Now Alex et al. are trying to take what’s obvious to nerds into a universe — local election boards, the courts, etc. — that operates by entirely different rules. Within this other universe, the burden is not on Diebold to prove its voting machines are secure; it’s on Alex et al. to prove they’re insecure. And even if they do prove they’re insecure — well, if it weren’t for those pesky researchers telling the bad guys how to cheat, what would we have to worry about?

So, how does one bridge this divide? How does one explain the obvious to those who, were they capable of understanding it, would presumably have understood it already? I wish I had an easy answer, but I fear there’s nothing to do but what Alex, Ed, and Ariel are doing already — namely, fight with everything you’ve got.

I woke up at my normal time — probably around 2PM — in my room at Berkeley’s International House, to find an avalanche of email: from a fellow grad student, urging everyone to check the news; from Christos Papadimitriou, reminding us that we have a community here, and communities can comfort; from Luca Trevisan, announcing that the class that he taught and I TA’ed would be canceled, since on a day like this it was impossible to think about algorithms. I then clicked over to news sites to find out what had happened.

After confirming that my friends and family were safe, I walked over to my office in Soda Hall, mostly to find people to talk to. Technically I had office hours for the algorithms class that afternoon, but I didn’t expect students actually to come. Yet come they did: begging for hints on the problem set, asking what would and wouldn’t be on the test, pointing to passages in the CLRS textbook that they didn’t understand. I pored over their textbook, shaking my head in disbelief, glancing up every minute or so at the picture of the burning buildings on the computer screen.

That night there was a big memorial service in Sproul Plaza. When I arrived, a woman offered me a candle, which I took, and a man standing next to her offered me a flyer, which I also took. The flyer, which turned out to be from a socialist organization, sought to place the events of that morning in “context,” describing the World Trade Center victims as “mostly white-collar executives and those who tried to save them.”

After a few songs and eulogies, a woman got up to explain that, on this terrible day, what was really important was that we try to understand the root causes of violence — namely poverty and despair — and not use this tragedy as a pretext to start another war. The crowd thunderously applauded.

While the speeches continued, I got up and wandered off by myself in the direction of Bancroft Way. Much as I did the year before, when the area around Telegraph was festooned with Nader for President posters, I felt palpably that I wasn’t living in an outcomes-based region of reality. The People’s Republic of Berkeley was proving to be a staunch ally of the Oilmen’s Oligarchy of Crawford, undermining the only sorts of opposition to it that had any possibility of succeeding.

I decided to forget about politics for a while and concentrate exclusively on research. I can’t say I succeeded at this. But I did pass my prelim exam three days later (on September 14), and a few weeks afterward proved the quantum lower bound for the collision problem.

Note: Feel free to post your own retrospective in the comments section. Andris Ambainis has already done so.

A reader from Istanbul wrote in, asking me to comment on the war in Israel and Lebanon. In other words, he wants me to make this blog the scene of yet another intellectual bloodbath, with insult-laden rockets launched from untraceable IP addresses and complexity-theoretic civilians trapped in the crossfire. What a neat idea! Why didn’t I think of it before?

Alright, let me start with some context. No, I’m not talking about the Gaza pullout, or Camp David, or the last Lebanon invasion, or the Yom Kippur War, or the Six-Day War, or the War of Independence, or the UN partition plan, or the 1939 White Paper. I’m talking about the first appearance of Israel in the extrabiblical historical record, which seems to have been around 1200 BC. Boasting in a victory stele about his recent military conquests in Canaan, the Egyptian pharaoh Merneptah included a single sentence about Israel:

Israel is laid waste; his seed is destroyed.

Sure, the pharoah was a bit premature. But give him credit for prescience if not for accuracy. Unlike (say) pyramid-building or Ra-worship, Merneptah’s Jew-killing idea has remained consistently popular for 3.2 millennia.

Today, in the year 2006, as the LHC prepares to find the Higgs boson and the New Horizons probe heads to Pluto, Am Yisra’el (literally, “the people that argues with God”) is once again surrounded by enemies whose stated goal is to wipe it off the face of the Earth. And, in the familiar process of fighting for its existence, that people is grievously, inexplicably, incompetently, blowing up six-year-olds and farmers while failing to make any visible progress on its military objectives.

So what is there to say about this that hasn’t already been said Ackermann(50) times? Instead of cluttering the blogosphere any further, I’ll simply point you to a beautiful New York Times op-ed by Rebecca Goldstein, commemorating the 350^th anniversary of Spinoza’s excommunication from the Jewish community of Amsterdam. Actually, I’ll quote a few passages:

Spinoza’s reaction to the religious intolerance he saw around him was to try to think his way out of all sectarian thinking. He understood the powerful tendency in each of us toward developing a view of the truth that favors the circumstances into which we happened to have been born. Self-aggrandizement can be the invisible scaffolding of religion, politics or ideology.

Against this tendency we have no defense but the relentless application of reason.

Spinoza’s system is a long deductive argument for a conclusion as radical in our day as it was in his, namely that to the extent that we are rational, we each partake in exactly the same identity.

Spinoza’s dream of making us susceptible to the voice of reason might seem hopelessly quixotic at this moment, with religion-infested politics on the march. But imagine how much more impossible a dream it would have seemed on that day 350 years ago.

Since I hadn’t heard from my friend Mahmoud Ahmadinejad for a while, I figured he must be busy with his new uranium-enrichment hobby. My suspicions weren’t alleviated by this excellent piece in the New York Review of Books. What I hadn’t realized is that Mahmoud is quite the joker! And no, I’m not talking about the obvious gag of funding a peaceful nuclear energy program by oil exports — I’m talking about the following Pythonesque routine, which I’m not making up:

IAEA: Iran, if your nuclear program is for peaceful purposes only, then why did we find traces of 36%-enriched uranium at the Natanz facility, whereas you’d only need 3% enrichment for a reactor?

Iran: Oh, that’s just because the equipment we bought from A. Q. Khan on the black market was contaminated.