List of important publications in computer science


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

On certain formal properties of grammars

  • Noam Chomsky
  • Information and Control 2 (1959), 137–167.

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

Finite automata and their decision problem

  • Michael O. Rabin and Dana S. Scott
  • IBM J. Research and Development, 3:114–125, 1959.
  • Online version

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

Importance: Topic creator, Breakthrough, Influence, Introduction

Decidability of second order theories and automata on infinite trees

  • Michael O. Rabin
  • Trans. Amer. Math. Soc. 141 (1969) pp. 1-35

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

Computability: An introduction to recursive function theory

  • Nigel J. Cutland
  • Cambridge University Press, 1980, ISBN 0-521-29465-7

Description: A popular textbook.

Importance: Introduction

Introduction to Automata Theory, Languages, and Computation

  • John E. Hopcroft
  • Jeffrey D. Ullman
  • Rajeev Motwani
  • Addison-Wesley, 2001, ISBN 0-201-02988-X

Description: A popular textbook.

Importance: Introduction

Computational complexity theory

Letter from Gödel to von Neumann

  • Kurt Gödel
  • A Letter from Gödel to John von Neumann,20 March 1956
  • Online version

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

Importance: Breakthrough

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

  • Michael O. Rabin
  • Tech. Rep. No. 1, O.N,R., Jerusalem, 1960

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

Importance: Topic creator, Breakthrough

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

On the computational complexity of algorithms

  • Juris Hartmanis
  • Richard Stearns
  • Trans. Amer. Math. Soc. 117 (1965), 285–306.

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

Importance: Topic creator, Breakthrough, Influence

A machine-independent theory of the complexity of recursive functions

  • Manuel Blum
  • Journal of the ACM, 14(2):322 336, 1967.

Description: The Blum axioms.

Importance: Breakthrough, Influence

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

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

Computers and Intractability: A Guide to the Theory of NP-Completeness

  • Michael R. Garey, David S. Johnson
  • Freeman, New York, 1979
  • ISBN 0-7167-1045-5

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

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

How to Construct Random Functions

  • Oded Goldreich, Shafi Goldwasser, Silvio Micali
  • Journal of the ACM, 33(4), 1984, 792–807.
  • Online copy (PDF)

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

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

The Knowledge Complexity of Interactive Proof Systems

  • Shafi Goldwasser, Silvio Micali, Charles Rackoff
  • SIAM Journal of Computing, 18(1):186–208, February 1989.

Description: This paper introduced the concept of zero knowledge.

Importance: Topic creator, Breakthrough

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

IP = PSPACE

  • Adi Shamir
  • Journal of the ACM, 39(4):869–877, 1992.

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

Computational Complexity

  • C.H. Papadimitriou
  • Addison-Wesley, 1994. ISBN 0-201-53082-1

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

Importance: Introduction

Interactive Proofs and the Hardness of Approximating Cliques

  • Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy
  • Journal of the ACM, 43:268–292, 1996.

Probabilistic Checking of Proofs: A New Characterization of NP

  • Sanjeev Arora and Shmuel Safra
  • Journal of the ACM, 45:70–122, 1998.

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

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

  • J. Alan Robinson
  • Communications of the ACM, 5:23–41, 1965.

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

  • L. G. Khachiyan
  • '' Soviet Mathematics Doklady, 20:191--194, 1979.

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

  • Michael O. Rabin
  • Journal of Number Theory 12 (1980), no. 1, pp. 128–138.

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

  • Donald Knuth

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

  • Niklaus Wirth
  • Prentice Hall, 1976, ISBN 0-13-022418-9

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

Importance: Influence

The Design and Analysis of Computer Algorithms

  • Alfred V. Aho
  • John E. Hopcroft
  • Jeffrey D. Ullman
  • Addison-Wesley, 1974, ISBN 0-201-00029-6

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

Importance: Influence, Introduction

How to Solve It By Computer

  • RG Dromey
  • Prentice Hall (1982), ISBN 0-13-434001-9

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

  • Robert Sedgewick
  • Addison-Wesley, 1983, ISBN 0-201-06672-6

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

  • 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.

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

  • Ray Solomonoff
  • Information and Control, vol. 7, pp. 1–22, March 1964; pp. 224–254, June 1964.

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

  • Gregory Chaitin
  • IBM Journal of Research and Development 21 (1977), pp. 350–359, 496.
  • Online version

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

  • C.E. Shannon
  • Bell System Technical Journal, 27:379–423,623–656, 1948
  • Online copy (HTML)

Description: This paper created communication theory and information theory.

Importance: Topic creator, Breakthrough, Introduction, Influence

Error detecting and error correcting codes

  • Richard Hamming
  • Bell Systems Technical Journal, vol. 29, pp. 147–160, 1950
  • Online copy

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

  • David A. Huffman
  • Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp. 1098–1101.
  • Online copy

Description: The Huffman coding.

Importance: Influence, 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

Description: The LZ77 compression algorithm.

Importance: Influence, Breakthrough

