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:
- 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
- Effect - A publication which had a major effect on the world or on the research
- Latest and greatest - The current most advanced result in a topic
Computability
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
Importance: Topic creator, Breakthrough, Effect
Importance: Topic creator, Breakthrough, Effect
Importance: Effect
Importance: Introduction, Effect, Latest and greatest
Importance: Topic creator, Breakthrough
Importance: Topic creator, Breakthrough
Importance: Topic creator, Breakthrough, Latest and greatest
Importance: Breakthrough
Importance: Introduction
Importance: Breakthrough, Effect
Importance: Topic Creator, Breakthrough, Effect
Importance: Effect
Importance: Effect
Importance: Introduction, Effect
Importance: Topic creator, Breakthrough, Effect
Importance: Introduction
Importance: Topic creator, Breakthrough, Introduction, Effect
Importance: Effect, Breakthrough
Importance: Effect, Breakthrough
Importance: Effect, Introduction
Importance: Effect
Importance: Effect, Breakthrough
Importance: Effect
Importance: Topic creator, Breakthrough, Effect
Importance: Breakthrough, Effect
Importance: Topic creator, Introduction, Effect
Importance: Breakthrough, Introduction, Effect
Importance: Topic creator, Breakthrough, Introduction, Effect, Latest and greatest (A great paper from every perspective...)
Importance: Breakthrough, Effect
Importance: Topic creator, Breakthrough
Importance: Topic creator, Breakthrough, Effect
Importance: Effect
Importance: Topic creator, Breakthrough, Effect
Importance: Topic creator, Breakthrough, Effect
Importance: Breakthrough, Effect
Importance: Effect
Importance: Breakthrough, Effect
Importance: Breakthrough, Effect
Importance: Effect
Importance: Effect
Importance: Effect
Importance: Effect
Importance: Effect
Importance: Introduction, Effect
Importance: Topic creator, Breakthrough, Effect, Introduction
Importance: Topic creator, Breakthrough, Effect, Introduction
Importance: Topic creator, Effect.
Importance: Topic creator, Effect
Importance: Effect
Importance: Effect
Importance: Effect
Importance: Effect
Importance: Topic creator, Effect
">
Importance: Breakthrough, Effect
Importance: Breakthrough, Effect
Importance: Effect
Importance: Effect, Latest and greatest
Computational complexity theory
On the computational complexity of algorithms
Description: This paper gave computational complexity its name and seed.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.Reducibility among combinatorial problems
Description: This paper showed that 21 different problems are NP-Complete and showed the importance of the concept.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.Theory and Applications of Trapdoor functions
Description: This paper introduced the concept of Trapdoor functions and described some of its application, like in cryptography.The Knowledge Complexity of Interactive Proof Systems
Description: This paper introduced the concept of zero knowledge.How to Construct Random Functions
Description: This paper showed that the existence of one way functions leads to computational randomness.IP = PSPACE
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.Computational Complexity
Description: This book provides a very good introduction to Computational ComplexityAlgorithms
A machine program for theorem proving
Description: The DLL algorithm. The basic algorithm for SAT and other NP-Complete problems.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.Optimization by simulated annealing
Description: A very common heuristic for NP-Complete problems.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...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.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.Algorithmic information theory
Description: A good introduction to Algorithmic information theory by one of the important people in the area.Information theory
A mathematical theory of communication
Description: This paper created communication theory and information theory.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, EffectA Method for the Construction of Minimum Redundancy Codes
Description: The Huffman coding.A Universal Algorithm for Sequential Data Compression
Description: The LZ77 compression algorithm. Elements of Information Theory
Description: A good and popular introduction to information theory.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. 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. Scheduling Techniques for Concurrent Systems
Description: Algorithms for coscheduling of related processes were givenDatabases
A relational model for large shared data bank
Description: This paper introduced the relational model for databases.
This model became the number one model.The Entity Relationship Model - Towards a Unified View of Data
Description: This paper introduced the Entity-relationship diagram(ERD) method of database design.Mining association rules between sets of items in large databases
Description: Association rules, a very common method for data mining.Cryptography
Communication Theory of Secrecy Systems
Description: Information theory based analysis of cryptography.New directions in cryptography
Description: This paper suggested public key cryptography and invented Diffie-Hellman key exchange.A Method for Obtaining Digital Signatures and Public Key Cryptosystems
Description: The RSA encryption method. The first public key encryption method.How to Share a Secret
\Description: A safe method for sharing a secret.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 intelligenceA 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.Machine learning
Language identification in the limit
Description: This paper created Algorithmic learning theory.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, EffectA theory of the learnable
Description: The Probably approximately correct learning (PAC learning) framework.Learnability and the Vapnik-Chervonenkis dimension
Description: The complete characterization of PAC learnability using the VC dimension.Cryptographic limitations on learning boolean formulae and finite automata
Description: Proving negative results for PAC learning. The strength of weak learnability
Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework. Learning in the presence of malicious errors
Description: Proving possibility and imposibility result in the malicious errors framework.Computer vision
The Phase Correlation Image Alignment Method
Description: A correlation method based upon the invert Fourier transform An Iterative Image RegistrationTechnique with an Application to Stereo Vision
Description: This paper provides efficient technique for image registration The Laplacian Pyramid as a compact image code
Description: A technique for image encoding using local operators of many scales Condensation -- conditional density propagation for visual tracking
Description: A technique for visual trackingCompilers
YACC: Yet another compiler-compiler
Description: Yacc is a tool that made compiler writing much easier.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.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. 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.The temporal logic of programs
Description: The use of temporal logic was suggested as a method for formal verification.
Importance: Topic creator, EffectAbstract 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.Software engineering
Go To Statement Considered Harmful
Description: Don't use goto - the beginning of structured programming.On the criteria to be used in decomposing systems into modules
Description: The importance of modularization and information hiding. The Mythical Man-Month: Essays on Software Engineering
Description: Throwing more people at the task will not speed its completion...No Silver Bullet: Essence and Accidents of Software Engineering
Description: We will keep having problems with software...The Cathedral and the Bazaar
Description: Open source methodology.Design Patterns: Elements of Reusable Object Oriented Software
Description: This book was the first to define and list design patternss in computer scienceParallel computing
The Structure of "THE"-Multiprogramming System
Description: The introduction of basic primitives like mutex as the basis of multiprocessing programming.How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs ''
Description: Requirements that guarantee the correct execution of multi process programs were defined.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.Computer networks
Ethernet: Distributed packet switching for local computer networks
Description: The Ethernet protocol.See also