List of important publications in computer science
This is a list of important publications in computer science, organized by field.
There are a number of reason why a particular publication might be regarded as important:
- Topic creator - A publication that created a new topic
- Break through - A publication that changed scientific knowledge significantly
- Introduction - A publication that is a good introduction or survey of a topic
- Impact - A publication which had a major impact on the world or on the research
- Latest and greatest - The current most advanced result in a topic
On computable numbers, with an application to the Entscheidungsproblem
- Alan Turing
- Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265. Errata appeared in Series 2, 43 (1937), pp 544-546.
- Online version
Description: Here it all began - The Turing Machine
Importance: Topic creator, Break through, Impact
On the computational complexity of algorithms
Description: This paper gave computational complexity its name and seed.
Importance: Topic creator, Break through, Impact
The complexity of theorem proving procedures
- S. A. Cook
- Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.
Description: This paper introduced the concept of NP-Completeness and proved that SAT is NP-Complete.
Importance: Topic creator, Break through, Impact
Reducibility among combinatorial problems
- R. M. Karp
- In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, New York, NY, 1972.
Description: This paper showed that 21 different papers are NP-Complete and showed the importance of the concept.
Importance: Impact
Computers and Intractability: A Guide to the Theory of NP-Completeness
Description: The main importance of this book is due to its extensive list of more than 300 NP-Complete problems. This list became a common reference and definition. It is important to note that though the book was published only few years after the concept was defined such an extensive list was found.
Importance: Introduction, Impact, Latest and greatest
The Knowledge Complexity of Interactive Proof Systems
Description: This paper introduced the concept of zero knowledge.
Importance: Topic creator, Break through
How to Construct Random Functions
Description: This paper showed that the existence of one way functions leads to computational randomness.
Importance: Topic creator, Break through, Latest and greatest
Description: This book provides a very good introduction to Computational Complexity
Importance: Introduction
A machine program for theorem proving
Description: The DLL algorithm. The basic algorithm for SAT and other NP-Complete problems.
Importance: Break through, Impact
Optimization by simulated annealing
Description: A very common heuristic for NP-Complete problems.
Importance: Impact
Description: This set of textbooks used to be very popular algorithms books. The algorithms were written in the MIX assembly language. Due to that, the algorithms were very precise but not very readable...
Importance: Impact
Introduction to algorithms
Description: As its name indicates this text book is a very good introduction to algorithms. This book became so popular that it is almost de facto standard for basic algorithms teaching. The only problem with this 1028 pages book is that it might cause severe pain when falling on your foot.
Importance: Introduction, Impact
A mathematical theory of communication
Description: This paper created communication theory and information theory.
Importance: Topic creator, Break through, Introduction, Impact
A mathematical theory of communication
Description: This paper created communication theory and information theory.
Importance: Topic creator, Break through, Introduction, Impact
A Method for the Construction of Minimum Redundancy Codes
- David A. Huffman
- Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.
Description: The Huffman coding.
Importance: Impact, Break trough
A Universal Algorithm for Sequential Data Compression
- Jacob Ziv
- Abraham Lempel
- IEEE Transactions on Information Theory, Vol. 23, No. 3, pp. 337-343.
- http://citeseer.nj.nec.com/ziv77universal.html
Description: The LZ77 compression algorithm.
Importance: Impact, Break trough
Elements of Information Theory
Description: A good and popular introduction to information theory.
Importance: Impact, Introduction
A relational model for large shared data bank
- E. F. Codd
- Communications of the ACM, 13(6):377-- 387, June 1970
Description: This paper introduced the relational model for databases.
This model became the number one model.
Importance: Topic creator, Break through, Impact
The Entity Relationship Model - Towards a Unified View of Data
- P.P-S. Chen
- ACM Transactions on Database Systems, Vol. 1, No. 1, March 1976, pp. 9-36
Description: This paper introduced the ERD method of database design.
Importance: Break through, Impact
Mining association rules between sets of items in large databases
Description: Association rules, a very common method for data mining.
Importance: Topic creator, Introduction, Impact
New directions in cryptography
Description: This paper suggested public key cryptography and invented Diffie-Hellman key exchange.
Importance: Topic creator, Break through, Introduction, Impact, Latest and greatest (A great paper from every perspective...)
A Method for Obtaining Digital Signatures and Public Key Cryptosystems
Description: The RSA encryption method. The first public key method.
Importance: Break through, Impact
How to Share a Secret
- Shamir, A.
- Comm. Assoc. Comput. Mach., vol.22, no.11, pp.612--613 (Nov. 1979)
Description: A safe method for sharing a secret.
Importance: Topic creator, Break through
Language identification in the limit
- E. M. Gold
- Information and Control, 10:447--474, 1967
Description: This paper created Algorithmic learning theory.
Importance: Topic creator, Break through, Impact
On the uniform convergence of relative frequencies of events to their probabilities
Description: Statistical learning theory, statistical uniform convergence and the VC dimension.
Importance: Break through, Impact
A theory of the learnable
- Valiant, L.G.
- Communications of the ACM, 27(11): 1134--1142 (1984)
Description: The Probably approximately correct learning (PAC learning) framework.
Importance: Topic creator, Break through, Impact
YACC: Yet another compiler-compiler
Description: Yacc is a tool that made compiler writing much easier.
Importance: Impact
Compilers: Principles, Techniques and Tools
Description: This book became a classic in compiler writing. It is also known as the Dragon book, after the (red) dragon that appears on its cover.
Importance: Introduction, Impact
GOTO Considered Harmful
Description: Don't use goto - the beginning of structured programming.
Importance: Topic creator, Impact
No Silver Bullet :Essence and accidents of software engineering
- F. Brooks
- Computer, 20(4):10-19, April 1987
- http://www.virtualschool.edu/mon/SoftwareEngineering/BrooksNoSilverBullet.html
Description: We will keep having problems with software...
Importance: Impact
The Cathedral and the Bazaar
Description: Open source methodology.
Importance: Impact
Design Patterns: Elements of Reusable ObjectOriented Software
Description: This book was the first to deifne and list design patterns in computer science
Importance: Topic creator, Impact
Ethernet: Distributed packet switching for local computer networks
Description: The Ethernet protocol.
Importance: Impact, Latest and greatest
Referenced By
Category:list | Comp.sc. | Computer Science | Computer Sciences | Computer Scientists | Computer scientist | Computing science | List of Refernce Tables | List of computer scientists | List of intellectual/social/spiritual/artistic reference tables | List of list of pages | List of lists | List of lists of lists | List of reference tables | Lists
|
