List of publications in computer science

Template:List of publications intro
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 230265. Errata appeared in Series 2, 43 (1937), pp 544546.
 Online version (MS IExplorer only) (http://www.abelard.org/turpap2/tp2ie.asp)
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), 137167.
Description: The Chomsky hierarchy, a containment hierarchy of classes of formal grammars that generate formal languages was introduced.
Importance: Topic creator, Breakthrough, Influence
Finite automata and their decision problem
 Michael O. Rabin and Dana S. Scott
 IBM J. Research and Development, 3:114125, 1959.
 Online version (http://domino.research.ibm.com/tchjr/journalindex.nsf/0/cdf6b2949432156385256bfa00683d63?OpenDocument)
Description: Mathematical treatment of automata, proof of core properties, and definition of nondeterministic finite automaton
Importance: Topic creator, Breakthrough, Influence, Introduction
 Mehryar Mohri
 FiniteState Transducers in Language and Speech Processing. Computational Linguistics 23(2): 269311 (1997).
 online version (http://www.cs.nyu.edu/~mohri/postscript/cl1.ps)
Description: Mathematical treatment of finitestate transducers, definition and proof of core properties.
Computational complexity theory
On the computational complexity of algorithms
 Juris Hartmanis
 Richard Stearns
 Trans. Amer. Math. Soc. 117 (1965), 285306.
Description: This paper gave computational complexity its name and seed.
Importance: Topic creator, Breakthrough, Influence
The complexity of theorem proving procedures
 S. A. Cook
 Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151158.
Description: This paper introduced the concept of NPCompleteness and proved that Boolean satisfiability problem(SAT) is NPComplete.
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 85103. Plenum Press, New York, NY, 1972.
Description: This paper showed that 21 different problems are NPComplete and showed the importance of the concept.
Importance: Influence
Computers and Intractability: A Guide to the Theory of NPCompleteness
 Michael R. Garey, David S. Johnson
 Freeman, New York, 1979
 ISBN 0716710455
Description: The main importance of this book is due to its extensive list of more than 300 NPComplete problems. This list became a common reference and definition. It is important to note that though the book was published only few years after the concept was defined such an extensive list was found.
Importance: Introduction, Influence, Latest and greatest
Theory and Applications of Trapdoor functions
 Andrew ChiChih Yao
 Proc. 23rd Symposium on the Foundations of Computer Science (1982), pp. 8091
Description: This paper introduced the concept of Trapdoor functions and described some of its application, like in cryptography.
Importance: Topic creator, Breakthrough
The Knowledge Complexity of Interactive Proof Systems
 Shafi Goldwasser, Silvio Micali, Charles Rackoff
 SIAM Journal of Computing, 18(1):186208, February 1989.
Description: This paper introduced the concept of zero knowledge.
Importance: Topic creator, Breakthrough
How to Construct Random Functions
 Oded Goldreich, Shafi Goldwasser, Silvio Micali
 Journal of the ACM, 33(4), 1984, 792807.
 Online copy (PDF) (http://theory.lcs.mit.edu/~cis/pubs/shafi/1986jacm.pdf)
Description: This paper showed that the existence of one way functions leads to computational randomness.
Importance: Topic creator, Breakthrough, Latest and greatest, Influence
IP = PSPACE
 Adi Shamir
 Journal of the ACM, 39(4):869877, 1992.
Description: IP is a complexity class whose characterization is quite different from the usual time/space bounded computational classes. In this paper Shamir showed the IP = PSPACE, hence each problem in one complexity class is solvable in the other.
Importance: Breakthrough
Computational Complexity
 C.H. Papadimitriou
 AddisonWesley, 1994. ISBN 0201530821
Description: This book provides a very good introduction to Computational Complexity
Importance: Introduction
Algorithms
A machine program for theorem proving
 M. Davis, G. Logemann, D. Loveland
 Comms. ACM, 5:394397, 1962.
Description: The DLL algorithm. The basic algorithm for SAT and other NPComplete problems.
Importance: Breakthrough, Influence
A MachineOriented Logic Based on the Resolution Principle
 J. Alan Robinson
 Comms. ACM, 5:2341, 1965.
Description: First description of resolution and unification used in theorem proving; used in Prolog & logic programming.
Importance: Topic Creator, Breakthrough, Influence
Optimization by simulated annealing
 Kirkpatrick, S., Gelatt, C., & Vecchi, M.
 Science, Number 4598, 13,pages 671680, May 1983.
 Online copy (http://citeseer.ist.psu.edu/kirkpatrick83optimization.html)
Description: A very common heuristic for NPComplete problems.
Importance: Influence
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: Influence
Introduction to Algorithms
 Thomas H. Cormen
 Charles E. Leiserson
 Ronald L. Rivest
 Clifford Stein
 MIT Press and McGrawHill. 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
 Inform. and Control, vol. 7, pp. 122, March 1964; pp. 224254, 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. 350359, 496.
 Online version (http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ibm.pdf)
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:379423,623656, 1948
 Online copy (HTML) (http://cm.belllabs.com/cm/ms/what/shannonday/paper.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. 147160, 1950
 Online copy (http://www.engelschall.com/~sb/hamming/?page=1)
Description: In this paper, Hamming introduced the idea of errorcorrecting 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. 10981101.
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. 337343.
 Online copy (http://citeseer.nj.nec.com/ziv77universal.html)
Description: The LZ77 compression algorithm.
Importance: Influence, Breakthrough
Elements of Information Theory
 T. M. Cover
 J. A. Thomas
 Wiley, 1991.
Description: A good and popular introduction to information theory.
Importance: Influence, Introduction
Operating system
An experimental timesharing system.
 Fernando J. Corbató,M. MerwinDaggett, and R.C. Daley
 Proceedings of the AFIPS FJCC, pages 335344, 1962.
 Online copy (HTML) (http://larchwww.lcs.mit.edu:8001/~corbato/sjcc62/)
Description: This paper discuss timesharing as a method of sharing computer resource. This idea changed the interaction with computer systems.
Importance: Influence
The UNIX TimeSharing System
 Dennis M. Ritchie and Ken Thompson
 Communications of ACM 7, 7, July 1974.
 Online copy (few formats) (http://citeseer.ist.psu.edu/ritchie74unix.html)
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
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
Databases
A relational model for large shared data bank
 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
The Entity Relationship Model  Towards a Unified View of Data
 P.PS. Chen
 ACM Transactions on Database Systems, Vol. 1, No. 1, March 1976, pp. 936
Description: This paper introduced the Entityrelationship diagram(ERD) method of database design.
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 207216, Washington, D.C., May 1993
 Online copy (HTML) (http://citeseer.nj.nec.com/agrawal93mining.html)
Description: Association rules, a very common method for data mining.
Importance: Topic creator, Introduction, Influence is
Cryptography
Communication Theory of Secrecy Systems
 C.E. Shannon
 " Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.284, page 656715, 1949.
 Online copy (PDF) (http://www.cs.ucla.edu/~jkong/research/security/shannon1949.pdf)
Description: Information theory based analysis of cryptography.
Importance: Breakthrough, Introduction, Influence
New directions in cryptography
 W.Diffie, M.E.Hellman
 IEEE Trans. Inform. Theory, IT22, 6, 1976, pp.644654
 Online copy (HTML) (http://citeseer.nj.nec.com/340126.html)
Description: This paper suggested public key cryptography and presented DiffieHellman key exchange.
Importance: Topic creator, Breakthrough, Introduction, Influence, 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 120126
 Online copy (HTML) (http://citeseer.nj.nec.com/rivest78method.html)
Description: The RSA encryption method. The first public key encryption method.
Importance: Breakthrough, Influence
How to Share a Secret
 Shamir, A.
 Comm. Assoc. Comput. Mach., vol.22, no.11, pp.612613 (Nov. 1979)
 Online copy (HTML) (http://szabo.best.vwh.net/secret.html)
Description: A safe method for sharing a secret.
Importance: Topic creator, Breakthrough
Proxy Blind Signature Scheme
 Awasthi, Amit K., Lal, S.
 Transaction on Cryptology, vol.2, no.1, pp.511 (Jan 2005)
 Extended Version(HTML) (http://www.gfcr.org/toc/TOCJAN0501.html)
Description: This is first scheme to introduce concept of branch banking.
Importance: Topic creator
Artificial intelligence
Computing machinery and intelligence
 Alan Turing
 Mind, 59:433460, 1950.
 Online copy (http://www.abelard.org/turpap/turpap.htm)
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
Probabalistic networks (?)
 Judea Pearl
 Publisher?, 1988.
Description: This book introduced Bayesian methods to AI.
Importance: Topic creator, Influence
A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence
 John McCarthy
 Marvin Minsky
 N. Rochester
 C.E. Shannon
 Online copy (http://wwwformal.stanford.edu/jmc/history/dartmouth/dartmouth.html)
Description: This summer research proposal marks the areas of research in artificial intelligence since then. It was a very long summer.
Importance: Influence
Machine learning
Language identification in the limit
 E. M. Gold
 Information and Control, 10:447474, 1967
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):264280, 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): 11341142 (1984)
Description: The Probably approximately correct learning (PAC learning) framework.
Importance: Topic creator, Breakthrough, Influence
Learnability and the VapnikChervonenkis dimension
 A. Blumer
 A. Ehrenfeucht
 D. Haussler
 M. K. Warmuth
 Journal of the ACM, 36(4):929965, 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 433444, New York. ACM.
 Online version(HTML) (http://citeseer.ist.psu.edu/kearns89cryptographic.html)
Description: Proving negative results for PAC learning.
Importance: Influence
The strength of weak learnability
 Robert E. Schapire
 Machine Learning, 5(2):197227, 1990.
 Online version(HTML) (http://citeseer.nj.nec.com/schapire90strength.html)
Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework.
Importance: Breakthrough, Influence
Learning in the presence of malicious errors
 Michael Kearns
 Ming Li
 Journal on Computing, 22(4):807837, August 1993.
 Online version(HTML) (http://citeseer.nj.nec.com/kearns93learning.html)
Description: Proving possibility and imposibility result in the malicious errors framework.
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, p. 163165, September
Description: A correlation method based upon the inverse Fourier transform
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, 674679,Vancouver, Canada,1981
 Online version (http://citeseer.ist.psu.edu/lucas81iterative.html)
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 = "COM31,4", p. 532540,1983.
 Online version (http://citeseer.ist.psu.edu/burt83laplacian.html)
Description: A technique for image encoding using local operators of many scales
Importance: Influence
Condensation  conditional density propagation for visual tracking
 M. Isard and A. Blake
 International Journal of Computer Vision 29(1), pp. 528, 1998.
 Online version (http://citeseer.ist.psu.edu/isard98condensation.html)
Description: A technique for visual tracking
Importance: Influence
Compilers
YACC: Yet another compilercompiler
 Stephen C. Johnson
 Unix Programmer's Manual Vol 2b, 1979
 Online copy (HTML) (http://citeseer.nj.nec.com/johnson79yacc.html)
Description: Yacc is a tool that made compiler writing much easier.
Importance: Influence
Compilers: Principles, Techniques and Tools
 Alfred V. Aho
 Ravi Sethi
 Jeffrey D. Ullman
 AddisonWesley, 1986. ISBN 0201100886
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
Assigning meanings to programs
 Robert W. Floyd
 Mathematical Aspects of Computer Science, pages 1932, 1967
Description: Introduced the idea of attaching logical assertions to points in a program in order to prove its correctness and influenced C. A. R. Hoare's seminal work on program verification.
Importance: Topic creator, Breakthrough, Influence, Introduction
An axiomatic basis for computer programming
 C. Antony R. Hoare
 Communications of the ACM, 12:576580, 1969
Description: Axiomatic foundation for program correctness proofs was laid. The importance of the use of formal methods is explained.
Importance: Topic creator, Breakthrough, Influence, Introduction
The temporal logic of programs
 Amir Pnueli
 In Proc. 18th IEEE Symposium on Foundation of Computer Science, pages 4657, 1977.
Description: The use of temporal logic was suggested as a method for formal verification. Importance: Topic creator, Influence
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, 238252, 1977
Description: Introducing abstract interpretation for the verification of computer programs by sound approximations.
Importance: Topic creator, Influence.
Model Checking
 Edmund M. Clarke, Orna Grumberg, Doron A. Peled
 MIT Press, 1999
Description: An overview of Model checking, an automatic formal verification technique Importance: Introduction
Software engineering
Go To Statement Considered Harmful
 Dijkstra, E. W.
 Communications of the ACM, 11(3), 147148, March 1968
 Online copy (HTML) (http://www.acm.org/classics/oct95/)
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, December:10531058, December 1972.
 Online copy (HTML) (http://www.acm.org/classics/may96/)
Description: The importance of modularization and information hiding.
Importance: Influence
The Mythical ManMonth: 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
 Brooks, Jr., F. P.
 Computer, 20(4), 1019, April 1987
 Online copy (HTML) (http://www.virtualschool.edu/mon/SoftwareEngineering/BrooksNoSilverBullet.html)
Description: We will keep having problems with software...
Importance: Influence
The Cathedral and the Bazaar
 Raymond, E.S.
 First Monday, 3, 3 (March 1998)
 Online copy (HTML) (http://www.redhat.com/support/wpapers/community/cathedral/whitepaper_cathedral.html)
Description: Open source methodology.
Importance: Influence
Design Patterns: Elements of Reusable Object Oriented Software
 E. Gamma, R. Helm, R. Johnson, J. Vlissides
 AddisonWesley, Reading, Massachusetts, 1995.
Description: This book was the first to define and list design patterns in computer science
Importance: Topic creator, Influence
Parallel computing
The Structure of "THE"Multiprogramming System
 Dijkstra, E. W.
 Communication of the ACM, Vol. 11, No. 5 May 1968, pp. 345346
 Online copy (HTML) (http://www.acm.org/classics/mar96/)
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 C28, number 9, p. 690691, 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 (http://citeseer.nj.nec.com/culler93logp.html)
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
Ethernet: Distributed packet switching for local computer networks
 R.M. Metcalfe, D.R. Boggs
 Commun. ACM 19, 7 (July 1976), 395404
 Online copy (HTML) (http://www.acm.org/classics/apr96/)
Description: The Ethernet protocol.
Importance: Influence, Latest and greatest
Distributed computing
The Byzantine Generals Problem
 Leslie Lamport, Robert Shostak, Marshall Pease
 Advances in UltraDependable Distributed Systems, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press
 Online version (http://citeseer.ist.psu.edu/lamport82byzantine.html)
Description: Impossibility result for distributed computing, see Byzantine failure.
Importance: Influence, Breakthrough
See also
 List of publications in science
 Notable publications in software engineering
 List of open problems in computer science
External links
Academic Search Engines