viernes, 24 de octubre de 2008

Routing on flat labels

Caesar, M., Condie, T., Kannan, J., Lakshminarayanan, K., and Stoica, I. 2006. ROFL: routing on flat lables. SIGCOMM Comput. Commun. Rev. 36, 4 (Aug. 2006), 363-374.
I'm sure the reviewers found their work rather amusing. :-P

domingo, 12 de octubre de 2008

Madness and Genius

One of my favorite comics is Abstruse Goose, which often shows a mix of science, math and humor. Great stuff! But I was rather surprised by the latest comic, The Cantor Madness, which somehow plays with the idea that some things “aren't meant to be comprehended by finite minds”. The comic also included links to a BBC documentary Dangerous Knowledge by independent filmmaker David Malone.

The film is quite interesting, it describes some of the amazing work of Georg Cantor (on infinity in mathematics), Ludwig Boltzmann (on statistical thermodynamics), Kurt Gödel (on the incompleteness theorem in logic) and Alan Turing (on computability and the halting problem). I learned many interesting things, I was familiar with the work of Cantor but not so much with his life. I also didn't knew too much about the work of Boltzmann.

On the downside, all of the movie somehow speculates that the power of the ideas that these persons were developing in their minds also caused them, well, to go insane. In particular, as well as the comic shows, it is lightly suggested that trying to prove the continuum hypothesis will literally drive you crazy. And we have seen this before. Other movies, such as A Beautiful Mind and very explicitly Pi, play with the similar concept of ideas so powerful that can effectively break your mind.

Coming back specifically to BBC's documentary, it is true that all of these scientists often had problems with depressions, in particular both Boltzmann and Turing ended their lives by suicide. But the hints of the movie trying to connect their work and ideas with their mental problems are very misleading.

Coincidentally, I've just finished reading a biography of Gödel, so I can shed some light on that. Gödel actually had problems with depression and hypochondriasis throughout all of his life. Not related at all with him trying to prove the continuum hypothesis, his mental illness gradually developed by many factors such as stress, a lot of pressure from responsibilities at work, and the death of close friends (Einstein being one of them).

The other interesting case is Alan Turing. He didn't really suffered from any strong depression or mental illness. He was an homosexual at a time where, in the U.K., homosexuality was regarded as illegal and a criminal offense. As an alternative to jail, Turing was given the option to undergo hormonal treatment with estrogen hormone injections to reduce his libido. His dead had certainly more to do with this prosecution than with the genius and reach of his ideas.

Also disappointing is the fact that the movie never mentions that the continuum hypothesis has been resolved. And the solution is no less exciting than the incompleteness theorem and the halting problem themselves. For those who haven't heard about it before, here is a very quick description of the problem. It turns out, as Cantor showed, that there are infinities of different sizes. In particular, he showed that there are more real numbers than there are natural numbers. The question is then: is there an infinite set whose size is larger that that of natural numbers but smaller than that of real numbers?

Well, as Paul Cohen proved by concluding the work of Gödel, the answer is: whatever you like. More formally he showed that the answer is independent from the axioms of set theory (as given by Zermelo–Fraenkel). So you can assume that there are no infinite sets between natural and real numbers, be happy with that, and prove theorems; in very much the same way in which you can assume that there are infinite sets between natural and real numbers, be happy with that, and prove theorems. Isn't that exciting or what?

Anyway, the movie obviously left me with some intrigue. It is true that some of the greatest minds of mankind have suffered from very strong mental illnesses. Is it maybe true that there is somehow a link between the two? I thought that, obviously, someone should have already done a study in that respect and, as I found out, of course many studies have been done. I was initially surprised with the results (after some thought it actually makes sense) since the fact is that yes, there is a correlation, but the correlation is negative.

According to several studies cited in the Intelligence quotient article on Wikipedia, persons with higher IQ tend to suffer less from severe depression, schizophrenia and Post-Traumatic Stress Disorder. Also a higher IQ is correlated with living longer and more healthy. Children with higher IQ also were less likely to suffer injuries that require hospitalization in their adult life. One possible explanation being that they better avoid injury and take better care of their own health.

sábado, 11 de octubre de 2008

Linking words

Often, when I looked up synonyms in a thesaurus, I was surprised on how relatively easy it was to, starting from some random word, follow a chain of ‘synonyms’ which eventually led to another word, whose meaning was completely different from the original one.

I obviously started thinking, are maybe all words connected in a large graph of synonyms? Or are words clustered into several groups with more or less similar meanings? And, if so, how many of such groups are there? A few tens? some hundreds? If you want to try to guess, this is your last chance.

Being the maniac I am, and having some basic knowledge of graph theory, I got my hands on the digital version of a thesaurus, and hacked in some quick scripts to find the answers. These are the results.

I used The Oxford American Writer's Thesaurus, it is also the one used by the Dictionary application available on Mac's. The version of the thesaurus I used has 31'673 ‘senses’ (i.e. entries relating a word with many other of the same meaning), and a total of 52'307 different words and small phrases.

Apart from a small set of very disconnected 193 senses (more details later), the rest of the 31'480 word senses are all linked together in the same group of connected words. This means that, pretty much from every word in the thesaurus you can get to every other word just by following chains of synonyms.

Even words with opposite meanings such as ‘good’ and ‘bad’ are connected, and not very far apart. Just by looking into the entries of two senses one finds that ‘good’ is listed as synonym of ‘mean’ (in the sense of accomplished), while ‘mean’ is listed as synonym of ‘bad’ (in the sense of base). If you are skeptic, here are the two relevant entries taken directly from the thesaurus:

accomplished: an accomplished bassoonist expert, skilled, skillful, masterly, successful, virtuoso, master, consummate, complete, proficient, talented, gifted, adept, adroit, deft, dexterous, able, good, competent, capable, efficient, experienced, seasoned, trained, practiced, professional, polished, ready, apt; informal great, mean, nifty, crack, ace, wizard; informal crackerjack.

base2: base motives sordid, ignoble, low, low-minded, mean, immoral, improper, unseemly, unscrupulous, unprincipled, dishonest, dishonorable, shameful, bad, wrong, evil, wicked, iniquitous, sinful. antonym noble.

Some more interesting trivia facts: In this large connected group, every word is connected to every other word by following, in average, 3.81 senses. So paths between different words tend to be very short. The center of the thesaurus is the word


from which you can get to any other connected word in an average of 2.66 senses.

The most distant pair of words is only 9 senses apart. These are the short phrases ‘swimming trunks’ and ‘in any other way’ which are connected by the following chain of senses:

bathing suit: swimming trunks - bathing suit
swimsuit: bathing suit - trunks
luggage: trunks - luggage
possession: luggage - assets
saving: assets - saving
but: saving - but
but: but - on the other hand
alternatively: on the other hand - otherwise
otherwise: otherwise - in any other way

The ‘boring’ words, which are disconnected from everything else, are usually words which only list a few synonyms and/or some usage notes in the thesaurus. The biggest group of such words has only 5 related senses. For those with curiosity, this is the full list of disconnected senses.

Also for those interested, the kind of programming techniques that I used to compute this information are very similar to those used by Stephen Dolan on his Six Degrees of Wikipedia. Although, being my graph considerably smaller, the results were obtained just by leaving a single computer running overnight.