Elements of Information Theory

  • Thomas M. Cover
  • Joy A. Thomas
  • Wiley, 1991.

Description: A good and popular introduction to information theory.

Importance: Influence, Introduction

Operating systems

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)

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

  • Peter J. Denning
  • Communications of the ACM, Vol. 11, No. 5, May 1968, pp 323-333
  • Online version(PDF)

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

Importance: Influence, Breakthrough

Virtual Memory, Processes, and Sharing in MULTICS

  • Robert C. Daley, Jack B. Dennis
  • Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 306-312.
  • Online version(PDF)

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

  • Butler W. Lampson
  • Communications of the ACM, 16(10):613-615, October 1973.
  • Online version(PDF)

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

  • Butler W. Lampson,David D. Redell
  • Communications of the ACM, Vol. 23, No. 2, February, 1980, pp. 105-117.
  • Online copy (PDF)

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

  • Marshall Kirk Mckusick, William N. Joy, Samuel J. Leffler, Robert S. Fabry
  • IACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, pp. 181-197.
  • Online copy (PDF)

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

  • Mendel Rosenblum,J. K. Ousterhout
  • ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 26-52.
  • Online version

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

  • Margo Seltzer, Keith Bostic, Marshall Kirk McKusick, Carl Staelin
  • Proceedings of the Winter 1993 USENIX Conference, San Diego, CA, January 1993, 307-326
  • Online version

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

  • G. Ganger, M. McKusick, C. Soules, Y. Patt
  • ACM Transactions on Computer Systems 18, 2. pp 127-153, May 2000
  • Online version

Description: A new way of maintaining filesystem consistency.

Importance:

Databases

A relational model for large shared data banks

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

  • Peter .P-S. Chen
  • ACM Transactions on Database Systems, Vol. 1, No. 1, March 1976, pp. 9–36

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

  • C.E. Shannon
  • " Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28-4, page 656–715, 1949.
  • Online copy (PDF)

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

  • David Kahn
  • New York: The Macmillan Company, 1967, (ISBN 0-684-83130-9).

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

  • Horst Feistel
  • IBM Research Report 2827, March 18, 1970.

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. Fesitel 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 development 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

  • W.Diffie, M.E.Hellman
  • IEEE Transactions on Information Theory, IT-22, 6, 1976, pp. 644–654
  • Online copy (HTML)

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

  • Loren M. Kohnfelder
  • Commun. ACM, vol. 21, no. 2, p. 179, 1978.

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

  • Ralph C. Merkle
  • Commun. ACM, vol. 21, no. 4, pages. 294-299, April 1978.

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

  • R. Rivest, A. Shamir, L. Adleman
  • Communications of the ACM, Vol. 21 (2), 1978, pages 120–126
  • Online copy (HTML)

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

Importance: Breakthrough, Influence

Using encryption for authentication in large networks of computers

  • R M Needham, M D Schroeder
  • Communications of the ACM, Vol 21, No 12 (1978)
  • Online version(PDF)

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

  • Shamir, A.
  • Communications of the ACM, vol. 22, no. 11, pp. 612–613 (November 1979)
  • Online copy (HTML)

Description: A safe method for sharing a secret.

Importance: Topic creator, Breakthrough

Data Security

  • Dorothy E. Denning ,Peter J. Denning
  • Computing Surveys, Vol. 11, No. 3, September 1979, if pp. 227-249.

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

  • Shafi Goldwasser, Silvio Micali
  • Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.
  • Online version (PDF)

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

  • Goldreich, O, Micali, S., Wigderson, A.
  • CRYPTO, LNCS vol 263, pp. 171–185, 1987
  • Online copy(HTML)

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 protocol, which allows individuals communicating over an insecure network to prove their identity to one another in a secure and practical manner.

Importance: Influence

Differential Cryptanalysis of DES-like Cryptosystems

  • Eli Biham,Adi Shamir
  • Journal of Cryptology, Vol. 4 No. 1 1991
  • Online version

Description: The method of Differential cryptanalysis.

Importance: Breakthrough, Influence

A new method for known plaintext attack of FEAL cipher

  • Matsui, M., Yamagishi, A
  • Advances in Cryptology - EUROCRYPT 1992
  • Online version

Description: The method of Linear cryptanalysis.

Importance: Breakthrough, Influence

breaking and fixing the Needham-Schroeder Public-Key protocol using FDR

Description: Used a standard model checker to analyse one of the original cryptographic protocols that had long been believed correct. By exposing what is now the most famous protocol attack using this method, this paper inspired an explosion of interest in the verification and analysis of such protocols that continues to this day.

Importance: Breakthrough, Influence

Differential Collisions in SHA-0

  • Florent Chabaud, Antoine Joux
  • Advances in Cryptology — CRYPTO '98

Description: A method for finding collisions in SHA-0 hash function.

Importance: Breakthrough, Influence

EFF DES cracker

  • Paul Kocher
  • 1998

