Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
List of publications in computer science
Main Page | See live article | Alphabetical index

List of publications in computer science

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

There are some reasons why a particular publication might be regarded as important:

Table of contents
1 Computability
2 Computational complexity theory
3 Algorithms
4 Algorithmic information theory
5 Information theory
6 Operating system
7 Databases
8 Cryptography
9 Artificial intelligence
10 Machine learning
11 Computer vision
12 Compilers
13 Formal verification
14 Software engineering
15 Parallel computing
16 Computer networks
17 See also


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 , Effect

On certain formal properties of grammars

Description: The Chomsky hierarchy, a containment hierarchy of classes of formal grammars that generate formal languages was introduced.

Importance: Topic creator, Breakthrough , Effect

Finite automata and their decision problem

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

Importance: Topic creator, Breakthrough , Effect, Introduction

Computational complexity theory

On the computational complexity of algorithms

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

Importance: Topic creator, Breakthrough, Effect

The complexity of theorem proving procedures

Description: This paper introduced the concept of NP-Completeness and proved that Boolean satisfiability problem(SAT) is NP-Complete.

Importance: Topic creator, Breakthrough, Effect

Reducibility among combinatorial problems

Description: This paper showed that 21 different problems are NP-Complete and showed the importance of the concept.

Importance: Effect

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, Effect, Latest and greatest

Theory and Applications of Trapdoor functions

Description: This paper introduced the concept of Trapdoor functions and described some of its application, like in cryptography.

Importance: Topic creator, Breakthrough

The Knowledge Complexity of Interactive Proof Systems

Description: This paper introduced the concept of zero knowledge.

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


Description: IP is a complexity class whose characterization is quite different from the usual time/space bounded computational classes. In this paper Shamir showed the IP = PSPACE, hence each problem in one complexity class is solvable in the other.

Importance: Breakthrough

Computational Complexity

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: Breakthrough, Effect

A Machine-Oriented Logic Based on the Resolution Principle

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

Importance: Topic Creator, Breakthrough, Effect

Optimization by simulated annealing

Description: A very common heuristic for NP-Complete problems.

Importance: Effect

The Art of Computer Programming

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: Effect

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 de facto standard for basic algorithms teaching. The only problem with this 1184-page book is that it might cause severe pain when falling on your foot.

Importance: Introduction, Effect

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, Effect

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, Effect

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, Effect

A Method for the Construction of Minimum Redundancy Codes

Description: The Huffman coding.

Importance: Effect, Breakthrough

A Universal Algorithm for Sequential Data Compression

Description: The LZ77 compression algorithm.

Importance: Effect, Breakthrough

Elements of Information Theory

Description: A good and popular introduction to information theory.

Importance: Effect, Introduction

Operating system

An experimental timesharing system.

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

Importance: Effect

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: Effect, Breakthrough

Scheduling Techniques for Concurrent Systems

Description: Algorithms for coscheduling of related processes were given

Importance: Effect


A relational model for large shared data bank

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

Importance: Topic creator, Breakthrough, Effect

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, Effect

Mining association rules between sets of items in large databases

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

Importance: Topic creator, Introduction, Effect


Communication Theory of Secrecy Systems

Description: Information theory based analysis of cryptography.

Importance: Breakthrough, Introduction, Effect

New directions in cryptography

Description: This paper suggested public key cryptography and invented Diffie-Hellman key exchange.

Importance: Topic creator, Breakthrough, Introduction, Effect, 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 encryption method.

Importance: Breakthrough, Effect

How to Share a Secret

\Description: A safe method for sharing a secret.

Importance: Topic creator, Breakthrough

Artificial intelligence

Computing machinery and intelligence

Description: This paper discusses whether machine can think and suggested the Turing test as a method for checking it. In a sense, this was the beginning of artificial intelligence

Importance: Topic creator, Breakthrough, Effect

A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence

Description: This summer research proposal marks the areas of research in artificial intelligence since then. It was a very long summer.

Importance: Effect

Machine learning

Language identification in the limit

Description: This paper created
Algorithmic learning theory.

Importance: Topic creator, Breakthrough, Effect

On the uniform convergence of relative frequencies of events to their probabilities

Description: Statistical learning theory, statistical uniform convergence and the VC dimension. Importance: Breakthrough, Effect

A theory of the learnable

Description: The Probably approximately correct learning (PAC learning) framework.

Importance: Topic creator, Breakthrough, Effect

Learnability and the Vapnik-Chervonenkis dimension

Description: The complete characterization of PAC learnability using the VC dimension.

Importance: Breakthrough, Effect

Cryptographic limitations on learning boolean formulae and finite automata

Description: Proving negative results for PAC learning.

Importance: Effect

The strength of weak learnability

Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework.

Importance: Breakthrough, Effect

Learning in the presence of malicious errors

Description: Proving possibility and imposibility result in the malicious errors framework.

Importance: Breakthrough, Effect

Computer vision

The Phase Correlation Image Alignment Method

Description: A correlation method based upon the invert Fourier transform

Importance: Effect

An Iterative Image RegistrationTechnique with an Application to Stereo Vision

Description: This paper provides efficient technique for image registration

Importance: Effect

The Laplacian Pyramid as a compact image code

Description: A technique for image encoding using local operators of many scales

Importance: Effect

Condensation -- conditional density propagation for visual tracking

Description: A technique for visual tracking

Importance: Effect


YACC: Yet another compiler-compiler

Description: Yacc is a tool that made compiler writing much easier.

Importance: Effect

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, Effect

Formal verification

Assigning meanings to programs

Description: Introduced the idea of attaching logical assertions to points in a program in order to prove its correctness and influenced C. A. R. Hoare's seminal work on program verification.

Importance: Topic creator, Breakthrough, Effect, Introduction

An axiomatic basis for computer programming

Description: Axiomatic foundation for program correctness proofs was laid. The importance of the use of formal methods is explained.

Importance: Topic creator, Breakthrough, Effect, Introduction

The temporal logic of programs

Description: The use of temporal logic was suggested as a method for formal verification. Importance: Topic creator, Effect

Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints

Description: Introducing abstract interpretation for the verification of computer programs by sound approximations.

Importance: Topic creator, Effect.

Software engineering

Go To Statement Considered Harmful

Description: Don't use goto - the beginning of structured programming.

Importance: Topic creator, Effect

On the criteria to be used in decomposing systems into modules

Description: The importance of modularization and information hiding.

Importance: Effect

The Mythical Man-Month: Essays on Software Engineering

Description: Throwing more people at the task will not speed its completion...

Importance: Effect

No Silver Bullet: Essence and Accidents of Software Engineering

Description: We will keep having problems with software...

Importance: Effect

The Cathedral and the Bazaar

Description: Open source methodology.

Importance: Effect

Design Patterns: Elements of Reusable Object Oriented Software

Description: This book was the first to define and list design patternss in computer science

Importance: Topic creator, Effect

Parallel computing


The Structure of "THE"-Multiprogramming System

Description: The introduction of basic primitives like mutex as the basis of multiprocessing programming.

Importance: Breakthrough, Effect

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs ''

Description: Requirements that guarantee the correct execution of multi process programs were defined.

Importance: Breakthrough, Effect

LogP: Towards a realistic model of parallel computation

Description: The LogP framework for parallel computing was suggested. The LogP provided a way to bridge the gap between theoretical analysis of algorithm and building real world systems.

Importance: Effect

Computer networks

Ethernet: Distributed packet switching for local computer networks

Description: The Ethernet protocol.

Importance: Effect, Latest and greatest

See also