Ernie's 3D Pancakes

Oh, so that's what α(n) means!

Allow me to join Sariel and Suresh and Adam and all the UIUC theory stduents in extoling Raimund Seidel and Micha Sharir's easy analysis of union-find with path compression. Go. Read. And remember, induction is your friend!

In his talk, Raimund described a similar (but simpler) analysis of space-time tradeoffs for partial-sum queries in the semigroup model, simplifying an old result of Chazelle. A semigroup is a set with an associative binary `addition' function, but not necessarily inverses or subtraction. Suppose we want to preprocess an array A[1..n] of elements of some semigroup (S,+), so that we can compute any partial sum A[i]+A[i+1]+...+A[j], given the indices i and j, using as few additions as possible (and no subtractions). If we don't allow any additions, the best we can do is store all n-choose-2 partial sums. If we allow exactly one addition, we only need to store O(n log n) partial sums. In general, if we allow at most 2k+1 additions per query, we only need to store O(n log^*k n) partial sums, where log^*0 n = log n, log^*k 1 = 0 and log^*k n = 1 + log^*k(log^*(k-1) n). Finally, by storing only O(n) partial sums, we can answer a partial-sum query with only O(α(n)) additions, where α(n) is the smallest integer k such that log^*k n ≤ 2.

Raimund tells me their paper started with Micha saying "This is my favorite recurrence—it's solution is α(n)—but I don't know any way to use it!" So they tried applying it to path compression, and they succeeded. But then they simplified the argument even more, so Micha's recurrence wasn't necessary. Poor, poor recurrence. Nobody wants it.

An obscure Fat Albert / mathematical philosophy joke

Russell:

Man, you like the ontological antirealist resolution in Principia Mathematica of the self-referential paradoxes in Frege's Grundgesetze der Arithmetik!

Whitehead:

Huh?

Russell:

No class!

(Suggested by Stewart Shapiro's Thinking about Mathematics)

Terror in the Skiiiiiies!

Like Annie Jacobsen, I recently took a long Northwest Airlines flight, #53 from Amsterdam to Detroit, on which I observed several Middle Eastern passengers. Including one who sat down immediately next to me! Blocking my access to the aisle! Who then began reading a book full of Arabic! And looking nervously around the plane! Oh my god, oh my god, help me, we're all going to DIE! EEAHEEAHEEAHEEAHEEAH!

As I girded my metaphorical loins in anticipation of poisoning my seatmate to death with the remains of my so-called "chicken" "dinner", she turns to me and asks where I'm from. Turns out she was flying to Nashville, my hometown, where she is a nursing student and her husband a mechanical engineer, after a two-month visit to her family in Tehran. We had a lovely chat about living in the South, and the current troubles in Iraq. She showed me several pictures of her family at various gatherings (a birthday party, her cousin's engagement), including several fascinating pictures of the ruins at Persepolis. We landed in Detroit without indicent and wished each other well.

However, when I went to claim my luggage in Detroit en route to customs, it never appeared! Apparently my bag was stuck in Amsterdam, or perhaps Vienna!! Coincidence? I think not!!!

(Rabid conspiracy-mongers have suggested that perhaps my bag was still in the Frankfurt Flughafenbahnhof, but such theories, which cast undue aspersions on the honesty and efficiency of the German people, are striclty without credence.)

Murakami explains mathematics

On the whole, I think of myself as one of those people who take a convenience-sake view of prevailing world conditions, events, existence in general. Not that I'm such a blasé, convenience-sake sort of guy—although I do have tendencies in that direction—but because more often than not I've observed that convenient approximations bring you closest to comprehending the true nature of things.

For instance, supposing that the planet earth were not a sphere but a giant coffee table, how much sifference in everyday life would it make? Granted, this is a pretty far-fetched example; you can't rearrange the facts of life so freely. Still, picturing the planet earth, for convenience sake, as a gigantic coffee table does in fact help clear away the clutter—those practically pointless contingencies such as gravity and the international dateline and the equator, those nagging irregularities that arise from the spherical view. I mean, for a guy leading a perfectly normal existence, how many times in the course of a lifetime would the equator be a significant factor?

——Haruki Murakami (translated by Alfred Birnbaum),
Hard-Boiled Wonderland and the End of the World (1991)

Eunoia

Awkward grammar appals a craftsman. (Hear here!)

Biff! Pow! Crash! D'oh!

Mark Liberman at Language Log has been discussing the correct way to spell Homer Simpson's "D'oh!" In response, I sent him a few links. Woo-hoo!

Springer jumps on the Open Access bandwagon, sort of

Springer recently announced that authors publishing in any Springer journal (including former Kluwer journals) will have the option of making their work available for free on the Springerlink web site, in exchange for a one-time publishing charge of $3000 per paper. Springerlink will contain a mix of pay-to-read and paid-to-publish papers. Even better,subscription costs will be reduced according to the fraction of pay-to-read papers.

That is, assuming anyone has $3000 lying around whenever they want to publish sometthing. I'm just cynical enough to believe that Springer has deliberately set the open-publication price just out of reach of most authors, at least in mathematics and computer science, in an effort to derail the open-access movement. Five years from now, when only a small fraction of authors have paid their hefty fee, Springer could easily argue "See? Authors don't really want open access! It was just a tiny handful of rabble-rousers all along."

Fortunately, Springer says elsewhere on its site:

If free publication, supporting a pressure-free editorial process, and free online availability are important to you, then you need only submit your article to any Springer journal. Springer’s ‘green’ self-archiving policy lets authors post their own versions of their accepted article on an institution’s public server, and subscription-based publication ensures that authors all over the world have equal opportunity at publication and a peer review process free from commercial pressure.

So if we want the world to have free access to our Springer-published papers, all we have to do is put them on the web, with Springer's blessing. So as an author, what's my incentive to pay Springer $3000? Every one of the benefits of Springerlink are already available really for free through Google, CiteSeer, the Los Alamos Cornell ArXiv, and authors' web pages.

In the Penthouse of the Ivory Tower

Gideon Lewis-Kraus writes an absolutely beautiful piece in The Believer about his four-day road trip through the 119th Annual MLA Convention, and more generally about literary academia. Read the whole thing!

The ultimate justification for the continued existence of the humanities, the big dramatic answer to what the humanities are for, is they aren't for anything, at least not in the usual senses. Their use lies in the reminder that there is a certain grandeur in speculative withdrawal, that there are still refuges—and this sounds terribly corny, but it's true, and it's important—where reflection trumps activity. A professor who studies metaphors of hydrophilia in medieval Ukrainian folk ballads isn't just teaching her students about those ballads; she's teaching her students that it's possible to live a life devoted to something as ostensibly trifling and pointless as metaphors of hydrophilia in medieval Ukrainian folk ballads just because you love it and have found others who love it, too. She's teaching that what seems meaningless may be a source of enchantment and connection, that our obsessive fervors may yet go unmuted.

... And this is where the dark hollow of anti-academic unrest is laid bare: critics of the academy are not really afraid of explicit political indoctrination, they're afraid of these preserves of communal autonomy. They're afraid of the flowering of the arcane, the unmarketable, the unprofitable. They're afraid that their children will become scruffy bohemian types.

Google can't count.

Speaking of "peer institutions"...

University Implicated In Checks-For-Degrees Scheme