Description: the EFF DES cracker (nicknamed "Deep Crack") is a machine built by the Electronic Frontier Foundation (EFF) to perform a brute force search of DES's keyspace--that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that DES's key is not long enough to be secure.

Importance: Breakthrough (and break code), Influence

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

A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence

  • John McCarthy
  • Marvin Minsky
  • N. Rochester
  • C.E. Shannon
  • Online copy

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

Importance: Influence

Fuzzy sets

  • Lotfi Zadeh
  • Information and Control, Vol. 8, pp. 338-353. (1965).
  • Online copy

Description: The seminal paper published in 1965 provides details on the mathematics of fuzzy set theory.

Importance: Topic creator, Influence

Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference

  • Judea Pearl
  • ISBN 1-55860-479-0 Publisher: Morgan Kaufmann Pub, 1988

Description: This book introduced Bayesian methods to AI.

Importance: Topic creator, Influence

Artificial Intelligence: A Modern Approach

  • Stuart J. Russell and Peter Norvig
  • Prentice Hall, Englewood Cliffs, New Jersey, 1995, ISBN 0-13-080302-2
  • Textbook's website

Description: The standard textbook in Artificial Intelligence. The book web site lists over 1000 colleges and universities in 93 countries using it.

Importance: Introduction, Influence

The Brain Makers: Genius, Ego & Greed In The Quest For Machines That Think''

  • HP Newquist
  • Macmillan/Sams, 1994, ISBN 0-672-30412-0

Description: The definitive book on the business of creating artificial intellligence.

Importance:

Machine learning

Language identification in the limit

Description: This paper created Algorithmic learning theory.

Importance: Topic creator, Breakthrough, Influence

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

Description: Computational learning theory, VC theory, statistical uniform convergence and the VC dimension.

Importance: Breakthrough, Influence

A theory of the learnable

  • Leslie Valiant
  • Communications of the ACM, 27(11):1134–1142 (1984)
  • Online copy (PDF)

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

Importance: Topic creator, Breakthrough, Influence

Learning representations by back-propagating errors

  • David E. Rumelhart, Geoffrey E. Hinton and Ronald J. Williams
  • Nature, 323, 533--536, 1986

Description: Development of Backpropagation algorithm for artificial neural networks. Note that the algorithm was first described by Paul Werbos in 1974.

Importance: Influence

Induction of Decision Trees

Description: Decision Trees are a common learning algorithm and a decision representation tool. Development of decision trees was done by many researchers in many areas, even before this paper. Though this paper is one of the most influential in the field.

Importance: Influence

Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm

Description: One of the papers that started the field of on-line learning. In this learning setting, a learner receives a sequence of examples, making predictions after each one, and receiving feedback after each prediction. Research in this area is remarkable because (1) the algorithms and proofs tend to be very simple and beautiful, and (2) the model makes no statistical assumptions about the data. In other words, the data need not be random (as in nearly all other learning models), but can be chosen arbitrarily by "nature" or even an adversary. Specifically, this paper introduced the Winnow (algorithm) algorithm.

Importance: Influence

Learning to predict by the method of temporal differences

  • Richard S. Sutton
  • Machine Learning 3(1): 9-44
  • Online copy

Description: The temporal differences method for reinforcement learning.

Importance: Influence

Learnability and the Vapnik-Chervonenkis dimension

  • A. Blumer
  • A. Ehrenfeucht
  • D. Haussler
  • M. K. Warmuth
  • Journal of the ACM, 36(4):929–965, 1989.

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

Importance: Breakthrough, Influence

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)

Description: Proving negative results for PAC learning.

Importance: Influence

The strength of weak learnability

Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework. The proof was done by introducing the boosting method.

Learning in the presence of malicious errors

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

Importance: Breakthrough, Influence

A training algorithm for optimum margin classifiers

  • Bernhard E. Boser
  • Isabelle M. Guyon
  • Vladimir N. Vapnik
  • Proceedings of the Fifth Annual Workshop on Computational Learning Theory 5 144-152, Pittsburgh (1992).
  • Online version(HTML)

Description: This paper presented support vector machines, a practical and popular machine learning algorithm. Support vector machines utilize the kernel trick, a generally used method.

Importance: Breakthrough, Influence

