Image:Split-arrows.svg
  It has been suggested that this article be split into multiple articles. (Discuss)
This list needs to be alphabetized.

This is a list of important publications in computer science, organized by field.

Some reasons why a particular publication might be regarded as important:

  • Topic creator – A publication that created a new topic
  • Breakthrough – A publication that changed scientific knowledge significantly
  • Introduction – A publication that is a good introduction or survey of a topic
  • Influence – A publication which has significantly influenced the world
  • Latest and greatest – The current most advanced result in a topic

Contents

Computability

Computability: An introduction to recursive function theory

Description: A very popular textbook.

Importance: Introduction

Decidability of second order theories and automata on infinite trees

Description: The paper presented the tree automaton, an extension of the automata. The tree automaton had numerous applications to proofs of correctness of programs.

Importance: Topic creator, Breakthrough, Influence, Introduction

Finite automata and their decision problems

Description: Mathematical treatment of automata, proof of core properties, and definition of non-deterministic finite automaton

Importance: Topic creator, Breakthrough, Influence, Introduction

Introduction to Automata Theory, Languages, and Computation

Description: A popular textbook.

Importance: Introduction

On certain formal properties of grammars

Description: This article introduced what is now known as the Chomsky hierarchy, a containment hierarchy of classes of formal grammars that generate formal languages.

Importance: Topic creator, Breakthrough, Influence

On computable numbers, with an application to the Entscheidungsproblem

Description: This article set the limits of computer science. It defined the Turing Machine, a model for all computations. On the other hand it proved the undecidability of the halting problem and Entscheidungsproblem and by doing so found the limits of possible computation.

Importance: Topic creator, Breakthrough, Influence

Computational complexity theory

A machine-independent theory of the complexity of recursive functions

Description: The Blum axioms.

Importance: Breakthrough, Influence

Algebraic methods for interactive proof systems

  • Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan
  • Journal of the ACM, 39(4):859–868, 1992.

Description: This paper showed that PH is contained in IP.

Importance: Breakthrough

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 Boolean satisfiability problem(SAT) is NP-Complete. Note that similar ideas were developed independently slightly later by Leonid Levin at "Levin, Universal Search Problems. (Problemy Peredatsi Informatsii) 9(3):265-266, 1973".

Importance: Topic creator, Breakthrough, Influence

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. Though the book was published only few years after the concept was defined such an extensive list was found.

Importance: Introduction, Influence, Latest and greatest

Degree of difficulty of computing a function and a partial ordering of recursive sets

Description: This technical report was the first publication talking about what later was renamed computational complexity

Importance: Topic creator, Breakthrough

How to Construct Random Functions

Description: This paper showed that the existence of one way functions leads to computational randomness.

Importance: Topic creator, Breakthrough, Latest and greatest, Influence

IP = PSPACE

Description: IP is a complexity class whose characterization (based on interactive proof systems) is quite different from the usual time/space bounded computational classes. In this paper, Shamir extended the technique of the previous paper by Lund, et al., to show that PSPACE is contained in IP, and hence IP = PSPACE, so that each problem in one complexity class is solvable in the other.

Importance: Breakthrough

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 problems are NP-Complete and showed the importance of the concept.

Importance: Influence

The Knowledge Complexity of Interactive Proof Systems

Description: This paper introduced the concept of zero knowledge.

Importance: Topic creator, Breakthrough

Letter from Gödel to von Neumann

Description: Gödel discusses the idea of efficient universal theorem prover

Importance: Breakthrough

On the computational complexity of algorithms

Description: This paper gave computational complexity its name and seed.

Importance: Topic creator, Breakthrough, Influence

Paths, trees, and flowers

  • Jack Edmonds
  • Canadian Journal of Mathematics, Vol 17, No -, 449-467, 1965

Description: There is a polynomial time algorithm to find a maximum matching in a graph that is not bipartite and another step toward the idea of computational complexity. For more information see.

Importance: Influence

Theory and Applications of Trapdoor functions

  • Andrew Chi-Chih Yao
  • Proc. 23rd Symposium on the Foundations of Computer Science (1982), pp. 80–91

Description: This paper creates a theoretical framework for Trapdoor functions and described some of their applications, like in cryptography. Note that the concept of trapdoor functions was brought at "New directions in cryptography" six years earlier (See section V "Problem Interrelationships and Trap Doors.").

