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
I wonder how many IT gurus are members of ACM or IEEE Computer Society? The % of /. members who are in ACM must be very small because ACM only has 75,000 members in total.
Two wrongs don't make a right, but three lefts do.
"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/
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 has been reported in Slashdot a while ago, but it deserves another mention: the manuscripts of Edsger W. Dijkstra. There are more than a thousand documents written by Dijkstra in this archive, and very interesting ones too -- careful or you'll lose days browsing it like I did.
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,
Citeseer was cited in the blurb, but a really nice service that they provide is the Computer Science Directory. There you can look for papers sorted by domain, and ranked by several criteria like "authority". The top papers are usually a good read if you are interested in a particular domain.
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/
I think Alan Kay would agree that not all CS papers of a worthy read are in CS..
:)
Chemistry
:)
g
Information Theory was certainly not in CS when it was orginally written in the 1940s..instead it was in Telcommunications and Mathematics
Basically the areas you shoudl be looking at are:
Logic
Philosphy
Mathematics
Physics
Bilogy
For example the concept of meta data.. ie data that has diferent menains based on context is common in all these areas and has direct applicatiosn to CS! Some of the current concepts of Semantic web are from this area and started in Language studies..:)
Rmember the old adage of the crusty old CS professor that CS is multidisplinary still applies!
Fred Grott
ShareMeTechnologies-The Mobile Future
http://www.jroller.com/page/shareme/Weblo
#11: Thou shalt not covet thy neighbor's tagline.
Don't Tread on OpenSource
- Van Jacobson and Michael J. Karels Congestion Avoidance and Control. SIGCOMM, 1988
- J.H. Saltzer, D.P. Reed and D.D. Clark, End-to-end Arguments in System Design, ACM Transactions on Computer Systems, Nov 1984, p. 277-288
- Jeffrey C. Mogul The Case for Persistent-Connection HTTP. In Proceedings of ACM Sigcomm '95, pp. 299-313, Cambridge, MA, August 1995
Maybe someone else will have better luck tracking down a link to Mogul's paper.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.
I'm learning to read classical Greek so that I may read Euripides.
An admirable exercise.
Journalist I.F. Stone, rather late in life, taught himself ancient Greek, in order to read the actual source documents relating to the trial and execution of Socrates.
No translation would suffice: Stone felt that only by reading the original text for himself could he arrive at the insight he desired.
-kgj
-kgj
MIT Open Courseware These are not whitepapers and the like. Rather, they are mostly lecture notes from the professors who teach the classes there - Enjoy!
p.s. - Check out the link in my earlier post
This is the paper by Diffie and Hellman that originated public-key cryptography. This paper explained for the first time (in an unclassified place) how two parties could communicate privately over an open channel without previously agreeing on a secret key. Every time your browser says, "Setting up a secure connection..." when you order from Amazon or check your bank account, you're witnessing the impact of this work.
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!
http://john.regehr.org/reading_list/