Shtetl-Optimized

Update (8/17): Believe it or not, this blog actually led to something (scroll down to comment #52 if the link doesn’t work).

Follow

I know I’ve been a derelict blogger since moving to MIT, allowing far, far too many of you to concentrate on work. But today I’m back with some quality procrastination material.

My colleague (and sometime überliberal commenter on this blog) Aram Harrow points me to a safety video for German forklift-truck drivers, which was posted to YouTube with English subtitles. As Aram says, it starts slow but is definitely worth watching to the end.

It’s funny: just this weekend, I was volunteering with the Cornell Alumni Association at the Greater Boston Food Bank. My job was to unload 40-pound boxes of canned goods from a forklift truck and place them on a conveyor belt. (And no, this is not something I’d normally do. Normally I’d offer to write a check to pay for ten people stronger than I am to unload boxes for the needy. Long story short, I was invited to do this by an individual of female persuasion.)

The whole time I was unloading boxes, I too was a bit worried about forklift safety — but, as I now know, not nearly as worried as I should have been.

Follow

From Science and NYT.

Follow

Today’s topic is one I was hoping I could avoid, since I know that my stance will alienate many of my own supporters. But after I read the comments on this post by Bill Gasarch, and reflected on all the men, women, and children who were dispossessed of their land while the world did nothing, I realized I could no longer remain silent.

Most of you will know what I’m talking about, but for those who don’t: I urge the readers of this blog to join me in severing all academic ties with the settler state of New Zealand, until that state makes complete restitution for its historic crimes against the Maori people. That means no more giving seminars at the University of Auckland. No more reading papers with “ac.nz” in the author’s email address. Indeed, no more involvement with any physics or climate research in Antarctica, the flights to which leave from Christchurch.

Some will say my proposed boycott smacks of anti-Kiwi prejudice. But in reality, some of my best friends are Kiwis. Furthermore, I hope and expect that those Kiwis who care about justice will embrace my proposal, for the chance it affords their rogue state to confront the lies and denial upon which it was founded.

Others will ask: if we’re going to boycott Kiwi scientists over the dispossession of the Maori, then why not boycott Australian scientists over the aboriginals, Chinese scientists over the Tibetans, or American scientists over the Native Americans, Iraqis, Vietnamese, or Guatemalans? I trust, however, that sensible people will recognize this question for the Kiwi diversionary tactic that it is. For what could Australia, China, or the US possibly have to do with New Zealand? Until the Kiwis acknowledge that the issue is them and only them, there is no hope for progress.

Even in a world rife with violence and despair, I can think of no single issue with a greater claim upon our conscience. And that is why I ask again: who will join me in severing all academic ties with New Zealand?

Follow

Razborov and Rudich won the Gödel Prize for “Natural Proofs”, which probably did as much as any single paper to elucidate the nature of the P vs. NP problem. (More from the Bearded One and the Pontiff.) Loosely speaking, R&R showed that any circuit lower bound satisfying certain extremely broad criteria would “bite its own tail,” and lead to efficient algorithms to distinguish random from pseudorandom functions — the very sort of thing that we wanted to prove was hard. This doesn’t by any means imply that a P≠NP proof is impossible, but it does show how the problem has a strange, self-referential character that’s not quite like anything previously encountered in mathematics, including in the work of Gödel and Turing. Technically simple but conceptually profound, the paper is also a masterpiece of clear, forceful exposition. When I first came across it as an undergrad at Cornell, I knew complexity was my subject.

Following on the heels of the New Yorker, the New York Times ran its own epic on the Large Hadron Collider. So science writers can do a decent job when they feel like it. Why can’t they write about P vs. NP the same way? Oh, right … them big machines …

Andy Drucker poses the following problem: suppose there are n blog posts, and for each post b_i, you’re told only that it was posted during the time interval [t_i,u_i]. Is there an efficient algorithm to count how many orderings of the blog posts are compatible with that information? Alternatively, is the problem #P-complete? Let me stress that Andy doesn’t know the answer to this question, and neither do I.

A certain MIT undergrad of my acquaintance sent the following letter to MIT’s DMCA enforcement office.

Dear MIT DMCA Agent,

After viewing Scoop and receiving your notice, I was more than happy to comply with NBC’s request to destroy it. Rest assured that I will no longer be downloading or sharing any post-Manhattan Woody Allen films.

Follow

1. I went on my first hot-air balloon ride (click here for photos). We landed in a Mennonite farm a half hour’s drive from Waterloo. Seven kids came out of the farmhouse to greet us, wearing caps and bonnets. These were the best-behaved kids I had ever seen in my life: they literally walked in formation, and only the oldest one spoke to us, the other six remaining silent. Having a balloon land on their farm was not at all a new experience for them.
2. I saw this xkcd cartoon, which succinctly captures a point that I’ve been trying to make for the last fifteen years, in arguments against conspiracy-mongers and other associated doofiati.
3. I read Elizabeth Kolbert’s New Yorker article about the Large Hadron Collider and the future of particle physics. I hereby nominate her for a Pulitzer; this is one of the best popular science articles I’ve ever read.
4. I saw Spider-Man 3, a profound philosophical drama that spoke to me on numerous levels. It is indeed true that with great power comes great responsibility; that we all have the capacity for good; and that, if we wish to vanquish the evil without, then we must first confront the arrogance within. My one complaint is that the Sandman was not a particularly effective villain. Let’s face it: sand just isn’t scary.
5. I got a job offer from MIT.

[Note: To clear up any confusion, I’m now lucky enough to have several great offers, and have not yet decided where I’m going, even unofficially.]

Follow

A reader points me to this recent Topology paper by Nabutovsky and Weinberger, which probably contains the biggest numbers to have ever arisen naturally in mathematics. Specifically, the authors show that, if we maximize the k^th Betti number (for k≥3) over all groups whose presentation has size N (while keeping the number finite), then it grows like the “super-duper Busy Beaver function” (that is, Busy Beaver with an oracle for the halting problem with an oracle for the halting problem).

The spiked magazine survey I blogged about earlier has finally been published. (Warning: Spouters ahead.)

Follow

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

Follow

Some of you might have read about how flight attendants at AirTran kicked a 3-year-old screaming brat and her parents off a plane, after the brat had already delayed takeoff for 15 minutes by refusing to get in her seat, and the parents had demonstrated their total unwillingness to control her. The parents went to the media expecting sympathy; instead, AirTran was immediately deluged with messages of support and people vowing to fly them from then on. Unfortunately, the airline then squandered a PR bonanza by apologizing profusely to the parents and refunding their tickets. In my opinion, there was no need to kick anyone off the plane: the child and parents should’ve been promptly moved to the luggage compartment, then whipped and beaten upon arrival.

Follow

The March 2007 issue of Notices of the American Mathematical Society is out. In it we find:

1. Fascinating conversations with three of the four Fields medalists (guess which one declined to be interviewed?)
2. An obituary of George Dantzig (linear programming pioneer), which I found incredibly frustrating for two reasons. First, the article repeatedly sidesteps the most interesting questions about Dantzig’s career: what were those open problems that he solved mistaking them for homework exercises? What impact did his WWII work actually have? Second, just as nothing in biology makes sense except in the light of evolution, so nothing in optimization makes sense except in the light of computational complexity — a topic this 19-page article somehow assiduously avoids.
3. A poem by Bill Parry (1934-2006), which stirred my soul as Walt Whitman never did back in 11^th-grade English, and which I here reproduce in its entirety.

Argument

As he cleaned the board,
chalk-dust rose like parched mist.
A dry profession, he mused as morosely
they shuffled settling tier upon tier.

Now, almost half-way through the course,
(coughs, yawns, and automatic writing)
the theorem is ready.

Moving to the crucial point,
the sly unconventional twist,
a quiver springs his voice and breast;

soon the gambit will appear
opposed to what’s expected.
The ploy will snip one strand
the entire skein sloughing to the ground.

His head turns sympathetically
from board to class.
They copy copiously.
But two, perhaps three pause and frown,

wonder will this go through,
questioning this entanglement
— yet they nod encouragement.
Then the final crux; the ropes relax and fall.

His reward: two smile, maybe three,
and one is visibly moved.
Q.E.D., the theorem is proved.

This was his sole intent.
Leaving the symbols on the board
he departs with a swagger of achievement.

Follow