Sunday, January 06, 2008

Freedom of Information

The entire academic community is based on the idea of taking previous people's work, and building on it. "Standing on the shoulders of Giants" is the goal. Unfortunately, this can only happen when the giants that have gone before give free access to their shoulders. If a piece of academic research is not made freely available, did it really achieve its goal? Did it build on human knowledge? No.

I am currently working on homeomorphic embedding. I'll write more about it in future, but the basic idea is that the relationship a \lhd b is a type of ordering (read \lhd as a left-pointing triangle with a bar under it). This ordering happens to be particularly good at ensuring termination. All is good.

Unfortunately a simple test of this relation takes exponential time, and is therefore infeasible. But good news - Jonathan Stillman determined how to reduce the running time down to O(size(a) . size(b) . arity), a perfectly reasonable time bound. The algorithm is contained in his thesis, "Computational problems in equational theorem proving", 1989. To obtain his thesis, the only way I can find is this link. To actually view the thesis, and the very important algorithm contained within, will cost a minimum of $46. Of course, its entirely possible it will rely on some side condition I can't guarantee, or not meet my needs for some other reason, but I won't know until after the money is gone.

I want to take the information, acknowledge it, and use it. Today I want to build a highly-optimising compiler for Haskell, tomorrow I might put the information to another use. After I've used the information, I will make my new discoveries and ideas available for free download on my website. Hopefully someone will be able to build on my ideas in new ways, and the cycle can continue. Hopefully one day all the information generated will be available for free on the web, then we truely can build on the work of those who have gone before.

Update: Matthew Danish (mrd on IRC) very kindly scanned and sent me the tech report "On The Complexity Of Homeomorphic Embeddings" by Stillman, which contains exactly the information I want. I am incredibly greatful to Matthew.


Anonymous said...

I've hit the portal wall more than once while researching. It's bullshit.

Robin said...

While I support free access to the sum of all human knowledge, isn't there money in your department that can be pressed into the service of paying the $46?

Neil Mitchell said...

Robin: Probably, yes. But...

1) I need to figure out how to get the money, who can authorise it, borrow the dept credit card etc - its got a high admin cost.

2) I want the information now. I can't get it now, so will have to work on other things etc.

3) The information may be useless to me. I can't tell that until I see it. $46 for a critical component of my thesis isn't bad, but $46 is expensive for an incorrect algorithm with such strong side conditions to make it worthless.

malcolm said...

I realise the cost is very annoying, but it probably just represents the age of the information you are trying to retrieve. The Thesis was produced on paper, not electronically, so there are real physical costs involved in replication and transport. For centuries, even until as recently as fifteen years ago, this was by far the common case, and everyone recognised that, whilst the information was free, the medium in which it was transcribed was not, and furthermore it took significant time to (a) discover it, and (b) get hold of a copy. Hooray for the internet, which has dramatically reduced the cost and increased the speed of access!

You can hardly blame the ACM for indexing materials that have no electronic copy. The alternative would be complete ignorance of the work altogether.