Importance: Topic creator, Breakthrough

Computational Complexity

Description: This book provides a very good introduction to Computational Complexity

Importance: Introduction

Interactive Proofs and the Hardness of Approximating Cliques

Probabilistic Checking of Proofs: A New Characterization of NP

Proof Verification and the Hardness of Approximation Problems

  • Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy
  • Journal of the ACM, 45:501–555, 1998.

Description: These three papers established the surprising fact that certain problems in NP remain hard even when only an approximative solution is required.

Importance: Topic creator, Breakthrough, Influence

Computational Linguistics

Realization of Natural-Language Interfaces Using Lazy Functional Programming

  • Richard A. Frost
  • ACM Computing Surveys Volume 38 Issue 4 Article 11, December 2006
  • Online copy

Description: This survey documents relatively less researched importance of lazy functional programming languages (i.e. Haskell) to construct Natural Language Processors and to accommodated many linguistic theories.

Importance: Survey, Introduction.

Algorithms

See also List of algorithms.

A machine program for theorem proving

  • M. Davis, G. Logemann, D. Loveland
  • Communications of the ACM, 5:394–397, 1962. reprinted at Siekmann, Jörg and Graham Wrightson (eds), Automation of Reasoning, vol. 1, Springer Verlag, 1983, pp. 267-270.

Description: The DLL algorithm. The basic algorithm for SAT and other NP-Complete problems.

Importance: Breakthrough, Influence

A Machine-Oriented Logic Based on the Resolution Principle

Description: First description of resolution and unification used in automated theorem proving; used in Prolog and logic programming.

Importance: Topic Creator, Breakthrough, Influence

The traveling-salesman problem and minimum spanning trees

  • M. HELD, R. M. KARP
  • Operations Res. 18 (1970),1138-1162

Description: The use of an algorithm for minimum spanning tree as an approximation algorithm for the NP-CompleteTravelling salesman problem. Approximation algorithms became a common method for coping with NP-Complete problems.

Importance: Breakthrough, Influence

A polynomial algorithm in linear programming

Description: For long, there was no provably polynomial time algorithm for the linear programming problem. Khachiyan was the first to provide an algorithm that was polynomial (and not just was fast enough most of the time as previous algorithms). Later, Karmarkar presented a faster algorithm at: Narendra Karmarkar(1984). "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol 4, nr. 4, p. 373–395.

Importance: Influence

Probabilistic algorithm for testing primality

Description: The paper presented the Miller-Rabin primality test and outlined the program of randomized algorithms.

Importance: Topic Creator, Breakthrough, Influence

Optimization by simulated annealing

  • Kirkpatrick, S., Gelatt, C., & Vecchi, M.
  • Science, Number 4598, 13, pages 671–680, May 1983.
  • Online copy

Description: This article described simulated annealing which is now a very common heuristic for NP-Complete problems.

Importance: Influence

The Art of Computer Programming

Description: This monograph has three popular algorithms books and a number of fascicles. The algorithms are written in both English and MIX assembly language (or MMIX assembly language in more recent fascicles). This makes algorithms both understandable and precise. However, the use of a low-level programming language frustrates some programmers more familiar with modern structured programming languages.

Importance: Influence

Algorithms + Data Structures = Programs

Description: An early, influential book on algorithms and data structures, with implementations in Pascal.

Importance: Influence

The Design and Analysis of Computer Algorithms

Description: One of the standard texts on algorithms for the period of approximately 1975–1985.

Importance: Influence, Introduction

How to Solve It By Computer

Description: Explains the Whys of algorithms and data-structures. Explains the Creative Process, the Line of Reasoning, the Design Factors behind innovative solutions.

Importance: Introduction

See Also: How to Solve It

Algorithms

Description: A very popular text on algorithms in the late 1980s. It was more accessible and readable (but more elementary) than Aho, Hopcroft, and Ullman. There are more recent editions.

Importance: Influence

Introduction to Algorithms

Description: As its name indicates this textbook is a very good introduction to algorithms. This book became so popular that it is almost the de facto standard for basic algorithms teaching.

Importance: Introduction, Influence

Algorithmic information theory

A formal theory of inductive inference