Knowledge-based analysis of microarray gene expression data by using support vector machines

  • MP Brown
  • WN Grundy
  • D Lin
  • Nello Cristianini
  • CW Sugnet
  • TS Furey
  • M Ares Jr,
  • David Haussler
  • PNAS, 2000 Jan 4;97(1):262-7 (http://www.pnas.org/cgi/content/abstract/97/1/262)

Description: The first application of supervised learning to gene expression data, in particular Support Vector Machines. The method is now standard, and the paper one of the most cited in the area.

Importance: Breakthrough, Influence

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, pp. 163–165, September

Description: A correlation method based upon the inverse Fourier transform

Importance: Influence

Determining Optical Flow

  • B.K.P. Horn and B.G. Schunck
  • Artificial Intelligence, Volume 17, 185–203, 1981

Description: A method for estimating the image motion of world points between 2 frames of a video sequence

Importance: Influence

An Iterative Image Registration Technique 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

Description: This paper provides efficient technique for image registration

Importance: Influence

The Laplacian Pyramid as a compact image code

  • Peter J. Burt and Edward H. Adelson
  • IEEE Transactions on Communications, volume = "COM-31,4", pp. 532–540, 1983.
  • Online version

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

Importance: Influence

Snakes: Active contour models

  • Michael Kass, Andrew Witkin, and Demetri Terzopoulos
  • International Journal of Computer Vision, 1(4):321–331, 1988. (Marr Prize Special Issue)
  • Online version

Description: An interactive variational technique for image segmentation and visual tracking

Importance: Influence, topic creator

Condensation -- conditional density propagation for visual tracking

  • M. Isard and A. Blake
  • International Journal of Computer Vision, 29(1):5–28, 1998.
  • Online version

Description: A technique for visual tracking

Importance: Influence

Compilers

On the translation of languages from left to right

  • D. E. Knuth
  • Information and Control 8 (1965), 607-639.

Description: Bottom up parsing for deterministic context-free languages from which later the LALR approach of Yacc developed.

Importance: Breakthrough, Influence

Semantics of Context-Free Languages.

  • D.E. Knuth
  • Math. Systems Theory 2:2 (1968), 127-145.

Description: About grammar attribution, the base for yacc's s-attributed and zyacc's LR-attributed approach.

Importance: Breakthrough, Influence

A program data flow analysis procedure

  • F.E. Allen, J. Cocke
  • Commun. ACM, 19, 137--147.

Description: From the abstract: "The global data relationships in a program can be exposed and codified by the static analysis methods described in this paper. A procedure is given which determines all the definitions which can possibly reach each node of the control flow graph of the program and all the definitions that are live on each edge of the graph."

Importance: Breakthrough, Influence

YACC: Yet another compiler-compiler

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

Importance: Influence

gprof: A Call Graph Execution Profiler

  • Susan L. Graham, Peter B. Kessler, Marshall Kirk McKusick
  • Proceedings of the ACM SIGPLAN 1982 Symposium on Compiler Construction,

SIGPLAN Notices 17, 6, Boston, MA. June 1982.

Description: The gprof profiler

Compilers: Principles, Techniques and Tools

  • Alfred V. Aho
  • Ravi Sethi
  • Jeffrey D. Ullman
  • Monica Lam
  • Addison-Wesley, 1986. ISBN 0-201-10088-6

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

Formal verification

On computable numbers, with an application to the Entscheidungsproblem

Description: In his paper on the Entscheidungsproblem, Alan Turing introduces the idea of a Turing Machine which he uses to prove the undecidability of the Halting Problem and (consequently) the undecidability of first-order logic (because if FOL were decidable then the Halting Problem would be decidable). This is the first of a series of so-called "negative" results formally proving that the set of all possible programs does not include a program V that is able to decide the formal correctness of (i.e. formally verify) any given program P - any attempt to write a "program verifier" V (always returning a yes/no result in a finite time) is therefore futile because the problem is provably impossible. However, it is still possible to write a program V' (returning a yes/no/maybe result) that is able to formally verify some programs but not all programs, even if it is not possible to define in advance exactly for which programs V' will be able to return "yes/no" rather than "maybe".

Importance: Breakthrough

Assigning Meaning to Programs

  • Robert Floyd
  • Mathematical Aspects of Computer Science, pages 19–32, 1967
  • scanned copy (bad quality, taken from External Link section at Robert Floyd)

Description: Robert Floyd's landmark paper Assigning Meaning to Programs introduces the method of inductive assertions and describes how a program annotated with first-order assertions may be shown to satisfy a pre- and post-condition specification - the paper also introduces the concepts of loop invariant and verification condition.

Importance: Topic creator

An Axiomatic Basis for Computer Programming

Description: Tony Hoare's paper An Axiomatic Basis for Computer Programming describes a set of inference (i.e. formal proof) rules for fragments of an Algol-like programming language described in terms of (what are now called) Hoare-triples.

Importance: Breakthrough

Guarded Commands, Nondeterminacy and Formal Derivation of Programs

  • Edsger W. Dijkstra
  • 1975

Description: Edsger Dijkstra's paper Guarded Commands, Nondeterminacy and Formal Derivation of Programs (expanded by his 1976 postgraduate-level textbook A Discipline of Programming) proposes that, instead of formally verifying a program after it has been written (i.e. post facto), programs and their formal proofs should be developed hand-in-hand (using predicate transformers to progressively refine weakest pre-conditions), a method known as program (or formal) refinement (or derivation), or sometimes "correctness-by-construction".

Importance: Topic creator

Proving Assertions about Parallel Programs

  • Edward A. Ashcroft
  • J. Comput. Syst. Sci. 10(1): 110-135 (1975)

Description: The paper that introduced invariance proofs of concurrent programs.

Importance: Breakthrough

An Axiomatic Proof Technique for Parallel Programs I

  • Susan S. Owicki, David Gries
  • Acta Inf. 6: 319-340 (1976)

Description: In this paper, along with the same authors paper "Verifying Properties of Parallel Programs: An Axiomatic Approach. Commun. ACM 19(5): 279-285 (1976)", the axiomatic approach to parallel programs verification was presented.

Importance: Breakthrough

A Discipline of Programming

  • Edsger W. Dijkstra
  • 1976

Description: Edsger Dijkstra's classic postgraduate-level textbook A Discipline of Programming extends his earlier paper Guarded Commands, Nondeterminacy and Formal Derivation of Programs and firmly establishes the principle of formally deriving programs (and their proofs) from their specification.

Importance: Influence

Denotational Semantics

  • Joe Stoy
  • 1977

Description: Joe Stoy's Denotational Semantics is the first (postgraduate level) book-length exposition of the mathematical (or functional) approach to the formal semantics of programming languages (in contrast to the operational and algebraic approaches).

Importance: Introduction

The Temporal Logic of Programs

  • Amir Pnueli
  • In Proc. 18th IEEE Symposium on Foundation of Computer Science, pages 46--57, 1977.

Description: The use of temporal logic was suggested as a method for formal verification.

Importance: Topic creator, Impact

Time, clocks, and the ordering of events in a distributed system

Description: The ordering of events is critical to consistency and correctness of many algorithms used in distributed computer systems. This paper discusses how such ordering can be managed consistently and introduces a set of rules for managing virtual time in such systems. These rules are the basis for many subsequent algorithms for ordering events in distributed system.

Importance: Influence

Communicating Sequential Processes (1978)

  • C.A.R. Hoare
  • 1978

Description: Tony Hoare's (original) Communicating Sequential Processes (CSP) paper introduces the idea of concurrent processes (i.e. programs) that do not share variables but instead cooperate solely by exchanging synchronous messages.

Importance: Influence

A Calculus of Communicating Systems

  • Robin Milner
  • 1980

Description: Robin Milner's A Calculus of Communicating Systems (CCS) paper describes a process algebra permitting systems of concurrent processes to be reasoned about formally, something which has not been possible for earlier models of concurrency (semaphores, critical sections, original CSP).

Importance: Breakthrough

Software Development: A Rigorous Approach

  • Cliff Jones
  • 1980

Description: Cliff Jones' textbook Software Development: A Rigorous Approach is the first full-length exposition of the Vienna Development Method (VDM), which has evolved (principally) at IBM's Vienna research lab over the previous decade and which combines the idea of program refinement as per Dijkstra with that of data refinement (or reification) whereby algebraically-defined abstract data types are formally transformed into progressively more "concrete" representations.

Importance: Influence

The Science of Programming

  • David Gries
  • 1981

Description: David Gries' textbook The Science of Programming describes Dijkstra's weakest precondition method of formal program derivation, except in a very much more accessible manner than Dijkstra's earlier A Discipline of Programming.

Importance: Introduction

Communicating Sequential Processes (1985)

  • C.A.R. Hoare
  • 1985

Description: Tony Hoare's Communicating Sequential Processes (CSP) textbook (currently the third most cited computer science reference of all time) presents an updated CSP model in which cooperating processes do not even have program variables and which, like CCS, permits systems of processes to be reasoned about formally.

Importance: Influence

The Z Notation: A Reference Manual

Description: Mike Spivey's classic textbook The Z Notation: A Reference Manual summarises the formal specification language Z which, although originated by Jean-Raymond Abrial, has evolved (principally) at Oxford University over the previous decade (Z may ultimately become by far the most widely used language of its kind).

Importance: Influence

Communication and Concurrency

  • Robin Milner
  • Prentice-Hall International, 1989

Description: Robin Milner's textbook Communication and Concurrency is a more accessible, although still technically advanced, exposition of his earlier CCS work.

Importance: Introduction

Programming from Specifications

Description: Carroll Morgan's Programming from Specifications describes mature methods for the formal derivation of algorithms (along with their proofs) from specifications.

Importance: Introduction, influence.

The B-Book: Assigning Programs to Meanings

  • Jean-Raymond Abrial
  • 1996

Description: Jean-Raymond Abrial's The B-Book: Assigning Programs to Meanings (note the nod to Floyd's work!) is a long-awaited textbook description of his B method for the formal derivation of algorithms (along with their proofs) from specifications.

