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
- Alan Turing
- Proceedings of the London Mathematical Society, Series 2, 42 (submitted May 28 1936, read November 12 1936), pp 230-265. Errata appeared in Series 2, 43 (1937), pp 544-546.
- Online version
Importance: Topic creator, Breakthrough , Effect
On certain formal properties of grammars
- Noam Chomsky
- Information and Control 2 (1959), 137-167.
Importance: Topic creator, Breakthrough , Effect
Finite automata and their decision problem
- Michael O. Rabin and Dana S. Scott
- IBM J. Research and Development, 3:114--125, 1959.
- Online version
Importance: Topic creator, Breakthrough , Effect, Introduction
Computational complexity theory
On the computational complexity of algorithms
- Juris Hartmanis
- Richard Stearns
- Trans. Amer. Math. Soc. 117 (1965), 285--306.
Importance: Topic creator, Breakthrough, Effect
The complexity of theorem proving procedures
- S. A. Cook
- Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.
Importance: Topic creator, Breakthrough, Effect
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.
Importance: Effect
Computers and Intractability: A Guide to the Theory of NP-Completeness
- Michael R. Garey, David S. Johnson
- Freeman, New York, 1979
- ISBN 0716710455
Importance: Introduction, Effect, Latest and greatest
Theory and Applications of Trapdoor functions
- Andrew Chi-Chih Yao
- Proc. 23rd Symposium on the Foundations of Computer Science (1982), pp. 80--91
Importance: Topic creator, Breakthrough
The Knowledge Complexity of Interactive Proof Systems
- Shafi Goldwasser, Silvio Micali, Charles Rackoff
- SIAM Journal of Computing, 18(1):186-208, February 1989.
Importance: Topic creator, Breakthrough
How to Construct Random Functions
- Oded Goldreich, Shafi Goldwasser, Silvio Micali
- Journal of the ACM, 33(4), 1984, 792-807.
- Online copy (PDF)
Importance: Topic creator, Breakthrough, Latest and greatest
IP = PSPACE
- Adi Shamir
- Journal of the ACM, 39(4):869-877, 1992.
Importance: Breakthrough
Computational Complexity
- C.H. Papadimitriou
- Addison-Wesley, 1994. ISBN 0201530821
Importance: Introduction
Algorithms
A machine program for theorem proving
- M. Davis, G. Logemann, D. Loveland
- Comms. ACM, 5:394--397, 1962.
Importance: Breakthrough, Effect
A Machine-Oriented Logic Based on the Resolution Principle
- J. Alan Robinson
- Comms. ACM, 5:23--41, 1965.
Importance: Topic Creator, Breakthrough, Effect
Optimization by simulated annealing
- Kirkpatrick, S, Gelatt, C, & Vecchi, M
- Science, Number 4598, 13 ,pages 671-680, May 1983.
- Online copy
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
- Thomas H. Cormen
- Charles E. Leiserson
- Ronald L. Rivest
- Clifford Stein
- MIT Press and McGraw-Hill. 2nd Edition, 2001. 1st Edition (with first three authors) published in 1991.
Importance: Introduction, Effect
Algorithmic information theory
A formal theory of inductive inference
- Ray Solomonoff
- Inform. and Control, vol. 7, pp. 1--22, March 1964; pp. 224--254, June 1964.
Importance: Topic creator, Breakthrough, Effect
Algorithmic information theory
- Gregory Chaitin
- IBM Journal of Research and Development 21 (1977), pp. 350-359, 496.
- Online version
Importance: Introduction
Information theory
A mathematical theory of communication
- C.E. Shannon
- Bell System Technical Journal, 27:379--423,623--656, 1948
- Online copy (HTML)
Importance: Topic creator, Breakthrough, Introduction, Effect
Error detecting and error correcting codes
- Richard Hamming
- Bell Systems Technical Journal, vol. 29, pp. 147--160, 1950
- Online copy
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
- David A. Huffman
- Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.
Importance: Effect, Breakthrough
A Universal Algorithm for Sequential Data Compression
- Jacob Ziv
- Abraham Lempel
- IEEE Transactions on Information Theory, Vol. 23, No. 3, pp. 337-343.
- Online copy
Importance: Effect, Breakthrough
Elements of Information Theory
- T. M. Cover
- J. A. Thomas
- Wiley, 1991.
Importance: Effect, Introduction
Operating system
An experimental timesharing system.
- Fernando J. Corbató,M. Merwin-Daggett, and R.C. Daley
- Proceedings of the AFIPS FJCC, pages 335--344, 1962.
- Online copy (HTML)
Importance: Effect
The UNIX Time-Sharing System
- Dennis M. Ritchie and Ken Thompson
- Communications of ACM 7, 7, July 1974.
- Online copy (few formats)
Importance: Effect, Breakthrough
Scheduling Techniques for Concurrent Systems
- J. K. Ousterhout
- Proceedings of Third International Conference on Distributed Computing Systems, 1982, 22—30.
Importance: Effect
Databases
A relational model for large shared data bank
- E. F. Codd
- Communications of the ACM, 13(6):377-- 387, June 1970
Importance: Topic creator, Breakthrough, Effect
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
Importance: Breakthrough, Effect
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)
Importance: Topic creator, Introduction, Effect
Cryptography
Communication Theory of Secrecy Systems
- C.E. Shannon
- " Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28-4, page 656--715, 1949.
- Online copy (HTML)
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
- R. Rivest, A. Shamir, L. Adleman
- Communications of the ACM, Vol. 21 (2), 1978, pages 120--126
- Online copy (HTML)
Importance: Breakthrough, Effect
How to Share a Secret
- Shamir, A
- Comm. Assoc. Comput. Mach., vol.22, no.11, pp.612--613 (Nov. 1979)
Importance: Topic creator, Breakthrough
Artificial intelligence
Computing machinery and intelligence
- Alan Turing
- Mind, 59:433--460, 1950.
- Online copy
Importance: Topic creator, Breakthrough, Effect
A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence
- John McCarthy
- Marvin Minsky
- N. Rochester
- C.E. Shannon
- Online copy
Importance: Effect
Machine learning
Language identification in the limit
- E. M. Gold
- Information and Control, 10:447--474, 1967
Importance: Topic creator, Breakthrough, Effect
On the uniform convergence of relative frequencies of events to their probabilities
- V. Vapnik, A. Chervonenkis
- Theory of Probability and its Applications, 16(2):264--280, 1971
A theory of the learnable
- Leslie Valiant
- Communications of the ACM, 27(11): 1134--1142 (1984)
Importance: Topic creator, Breakthrough, Effect
Learnability and the Vapnik-Chervonenkis dimension
- A. Blumer
- A. Ehrenfeucht
- D. Haussler
- M. K. Warmuth
- Journal of the ACM, 36(4):929--865, 1989.
Importance: Breakthrough, Effect
Cryptographic limitations on learning boolean formulae and finite automata
- M. Kearns
- L. G. Valiant
- In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433--444, New York. ACM.
- Online version(HTML)
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
- C.D. Kuglin and D.C. Hines
- IEEE 1975 Conference on Cybernetics and Society, 1975, New York, p. 163--165, September
Importance: Effect
An Iterative Image RegistrationTechnique with an Application to Stereo Vision
- Lucas, B.D and Kanade, T
- Proceedings of the 7th International Joint Conference on Artificial Intelligence, 674--679,Vancouver, Canada,1981
- Online version
Importance: Effect
The Laplacian Pyramid as a compact image code
- Peter J. Burt and Edward H. Adelson
- IEEE Transactions on Communications, volume = "COM-31,4", p. 532--540,1983.
- Online version
Importance: Effect
Condensation -- conditional density propagation for visual tracking
- M. Isard and A. Blake
- International Journal of Computer Vision 29(1), pp. 5--28, 1998.
- Online version
Importance: Effect
Compilers
YACC: Yet another compiler-compiler
Description: Yacc is a tool that made compiler writing much easier.Importance: Effect
Compilers: Principles, Techniques and Tools
- Alfred V. Aho
- Ravi Sethi
- Jeffrey D. Ullman
- Addison-Wesley, 1986. ISBN 0201100886
Importance: Introduction, Effect
Formal verification
Assigning meanings to programs
- Robert W. Floyd
- Mathematical Aspects of Computer Science, pages 19-32, 1967
Importance: Topic creator, Breakthrough, Effect, Introduction
An axiomatic basis for computer programming
- C. Antony R. Hoare
- Communications of the ACM, 12:576--580, 1969
Importance: Topic creator, Breakthrough, Effect, Introduction
The temporal logic of programs
- Amir Pnueli
- In Proc. 18th IEEE Symposium on Foundation of Computer Science, pages 46--57, 1977.
Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints
- Patrick and Radhia Cousot
- In Proc. 4th ACM Symposium on Principles of Programming Languages, 238--252, 1977
Importance: Topic creator, Effect.
Software engineering
Go To Statement Considered Harmful
- Dijkstra, E. W
- Communications of the ACM, 11(3), 147-148, March 1968
- Online copy (HTML)
Importance: Topic creator, Effect
On the criteria to be used in decomposing systems into modules
- David Parnas
- Communications of the ACM, December:1053-1058, December 1972.
- Online copy (HTML)
Importance: Effect
The Mythical Man-Month: Essays on Software Engineering
- Brooks, Jr., F. P
- Addison Wesley Professional. 2nd Edition 1995.
Importance: Effect
No Silver Bullet: Essence and Accidents of Software Engineering
- Brooks, Jr., F. P
- Computer, 20(4), 10-19, April 1987
- Online copy (HTML)
Importance: Effect
The Cathedral and the Bazaar
- Raymond, E.S
- First Monday, 3, 3 (March 1998)
- Online copy (HTML)
Importance: Effect
Design Patterns: Elements of Reusable Object Oriented Software
- E. Gamma, R. Helm, R. Johnson, J. Vlissides
- Addison-Wesley, Reading, Massachusetts, 1995.
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 ''
- Leslie Lamport
- IEEE Transactions on Computers, volume C-28, number 9, p. 690-691, September, 1979.
Importance: Breakthrough, Effect
LogP: Towards a realistic model of parallel computation
- D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken
- In Proceedings 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May 1993.
- Online version
Importance: Effect
Computer networks
Ethernet: Distributed packet switching for local computer networks
Description: The Ethernet protocol.Importance: Effect, Latest and greatest
See also
- List of publications in Science
- List of publications in Mathematics
- List of publications in statistics
- Notable publications in software engineering