Description: This was the beginning of Algorithmic information theory and Kolmogorov complexity. Note that though Kolmogorov complexity is named after Andrey Kolmogorov, he said that the seeds of that idea are due to Ray Solomonoff. Andrey Kolmogorov contributed a lot to this area but in later articles.

Importance: Topic creator, Breakthrough, Influence

Algorithmic information theory

Description: A good introduction to Algorithmic information theory by one of the important people in the area.

Importance: Introduction

Information theory

A mathematical theory of communication

Description: This paper created communication theory and information theory.

Importance: Topic creator, Breakthrough, Introduction, Influence

Error detecting and error correcting codes

Description: In this paper, Hamming introduced the idea of error-correcting code. He created the Hamming code and the Hamming distance and developed methods for code optimality proofs.

Importance: Topic creator, Breakthrough, Introduction, Influence

A Method for the Construction of Minimum Redundancy Codes

Description: The Huffman coding.

Importance: Influence, Breakthrough

A Universal Algorithm for Sequential Data Compression

Description: The LZ77 compression algorithm.

Importance: Influence, Breakthrough

Elements of Information Theory

Description: A good and popular introduction to information theory.

Importance: Influence, Introduction

Operating systems

An experimental timesharing system.

Description: This paper discuss time-sharing as a method of sharing computer resource. This idea changed the interaction with computer systems.

Importance: Influence

The Working Set Model for Program Behavior

Description: The beginning of cache. For more information see SIGOPS Hall of Fame.

Importance: Influence, Breakthrough

Virtual Memory, Processes, and Sharing in MULTICS

Description: The classic paper on the most ambitious operating system in the early history of computing. Difficult reading, but it describes the implications of trying to build a system that takes information sharing to its logical extreme. Most operating systems since Multics have incorporated a subset of its facilities.

Importance: Influence, Breakthrough

A note on the confinement problem

Description: This paper addresses issues in constraining the flow of information from untrusted programs. It discusses covert channels, but more importantly it addresses the difficulty in obtaining full confinement without making the program itself effectively unusable. The ideas are important when trying to understand containment of malicious code, as well as aspects of trusted computing.

Importance: Influence

The UNIX Time-Sharing System

Description: The Unix operating system and its principles were described in this paper. The main importance is not of the paper but of the operating system, which had tremendous effect on operating system and computer technology.

Importance: Influence, Breakthrough

Weighted voting for replicated data

  • David K. Gifford
  • Proceedings of the 7th ACM Symposium on Operating Systems Principles, pages 150-159, December 1979. Pacific Grove, California
  • Online copy (few formats)

Description: This paper describes the consistency mechanism known as quorum consensus. It is a good example of algorithms that provide a continuous set of options between two alternatives (in this case, between the read-one write-all, and the write-one read-all consistency methods). There have been many variations and improvements by researchers in the years that followed, and it is one of the consistency algorithms that should be understood by all. The options available by choosing different size quorums provide a useful structure for discussing of the core requirements for consistency in distributed systems.

Importance: Influence, Breakthrough

Experiences with Processes and Monitors in Mesa

Description: This is the classic paper on synchronization techniques, including both alternate approaches and pitfalls.

Importance: Influence

Scheduling Techniques for Concurrent Systems

  • J. K. Ousterhout
  • Proceedings of Third International Conference on Distributed Computing Systems, 1982, 22—30.

Description: Algorithms for coscheduling of related processes were given

Importance: Influence

A Fast File System for UNIX

Description: The file system of UNIX. One of the first papers discussing how to manage disk storage for high-performance file systems. Most file-system research since this paper has been influenced by it, and most high-performance file systems of the last 20 years incorporate techniques from this paper.

Importance: Influence

The Design and Implementation of a Log-Structured File System

Description: Log-structured file system.

Importance: Influence

Microkernel operating system architecture and Mach

  • David L. Black, David B. Golub, Daniel P. Julin, Richard F. Rashid, Richard P. Draves, Randall W. Dean, Alessandro Forin, Joseph Barrera, Hideyuki Tokuda, Gerald Malan, David Bohman
  • Proceedings of the USENIX Workshop on Microkernels and Other Kernel Architectures, pages 11-30, April 1992.

Description: This is a good paper discussing one particular microkernel architecture, and the benefits over more monolithic kernel approaches to system design. Mach underlies Mac OS X, and its architecture had a significant impact on the design of the Windows NT kernel and modern microkernels like L4.

