Interesting Stuff

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.

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

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.

Mark Shuttleworth (co-creator of Ubuntu Linux) gives an interesting look at how Ubuntu is developed, and how it fits into the world. This talk, much like Ubuntu itself, isn’t particularly technical although it makes reference to lots of other projects/programs that you might not recognize if you’re not already familiar with open source software.

For those who aren’t in the know, Ubuntu is a Linux distribution designed for ease of use with little required knowledge on the user’s behalf. It is one of the newest distributions, one of the most quickly growing ones, and one of the simplest to use (which makes sense, because it was designed that way). There is also a lot of mention of the Novell/Microsoft deal, in which Microsoft is going to start supporting some parts of the SUSE Linux distribution (which is owned by Novell these days).

I realize that this would have been more timely before the election, but I’ve come across a very good demonstration of how Diebold voting machines can be compromised without leaving any evidence behind. Seeing this stuff makes it seem much more real than reading about it.

and one more reminder to not trust Wikipedia more than you’d trust a friend of an acquaintance: the entry on Jim Sensenbrenner has had its “controversy” section removed. There is now no mention that Sensenbrenner introduced the controversial PATRIOT and Real ID Acts, nor is there a mention of his travel budget, which is paid for by special interests (against congressional rules) and is the largest of any Congressperson. edit: upon closer reading, these things are sprinkled in among the other sections in the page, but are not as easily accessible as they had been. So remember: don’t trust Wikipedia to be either correct or unbiased, any more than you’d trust anyone you’ve just met. Edit: and don’t trust the pages to keep the same format they have now.

Today’s nerdtacular tip is brought to you by the letter π and the number e: if you telnet into port 80 of a webserver, you can write your HTTP requests by hand. I haven’t quite figured out how to use this to my advantage yet, but I’m pretty sure it’s there somewhere… I can now fill in my own custom values when submitting forms, without bothering to download and edit the source for the page with the form on it, if nothing else (though I’d still need to look at the source to see what parameters the form contains).
A quick example →

I wrote an integer factorisation program (Java bytecode also available for those without a compiler) using an algorithm I just made up, and it works surprisingly well (significantly better than brute force, not nearly as good as the best-known algorithms out there today). Yes, it still has exponential running time, but I thought it was a neat idea.

A summary of the algorithm →

…is Bruce Schneier, the world-renowned security guru. From the website, a list of my favorites →