Importance: Influence

The Theory and Practice of Concurrency

Description: Bill Roscoe's The Theory and Practice of Concurrency is a postgraduate-level textbook describing CSP (including mutually consistent operational, denotational and algebraic semantics) after many years of evolution at Oxford University.

Importance: Introduction

On a Method of Multiprogramming

  • Wim Feijen and Netty van Gasteren
  • 1999

Description: An extension of Dijkstra's method of deriving sequential programs to the concurrent world.

Importance: Introduction

Software engineering

Software engineering: Report of a conference sponsored by the NATO Science Committee

  • Peter Naur, Brian Randell (eds.)
  • Garmisch, Germany, 7–11 October 1968, Brussels, Scientific Affairs Division, NATO (1969) 231pp.
  • Online copy (PDF)

Description: Conference of leading figures in software field circa 1968

Importance: Defined the field of Software engineering

Go To Statement Considered Harmful

  • Dijkstra, E. W.
  • Communications of the ACM, 11(3):147–148, March 1968
  • Online copy (HTML)

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

Importance: Topic creator, Influence

On the criteria to be used in decomposing systems into modules

  • David Parnas
  • Communications of the ACM, Volume 15, Issue 12:1053–1058, December 1972.
  • Online copy (HTML)

Description: The importance of modularization and information hiding. Note that information hiding was first presented in a different paper of the same author - "Information Distributions Aspects of Design Methodology", Proceedings of IFIP Congress '71, 1971, Booklet TA-3, pp. 26-30