Importance: Influence

An Implementation of a Log-Structured File System for UNIX

Description: The paper was the first production-quality implementation of that idea which spawned much additional discussion of the viability and short-comings of log-structured filesystems. While "The Design and Implementation of a Log-Structured File System" was certainly the first, this one was important in bringing the research idea to a usable system..

Importance: Influence

Soft Updates: A Solution to the Metadata Update problem in File Systems

Description: A new way of maintaining filesystem consistency.

Importance:

Databases

A relational model for large shared data banks

Description: This paper introduced the relational model for databases. This model became the number one model.

Importance: Topic creator, Breakthrough, Influence

Binary B-Trees for Virtual Memory

  • Rudolf Bayer
  • ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219-235.

Description: This paper introduced the B-Trees data structure. This model became the number one model.

Importance: Influence

Relational Completeness of Data Base Sublanguages

  • E. F. Codd
  • In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972)
  • Online version (PDF)

Description: Completeness of Data Base Sublanguages

Importance:

The Entity Relationship Model – Towards a Unified View of Data

Description: This paper introduced the Entity-relationship diagram(ERD) method of database design.

Importance: Breakthrough, Influence

SEQUEL: A structured English query language

  • Donald D. Chamberlin, Raymond F. Boyce
  • International Conference on Management of Data, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, Ann Arbor, Michigan, pp. 249–264

Description: This paper introduced the SQL language .

Importance: Influence

The notions of consistency and predicate locks in a database system

  • K.P. Eswaran, J. Gray, R.A. Lorie, I.L. Traiger
  • Communications of the ACM 19, 1976, 624--633

Description: This paper defined the concepts of transaction, consistency and schedule.It also argued that a transaction needs to lock a logical rather than a physical subset of the database.

Importance: Breakthrough, Influence

Mining association rules between sets of items in large databases

  • Rakesh Agrawal, Tomasz Imielinski, Arun Swami
  • Proc. of the ACM SIGMOD Conference on Management of Data, pages 207–216, Washington, D.C., May 1993
  • Online copy (HTML)

Description: Association rules, a very common method for data mining.

Importance: Topic creator, Introduction, Influence

Principles of Transaction-Oriented Database Recovery

  • Theo Härder, Andreas Reuter
  • ACM Computing Surveys 15(4), May 1983

Description: Introduced the ACID paradigm for transactions.

Importance: Introduction, Influence

Cryptography

The index of coincidence and its applications in cryptology

  • William F. Friedman
  • The index of coincidence and its applications in cryptology, Department of Ciphers. Publ 22. Geneva, Illinois, USA: Riverbank Laboratories, 1922.

Description: Presented the index of coincidence method for codebreaking.

Importance: Breakthrough, Influence

Treatise on the Enigma

Description: The breaking of the Enigma.

Importance: Breakthrough, Influence

Communication Theory of Secrecy Systems

Description: Information theory based analysis of cryptography. The original form of this paper was a confidential Bell Labs report from 1945, not the one published.

Importance: Breakthrough, Introduction, Influence

The Codebreakers, The Story of Secret Writing

Description: Almost nothing had been published in cryptography in several decades and very few non-government researchers were thinking about it. The Codebreakers, a popular and not academic book, made many more people aware and contains a lot of technical information, although it requires careful reading to extract it. Its 1967 appearance was followed by the appearance of many papers over the next few years.

Importance: Influence

Cryptographic Coding for Data-Bank Privacy

Description: Feistel ciphers are a form of cipher of which DES is the most important. It would be hard to overestimate the importance of either Feistel or DES. Feistel pushed a transition from stream ciphers to block ciphers. Although most ciphers operate on streams, most of the important ciphers today are block ciphers at their core.

Importance: Influence

Data Encryption Standard

  • NBS Federal Standard FIPS PUB 46, 15 Jan 1977.

Description: DES is not only one of the most widely deployed ciphers in the world but has had a profound impact on the development of cryptography. Roughly a generation of cryptographers devoted much of their time to attacking and improving DES.

Importance: Influence

New directions in cryptography

Description: This paper suggested public key cryptography and presented Diffie-Hellman key exchange. For more information about this work see: W.Diffie, M.E.Hellman, "Privacy and Authentication: An Introduction to Cryptography", in Proc. IEEE, Vol 67(3) Mar 1979, pp 397-427.

