Category Archives: Theory

Path Compression

It’s my turn to present a paper for our Algorithms reading group this Friday, and I’m presenting Seidel’s & Sharir’s paper Top-Down Analysis of Path Compression. I don’t have a lot to say about it yet, as I’m still digesting it. This is basically what I’m doing tonight, so I don’t have much to blog about either.

Feel free to wax philosophical about recursion in the comments.


Spring Break

Spring break is here, so it will be a good time to take a look at a couple things in addition to getting some work done.

Here’s a couple things I’m looking at right now:

As for work, among many other things, I’m trying to find a good “how-to” on deriving a curvature tensor. It seems that differential geometers like to leave these things as an “exercise.”

Does the Act of Defending Theory Make One a Theoretician?

Woops. Almost forgot to make a post today.

In the interest of getting it in under the wire, I’ll just pose the question:

Does the Act of Defending Theory Make One a Theoretician?

Would one defend theory, other than to justify one’s existence as a theoretician?

The reason that I ask is that in Suresh‘s computational geometry class today, someone asked why anyone would care about manifolds. I found myself defending theory alongside Suresh, who was also preventing me from assaulting this person for asking such an insulting question.

Tattoos and Kolmogorov Complexity

My wife is still suffering pain from the new tattoo that she got a few days ago. She was a little more enthusiastic about her second and she got one on her leg about the size of a piece of Wonder bread, and it has a lot of fill (her first is about the size of a nickel, if that gives you some context). Incidentally, it is beautiful and totally fits her character.

Ever since her first tattoo, though, she has been bugging me to get a tattoo. First it was her name, then the appeals to get something “sciencey,” and finally, of course, to get something in binary (her name in binary, in fact). I can tell you right now that I will never get a tattoo in binary digits. In fact, my tendency to overengineer will probably prevent me from ever getting a tattoo at all, because I’d want it to be “perfect.” I’d die with this thing on my body, after all.

This got me thinking about the complexity of tattoos, and whether it’s desirable to design a tattoo with a complexity much higher than its Kolmogorov complexity. I could see it both ways: on one hand, it may be desirable to have an attractive pattern, especially one that’s self-similar, while on the other, it would be kind of silly to write a small sentence in binary ASCII (I’m sure there are some). I was kind of disappointed, however, when a Google image search turned up nothing for “Kolmogorov tattoo.”

Maybe I should get this tattooed on my body: “The smallest positive integer not definable in under eleven words.”