Importance: Breakthrough , Influence

Hierarchical Program Structures

  • Ole-Johan Dahl, C. A. R. Hoare
  • in Dahl, Dijkstra and Hoare, Structured Programming, Academic Press, London and New York, pp. 175-220, 1972.

Description: The beginning of Object-oriented programming. This paper argued that programs should be decomposed to independent components with small and simple interfaces. They also argued that objects should have both data and related methods.

Importance: Breakthrough , Influence

A technique for software module specification with examples

Description: software specification.

Importance: Influence

The Emperor's Old Clothes

  • C.A.R. Hoare
  • Communications of the ACM, Vol. 24, No. 2, February 1981, pp. 75-83.
  • Archived copy (PDF)

Description: A lovely story of how large software projects can go right, and then wrong, and then right again, told with humility and humor. Illustrates the "second-system effect" and the importance of simplicity.

Importance: Influence

The Mythical Man-Month: Essays on Software Engineering

  • Brooks, Jr., F. P.
  • Addison Wesley Professional. 2nd edition, 1995.

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

Importance: Influence

No Silver Bullet: Essence and Accidents of Software Engineering

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

Importance: Influence

The Cathedral and the Bazaar

Description: Open source methodology.

Importance: Influence

Design Patterns: Elements of Reusable Object Oriented Software

  • E. Gamma, R. Helm, R. Johnson, J. Vlissides
  • Addison-Wesley, Reading, Massachusetts, 1995.

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

Importance: Topic creator, Influence

Statecharts: A Visual Formalism For Complex Systems

  • David Harel
  • D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8:231--274, 1987
  • Online version

Description: Statecharts are a visual modeling method. They are an extension of state machine that might be exponentially more efficient. Therefore, statcharts enable formal modeling of applications that were too complex before. Statecharts are part of the UML diagrams.

Importance: Influence

Parallel computing

The Structure of "THE"-Multiprogramming System

  • Edsger W. Dijkstra
  • Communication of the ACM, Vol. 11, No. 5 May 1968, pp. 345–346
  • Online copy (HTML)

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

Importance: Breakthrough, Influence

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

  • Leslie Lamport
  • IEEE Transactions on Computers, volume C-28, number 9, pp. 690–691, September 1979.

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

Importance: Breakthrough, Influence

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

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

Computer networks

A Protocol for Packet Network Interconnection

  • Vint Cerf, Bob Kahn
  • IEEE Transactions on Communication Technology, 1974
  • Online copy (PDF)

Description: Packet Network Interconnection.

Importance: Influence

Ethernet: Distributed packet switching for local computer networks

  • R.M. Metcalfe, D.R. Boggs
  • Communications of the ACM 19, 7 (July 1976), 395–404
  • Online copy (HTML)

Description: The Ethernet protocol.

Importance: Influence, Latest and greatest

End-To-End Arguments in System Design

  • J.H. Saltzer, D.P. Reed, D.D. Clark
  • Proceedings of the 2nd International Conference on Distributed Systems, 509-512, April 1981.
  • Online copy (PDF)

Description: Many of critical design problems in networking and systems focus on the right "layer" in which to provide particular functionailty. The basic debate is whether the core system or network should provide the functionaility, or whether it should be left to the end-system or application to implement using more basic primitives provided in the core network or base system. This paper highlights these issues and argues for one side. The argument has occurred over and over again in various aspects of system design and it is important to understand the basic philosopy of both sides of the debate.

Importance: Influence

Internet Protocol

  • RFC 791, Information Sciences Institute, Marina Del Rey, California, September 1981
  • Online copy (HTML)

Description: The Internet Protocol (IP).This paper describes the he Internet Protocol (IP), a fundamental protocol that drive the Internet. Required (but quite technical) reading for anyone who wants to understand networking.

Importance: influence

Transmission Control Protocol

  • RFC 793, Information Sciences Institute, Marina del Rey, California, September 1981.
  • Online copy (HTML)

Description: The Transmission Control Protocol (TCP).