Importance: Topic creator, Breakthrough, Introduction, Influence

On the Signature Reblocking Problem in Public Key

Description: In this paper (along with Loren M. Kohnfelder,"Using Certificates for Key Distribution in a Public-Key Cryptosystem", MIT Technical report 19 May 1978), Kohnfelder introduced certificates (signed messages containing public keys) which are the heart of all modern key management systems.

Importance: Topic creator, Breakthrough, Influence

Secure Communications Over Insecure Channels

Description: This paper introduced a branch public key cryptography, known as public key distribution systems. Merkle work predated "New directions in cryptography" though it was published after it. The Diffie-Hellman key exchange is an implementation of such a Merkle system. Hellman himself has argued that the more correct name would be Diffie-Hellman-Merkle key exchange.

Importance: Influence

A Method for Obtaining Digital Signatures and Public Key Cryptosystems

Description: The RSA encryption method. The first public key encryption method.

Importance: Breakthrough, Influence

Using encryption for authentication in large networks of computers

Description: This paper introduced the basic ideas of cryptographic protocols and showed how both secret-key and public-key encryption could be used to achieve authentication.

Importance: Breakthrough, Influence

How to Share a Secret

Description: A safe method for sharing a secret.

Importance: Topic creator, Breakthrough

Data Security

Description: A paper that surveys the problems in creating secure systems. The description of database inference is particularly chilling; after reading this you'll understand why it is very difficult to publish aggregated information such as census data without accidentally exposing the private information of individuals.

Importance: influence

Security policies and security models

  • J. Goguen, J. Meseguer
  • IEEE symposium on security and privacy, 1982, pp11-20
  • Online version(PDF)

Description: Noninterference is the study of when interaction by one user with a system can affect what a second user sees. It can be applied to trying to stop an attacker disrupting the second user's view of the system, or to analysing whether a high-security first user can pass information to a low-level second user via a covert channel. This paper was the first to give a useful characterisation of this property.

Importance: influence

On the security of public key protocols

  • D Dolev, A Yao
  • IEEE transactions on Information Theory Vol 2 number 3, 1983

Description: Introduced the model of the adversary against which almost all cryptographic protocols are judged.

Importance: influence

Probabilistic Encryption

Description: The paper provides a rigorous basis to encryption (e.g., partial information) and shows that it possible to equate the slightest cryptanalysis to solve a pure math problem. Second, it introduces the notion of computational indistinguishability that has and will underpin our understanding of the world, since ultimately we all are bounded computational entities.

Importance: Breakthrough, influence

Fast, rigorous factorization and discrete logarithm algorithms

  • Carl Pomerance
  • D. S. Johnson, T. Nishizeki, A. Nozaki, H. S. Wilf, eds., Academic Press, Orlando, Florida, 1987, pp. 119-143.

Description: First published sub exponential algorithm to the Discrete logarithm problem. The Discrete logarithm problem is the base of many cryptographic systems. Pomerance algorithm is second chronologically to the work of Rich Schroeppel's work. Schroeppel rarely published and preferred to circulate his work to interested researchers. Schroeppel's work is referenced at Knuth, vol. 2, 2nd edition, pages 383-384.

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design

Description: This paper explains how to construct a zero-knowledge proof system for any language in NP.

Importance: Breakthrough, Influence

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority

Description: Seminal paper in secure function evaluation

Importance: Breakthrough, Influence

The Digital distributed system security architecture

  • M. Gasser, A. Goldstein, C. Kaufman, B. Lampson
  • Proceedings of the 1989 National Computer Security Conference, pages 305-319, 1989.
  • Online copy

Description: This paper discusses issues related to privileges and authentication of software and hardware components in distributed systems. It is interesting in that it formalizes the understanding of the rights used by programs and software running on bahalf of users and other entities. The concepts from this paper provide an early glimpse at the issues of atestation addressed much later by trusted computing architectures.

Importance: Influence

Kerberos: An Authentication Service for Open Network Systems

  • Jennifer G. Steiner, Clifford Neuman, Jeffrey I. Schiller
  • B. Clifford Neuman and Theodore Ts'o IEEE Communications, 32(9) pp33-38, September 1994.
  • See also Proc. USENIX Winter Conference, February 1988, pp. 191-202
  • Online version (HTML)

Description: The Kerberos authentication