Slashdot Mirror
Great Computer Science Papers?
slevin writes "Recently I listened to a talk by Alan Kay who mentioned that many 'new' software ideas had already been discovered decades earlier by computer scientists - but 'nobody reads these great papers anymore.' Over the years I have had the opportunity to read some really great and thought-provoking academic papers in Computer Science and would like to read more, but there are just too many to sort through. I'm wondering what great or seminal papers others have encountered. Since Google has no answers, perhaps we can come up with a list for the rest of the world?"
For "great and seminal" it's hard to beat Alan Turing's 1950 (!) paper on AI.
~ Whence do you come, slayer of men, or where are you going, conqueror of space?
Often, when you're new to a given domain, there exists a book (on citeseer too...) that covers the domain and express, often better than the original authors, the main ideas.a nnonday/pape r.html
Then, you can use citeseer to see what's new and what's the fashion in the domain.
Anyway, one of the best papers (and oldest) I read give birth to a whole community:
http://cm.bell-labs.com/cm/ms/what/sh
"The UNIX Time-Sharing System," by Dennis Ritchie & Ken Thompson, is one of the best-written papers ever. The elegance of thought and economy of description set a standard we should all aspire to.t ml
t ml
http://cm.bell-labs.com/cm/cs/who/dmr/cacm.h
I list several more classics on my "Software Engineering Reading List" page at
http://www.multicians.org/thvv/swe-readings.h
What about the work of Edsger Dijkstra? His seminal work on 'The GOTO statement considered harmful', the Shortest Path Algorithm, and the dining philosophers.
The truth is rarely pure and never simple. Oscar Wilde (1854 - 1900)
If nobody reads those "great old papers" any more, there's probably a reason. Sometimes the ideas have been superceeded; sometimes they weren't any good to begin with; often the papers are simply really hard to understand. The fact that people seriously suggest reading "great papers" reflects on the immaturity of the field; in a field like mathematics, hardly anyone ever reads the original papers (even for work done in the 20th century), instead opting to read someone else's simplification/clarification of the ideas.
We speak of the TAoCP as "the bible", but I'm not sure if there are any "new" ideas there; rather, the value of TAoCP is as a compilation and exposition of all the best ideas other people have produced.
Learn about great algorithms; don't worry about reading great papers.
Tarsnap: Online backups for the truly paranoid
I've taught computer science. Specifically Software Engineering where there is about a 1" thick stack of around 15 papers that get the whole idea. Wonderful works like "Goto Considered Harmful" (Communications of the ACM, 11, p147-148, 1968) come to mind. But I don't think there's much hope the typical /.er will take the time and effort to read them better yet think about them.
In the last couple of weeks /. as a culture came up as a lunch conversation between my co-workers and I. We came to the conclusion that the wild herd doesn't pay for stuff (Kazaa, Morphious, etc), is ADD (how many times have you read a posting where the poster hadn't read the link?) and generally thinks that education is mostly worthless (the bi-annual do I need a degree grudge match). Given these behaviors, why go through the effort of making a list?
If I were working this space (putting my teaching hat back on) I'd cover:
Computer Architecture (where all things come from)
Theory of Computing including O() [& friends], analysis of algs, Turing, etc.
Software Engineering
Software Testing
Graphics
Databases
Numerical Methods
Simulation (& Statistics)
and
Systems Analysis (where apparently all books currently suck)
I think that would be the place to start and there would be more than 10 or 20 of them.
-- Multics
McCarthy's paper on Lisp: Recursive Functions of Symbolic Expressions and Their Computation by Machine (Part I).
For a refreshing analysis of the paper by Lisp guru Paul Graham (the same guy who proposed the idea of Bayesian anti-spam filtering), see The Roots of Lisp.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
ACM and IEEE are just the places I would look for such papers. The proceedings of ACM SIGCOMM for example are a very good "filter" for the flood of papers on networking.
You betcha. There has been a lot of research over the past 50 years, and much of it ignored - especially research that isn't in English.
A lot of old research is interesting in terms of Patent law. A lot of this research can be used to invalidate patent cliaims - prior art. An idea published 30 years ago simply cannot be legitimately patented now.
Very recently my Dad told me about a new patent assigned to one of his competitors. But my Dad claimed that his colleauge didn't patent that very idea in the 1970s because my dad knew of prior art - my dad had heard a researcher from Germany talk about the same thing at a small conference.
Given prior art, my Dad and his colleauge didn't apply for patent back then. But 35 years later, a company patented the idea. My Dad was pretty pissed!
So Dad and I shlogged through tons of (paper) documents and LoC and other resources trying to help him remember who the speaker was and where the conference was held. After a few weeks of digging, we got a copy of the (hard to locate) conference proceedings, and now that brand new patent looks like it's toast.
Now here's the rub - the only reason why this patent was invalidated was because my dad is still in the industry - and he's well over retirement age. Everyone else my Dad works with thought the patent would toast them. Only my dad, and old researcher with a good memory, could help his company overcome the (invalid) patent. What if my dad was retired? What if he didn't attend that talk in the 1970s? Most people simply wouldn't have known where to look for the prior art. [And not every call for prior art is suitable for Slashdot.]
Old research and old researchers are good - not only for disposing of "new" patents, but for the value of the efforts and lessons learned. So much is forgotten.
...but Claude E. Shannon's paper, A Mathematical Theory of Communication has changed our outlook on information and communication. The importance of this paper on modern communication cannot be stressed enough, and it is very readable. If I had 10 papers to take to a desert island, surely this one would be on my list (:
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
This is shameless self-promotion, but you should read my book!
Technomanifestos discusses the truly thought-provoking, inspirational, seminal computer papers of the 20th century, from Turing's "On Computable Numbers" and "Computing Machinery and Intelligence", to Alan Kay's "Personal Dynamic Media" to Larry Wall's States of the Perl Onion.
The book delves into the historical, biographical, and scientific context of works such as these and follows the thread of inspiration to today's world. If you want to know where the Internet germinated, or how Marshall McLuhan and Pierre de Chardin influenced the World Wide Web (or even who McLuhan and de Chardin are!) you should pick up my book. And then read it.
Technomanifestos tracks the evolution of the MIT hacker, from the dapper Boston Brahmin Vannevar Bush to the famously unkempt Richard Stallman, and introduces the cast of lesser-known (to the non-Slashdot world) but crucially inventive individuals such as Ivan Sutherland and Seymour Papert.
Moreover, it discusses how the truly great computing ideas come from people who recognize that technology, especially information technology, has the power to transform people and society--these are (in the words of similarly great books) tools for thought and dream machines.
Or if you have no interest in helping me pay my DSL bill, you can go straight to the sources, many of which are available online.
author,
Does anyone know of a website where you can get access to comp sci and comp eng papers and stuff?
Try looking at arxiv.org and CiteSeer.
OS Reviews: Free and Open Source Software
Though it has very few entries, and is no longer updated, there are at least two papers in that list that the typical Slashdotter may have heard about: Go To Statement Considered Harmful, by Dijkstra, and Reflections on Trusting Trust, by Ken Thompson.
The remaining ACM Classics of the Month are here.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Donald Knuth has written a lot of interesting papers, but his paper on TeXs line-breaking algoritm
and as far as I know, the algoritm is still state of the art and is used only by TeX, InDesign and an addition to QuarkXPress.
-- Rolf Lindgren, cand.psychol
As a PhD student, I often have to look for papers in the computer science field ; and very often, CiteSeer yields better results - or, rather, different results, but with a very good cross-referencing system. You can directly jump to the other papers cited by the paper you're reading, and you can see which papers did cite it, too.
The URL :
http://citeseer.nj.nec.com/cs
That said, I often find very interesting ideas in scientific papers, but sometimes things can't be implemented with current technology (I'm still talking about computer science domain, since that's what I know), or sometimes, the good idea in the paper is obsoleted a few years later.
For instance, I remember a scheduling algorithm to read disk blocks in a Video-On-Demand server : it was maybe very clever when it was written, when they had to feed 155 Mbps with a computer having 16 MB of RAM, but today, you have maybe 10 times more throughput, but 100 times more RAM - so you can use simpler, memory-hungry, buffering methods.
The problem is, that it's difficult (IMHO) to say "OK, this paper is theoretically interesting, but we can't implement this today, BUT we will probably be able to do it in a few (dozen) years", because you don't know what will and won't evolve (in my previous example, it was easy to predict that network bandwidth and memory size would increase, but it was maybe harder to guess that MPEG4 and DivX would allow the bitrate of a video stream to stay low...)
"On computable numbers, with an application to the Entscheidungsproblem"" is unarguably the paper that began the field of computer science as we understand it today. Here we have the first descriptions of universal computing devices, Turing machines, which eventually led to the idea of universal stored-program digital computers. The paper even seems to describe, in what is unarguably the first ever conceptual programming language, a form of continuation passing style in the form of the "skeleton tables" Turing used to abbreviate his Turing machine designs. It's also relatively easy reading compared to many other scientific papers I've seen.
Along with this we might also include Alonzo Church's 1941 paper "The Calculi of Lambda Abstraction" (which sadly does not appear to be anywhere online), where the lambda calculus, the basis for all functional programming languages, is first described.
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
Since nobody who seems to have actually read any computer science papers has posted, here are two that immediately come to my mind.
:)
Vannevar Bush. As We May Think. Atlantic Monthly, July, 1945.
This paper put forth the very first ideas about how people can mechanically search for information. While we don't have desks with levers on them, we do have Google.
Tim Berners Lee. Information Management: A Proposal. 1989.
This paper is where Tim Berners Lee proposes what we now know as the world wide web. It's an interesting read if you'd like to see what the original intent of the web was so that you can compare it to what we have today.
A place to look for good old computer science papers is in older issues of Communications of the ACM. There are lots of articles in plain English that you may find of interest. If you are a university student, your school may have a subscription to the ACM Digital Library. If they do, you can read all the issues back to 1958.
Also, you can find a lot of interesting CS publications at Citeseer. They have a page with the top 200 most accessed papers of all times. When I skimmed through it, I saw quite a few titles that may be of interest.
In the section titled GENERIC STRUCTURE, HIERARCHIES , Sutherland describes how he restructured SKETCHPAD in what we would immediately recognize as an OO manner:
Later in the section DEMONSTRATIVE LANGUAGE we see what we might call today the association of classes with methods as Sutherland notes:
So what is the basic idea? That computers should not be constrained to the physical desktop, but should become an everyday and seamless part of our lives. And in this paper, Weiser and his team at Xerox PARC introduced location-based computing; devices of all form factors, from small PDAs to tablet PCs to electronic whiteboards; sensors for integrating the physical and virtual worlds; wireless networking to make it all connected no matter where you were (in their office building anyway). Weiser's vision is so influential, that there are now (literally) thousands of researchers working on what he called ubiquitous computing, as well as several research conferences devoted to this theme, not to mention the direction that the commercial world has already taken with PDAs, WiFi, sensor networks, and so on.
A recent short job assignment at HP let me run amok through the online libraries of both IEEE and ACM. It was interesting to see published articles from 5-10 years ago that directly covered topics that were the hot issues in the office today. Looking at the issues that were hot topics in the last few companies over the past 2 years, I saw the same pattern of scholarly articles being about 5-10 years ahead of the industry.
While working in medium to larger companies, I would find the number of people who did not even understand simple concepts of Computer Science frightening.
I am curious as to how much effort is wasted reinventing the wheel. I know a lot, because as a programmer on death march projects, I rarely have the hours to devote to finding how other people solved the same problem 5-30 years ago. That pointy haired boss breathing down my back thinks that any time not spent slaving over a hot keyboard is a waste of time. As the old saying: it is hard to remember the job is to drain the swamp when you are up to your armpits wrestling with gators. No amount of showing that spending a few hours sharpening the saw each week could save far more time that what appeared to be wasted. One past job allowed some time to be billed to research each week until some phb wandered by to bitch about it. It was the appearance of goofing off reading that made the boss look worse than the schedule slipping. And appearances appear to be more important in today's economy than actual results.
I think you mean "The Calculi of Lambda Conversion" , or are they two different things?
Here is a neat site that I found (yep, using Google):
Great Papers in Computer Science:
http://bit.csc.lsu.edu/~chen/GreatPapers.html
I kept trying to put the TOC from the site in this comment, but Slashdot kept saying that the line length was too short. Since it was just plain text, I do not understand what was going on with that. So sorry, but the link really is worth checking out. Good reading!