Importance: Influence

http://citeseer.ist.psu.edu/birrell84implementing.html

Implementing Remote Procedure Calls

  • Andrew D. Birrell, Bruce Jay Nelson
  • ACM Transactions on Computer Systems, Vol. 2, No. 1, February 1984, pp. 39-59.
  • Online copy

Description: This is the seminal paper on Remote Procedure Call, which provides a higher-level mechanism for communicating between the components of a distributed system.

Importance: Influence

A Dynamic Network Architecture

  • Sean W. O'Malley, Larry L. Peterson
  • ACM Transactions on Computer Systems, 10(2), May 1992
  • Online copy

Description: Network software in distributed systems.

Importance: Influence

Distributed computing

The Byzantine Generals Problem

  • Leslie Lamport, Robert Shostak, Marshall Pease
  • Advances in Ultra-Dependable Distributed Systems, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press
  • Online version

Description: Impossibility result for distributed computing, see Byzantine failure.

Importance: Influence, Breakthrough

Impossibility of Distributed Consensus with One Faulty process

Description: Impossibility to achieve consensus in asynchronous systems if one process is faulty .

Importance: Influence, Breakthrough

Nancy A. Lynch and Mark R. Tuttle. An introduction to input/output automata. CWI-Quarterly, 2(3):219-246, September 1989. Also available as MIT Technical Memo MIT/LCS/TM-373. (ps, pdf)

An introduction to input/output automata

  • Nancy Lynch, Mark R. Tuttle
  • CWI-Quarterly, 2(3):219-246, September 1989. Also available as MIT Technical Memo MIT/LCS/TM-373.
  • Online version

Description: input/output automata

Importance:

The Topological Structure of Asynchronous Computability

Description: The paper improved the understanding of asynchronous wait-free deterministic computation in the basic shared memory model. The authors transform a dynamic model into a static one by associating computational tasks with simplicial complexes and translating the question of existence of a wait-free protocol into (distinct but related) topological questions about the complexes. The paper won the Gödel Prize at 2004 with "Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge".

Importance: Influence, Breakthrough

Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge

  • Michael Saks, Fotios Zaharoglou
  • SIAM J. on Computing, Vol. 29 (2000), 1449-1483.

Description: The paper improved the understanding of asynchronous wait-free deterministic computation in the basic shared memory model. These papers transforming a dynamic model into a static one by associating computational tasks with simplicial complexes and translating the question of existence of a wait-free protocol into (distinct but related) topological questions about the complexes. The paper won the Gödel Prize at 2004 with "The Topological Structure of Asynchronous Computability".

Importance: Influence, Breakthrough

Internet

As We May Think

Description: The paper argued that as humans turned from war, scientific efforts should shift from increasing physical abilities to making all previous collected human knowledge more accessible. As We May Think predicted many kinds of technology invented after its publication, including hypertext, personal computers, the Internet, the World Wide Web, speech recognition, and online encyclopedias such as Wikipedia

Importance: Influence

Grapevine: An Exercise in Distributed Computing

  • Andrew D. Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder
  • Communications of the ACM\fR, Vol. 25, No. 4, April 1982, pp. 260-274.
  • Online version(PDF)

Description: The Grapevine system. The paper describes one of the first attempts to build a large-scale distributed system (the Xerox mail system). Exposes many interesting problems related to distributed systems and describes how they were solved in this particular system.

Importance: Influence

The Design Philosophy of the DARPA Internet Protocols

Description: The DARPA Internet Protocols (TCP/IP).

Importance: Influence

The Anatomy of a Large-Scale Hypertextual Web Search Engine

  • Sergey Brin and Lawrence Page
  • Computer Networks and ISDN Systems,volume 30,number = 1-7,pages = 107-117, 1998.

Description: The Anatomy of a Search Engine, known today as Google.

Importance: Influence

Programming languages

The FORTRAN Automatic Coding System

  • John Backus et al.
  • Proceedings of the WJCC (Western Joint Computer Conference), Los Angeles, California, February, 1957.
  • Online version(PDF)

Description: This paper describes the design and implementation of the first FORTRAN compiler by the IBM team. Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing.

Importance: Breakthrough, Influence

ALGOL 60

  • B. Randell and L.J. Russell, ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer. Academic Press, 1964. The design of the Whetstone Compiler. One of the early published descriptions of implementing a compiler. See the related papers: Whetstone Algol Revisited, and The Whetstone KDF9 Algol Translator by B. Randell
  • Edsger W. Dijkstra, Algol 60 translation: an algol 60 translator for the x1 and making a translator for algol 60, report MR 35/61. Mathematisch Centrum, Amsterdam, 1961. 1

Description: Algol 60 introduced block structure.

Importance: Influence

Simula 67

Description: Simula 67 introduced object orientation to the field of programming languages

Importance: Influence

Computer architecture

Colossus computer

  • T. H. Flowers
  • Annals of the History of Computing, Vol. 5 (No. 3), 1983, pp. 239–252.
  • The Design of Colossus

