Interesting Stuff

I just flew in from Reno, and boy are my arms tired. The ironic thing is that it’s totally true. Here’s what’s happened in the past 48 hours:

The first party →

Define a “hub” to be a vertex that shares an edge with every other vertex (such as the middle of a star graph, or any vertex in a complete graph). Suppose we have the adjacency matrix of an undirected, unweighted graph with V vertices (so our input has size V^2). Find an algorithm with running time o(V^2) that can determine whether a hub exists in the graph, or prove that no such algorithm exists. Note the use of little-o notation: the algorithm must be asymptotically faster than (big) O(V^2).

My bet is that no such algorithm exists, but I can’t figure out how to prove it.

I’ll be at Mudd tomorrow, btw.

If you’re playing Zelda: Twilight Princess and get the iron boots, you should save to a different save slot. The next part is so awesome that you’ll want to play it over and over. Oh, man. This game is amazing.

There is an exploit in the Adobe PDF plugin for web browsers. Adobe has already fixed the vulnerability, so you should all update your plugins. This vulnerability affects users of Internet Explorer and Firefox, on Windows and Linux (and any other browser/OS combination that uses the Adobe plugin).

My apartment has not had internet access since Friday evening. I have called Time Warner Cable about this, and eventually managed to get an automated response saying they were aware of the problem. In the meantime, I’m writing this from the office. I have no idea how long I will be without service, nor how often this problem is going to occur (I never had any problems with Adelphia; they were bought out by TWC a couple months ago and this is the second major outage problem I’ve had). and even when I have service, it is noticeably slower than my connection with Adelphia was. I’m very dissatisfied with Time Warner Cable right now.

and you wouldn’t believe it, but they’re the best ISP in Minneapolis, hands down. Go figure.

Take a classic game that makes heavy use of a simple physics engine (such as Asteroids), and add in general relativity to the physics engine (and set the speed of light so that the game has very noticeable relativistic effects). For the Asteroids example, asteroids traveling at high speeds relative to you would exhibit Lorenz contraction, asteroids coming towards you would be bluish and those going away would be reddish, firing your gun would propel you backwards a little, etc. I’m not sure if accelerating would have different behavior than in the usual version (sure, the asteroids would age faster, but that wouldn’t be noticeable in-game). Stuff displayed on the screen would be what the spaceship pilot would perceive “now.” I suspect it would be an interesting twist on a classic game, and give people a better intuition for relativity (assuming people like it and play it a bunch). I can’t find such a game already created on the internet, but I haven’t looked too hard.

Any thoughts?

As more details come out, it looks like I was spot-on last night in my analysis of the embassy bombing in Athens. Hot damn!

It turns out one of my coworkers used to work for Evolution Robotics, which made the ER1 I used in my robotics research a year and a half ago. It’s nice to know that he agrees with me that the ER1 could have been a great product except the basic software, power converter, and marketing department were crap (though apparently if we had sprung for the $1,000 software it would have worked better). Intriguingly, he also thinks that adding a laptop and camera to a Roomba is a good way to get a cheap robot, which is what Prof. Dodds is doing now (he was my robotics research prof). Nifty!

For several weeks, I have been pondering the following: speakers and microphones are pretty much the same, in that they’re both bits of piezoelectric material held next to magnets with wires coming out of both sides. The only difference is that current is imposed on one and the other imposes itself on the current instead. Consequently, it seems like you could take your headphones and use them as really crappy microphones to record sound wherever you go with an MP3 player, assuming you made the correct changes to the firmware. Well, it turns out that not only is this possible, but people have already done it. In true hacker form, the first step is to install Linux on your iPod. I don’t think I’m actually going to do this in the foreseeable future, but it’s nice to know that someone else has tried it and it works.