Description: The Colossus machines were early computing devices used by British codebreakers to read encrypted German messages during World War II. Colossus was an early binary electronic digital computer. The design of Colossus was later described in the referenced paper.

Importance: Topic creator, Breakthrough , Influence

First Draft of a Report on the EDVAC

Description: It contains the first published description of the logical design of a computer using the stored-program concept, which has come to be known as the von Neumann architecture.

Importance: Topic creator, Breakthrough , Influence

Architecture of the IBM System/360

Description: The IBM System/360 (S/360) is a mainframe computer system family announced by IBM on April 7, 1964. It was the first family of computers making a clear distinction between architecture and implementation.

Importance: Breakthrough , Influence

The case for the reduced instruction set computer

  • DA Patterson,DR Ditzel
  • Computer ArchitectureNews, vol. 8, no. 6, October 1980, pp 25-33.
  • Online version(PDF)

Description: The reduced instruction set computer( RISC) CPU design philosophy. The RISC is a CPU design philosophy that favors a reduced instruction set as well as a simpler set of instructions.

Importance: Breakthrough , Influence

Comments on "the Case for the Reduced Instruction Set Computer"

Description:

Importance:

The CRAY-1 Computer System

  • DW Clark, WD Strecker
  • Communications of the ACM, January 1978, volume 21, number 1, pages 63-72.
  • Online version(PDF)

Description: The Cray-1 was a supercomputer designed by a team including Seymour Cray for Cray Research. The first Cray-1 system was installed at Los Alamos National Laboratory in 1976, and it went on to become one of the best known and most successful supercomputers in history.

Importance:

Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities

  • Gene Amdahl
  • AFIPS 1967 Spring Joint Computer Conference, Atlantic City, N.J.
  • Online version(PDF)

Description: The Amdahl's Law.

Importance:

A Case for Redundant Arrays of Inexpensive Disks (RAID)

  • David A. Patterson, Garth Gibson, Randy H. Katz
  • In International Conference on Management of Data, pages 109--116, 1988.
  • Online version(PDF)

Description: This paper discusses the concept of RAID disks, outlines the different levels of RAID, and the benefits of each level. It is a good paper for discussing issues of reliability and fault tolerance of computer systems, and the cost of providing such fault-tolerance.

Importance: Influence

Computer graphics

Elastically deformable models

  • D. Terzopoulos, J. Platt, A. Barr, K. Fleischer
  • Computer Graphics, 21(4), 1987, 205-214, Proc. ACM

SIGGRAPH'87 Conference, Anaheim, CA, July, 1987.

Description: The Academy of Motion Picture Arts and Sciences cited this paper as a "milestone in computer graphics".

Importance: Influence

History of computation

The Computer from Pascal to von Neumann

  • Herman H. Goldstine
  • Princton University Press, 1972, ISBN 0-691-08104-2

Description: Perhaps the first book on the history of computation.

Importance:

A History of Computing in the Twentieth Century

edited by:

  • Nicholas Metropolis
  • J. Howlett
  • Gian-Carlo Rota
  • Academic Press, 1980, ISBN 0-12-491650-3

Description: Several chapters by pioneers of computing.

Importance:

Computer science humor

The Complexity of Songs

  • Donald Knuth
  • Knuth, D. The Complexity of Songs, SIGACT News, Summer 1977, 17-24.
  • Knuth, D. The Complexity of Songs, Communications of the ACM, 1984, 27 (4) pp. 345--348.

Description: The article capitalizes on the tendency of popular songs to evolve from long and content-rich ballads to highly repetitive "content-free" texts.

Importance: humor is considered healthy

On Folk Theorems

  • David Harel, "On Folk Theorems", Comm. Assoc. Comput. Mach. 23 (1980), 379-389
  • Online version(PDF)

Description: A paper that is both serious and funny about "the things we all know".

Importance: Makes you wonder how we know what we all know.

How to prove it

  • Dana Angluin
  • Sigact News, Winter-Spring 1983, Volume 15 #1

Description: Angluin presents some common proof techniques that should become less common.

Importance: When treated seriously, highly pedagogic

See also

  • List of publications in science
  • Notable publications in software engineering
  • List of open problems in computer science
  • DBLP (Digital Bibliography & Library Project in computer science)
  • The Collection of Computer Science Bibliographies

Awards for publications (and not for general contribution):

  • Dijkstra Prize, a prize for outstanding papers on the principles of distributed computing
  • Gödel Prize, a prize for outstanding papers in theoretical computer science
  • Paris Kanellakis Award, a prize given to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing.

Academic Search Engines

Further reading

  • Laplante, Phillip (ed). (1996) Great Papers in Computer Science. New York: IEEE Press. ISBN 031406365X.
  • Randell, Brian (ed). (1982). The Origins of Digital Computers: Selected Papers. 3rd ed. Berlin: Springer-Verlag. ISBN 0387113193.

he:פרסומים חשובים במדעי המחשב