This list needs to be alphabetized.

This is a list of important publications in computer science, organized by field. Image File history File links Broom_icon. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

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
• Influence – A publication which has significantly influenced the world
• Latest and greatest – The current most advanced result in a topic

Computability

Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ...

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
• PDF version of above page (verified to display properly with xpdf and acroread)

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. The Entscheidungsproblem (German for decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ... Alan Mathison Turing, OBE, FRS (23 June 1912 – 7 June 1954) was an English mathematician, logician, and cryptographer. ... The London Mathematical Society (LMS) is the leading mathematical society in England. ... is the 148th day of the year (149th in leap years) in the Gregorian calendar. ... Year 1936 (MCMXXXVI) was a leap year starting on Wednesday (link will display the full calendar) of the Gregorian calendar. ... is the 316th day of the year (317th in leap years) in the Gregorian calendar. ... Year 1936 (MCMXXXVI) was a leap year starting on Wednesday (link will display the full calendar) of the Gregorian calendar. ... For the test of artificial intelligence, see Turing test. ... In computability theory the halting problem is a decision problem which can be stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ... The Entscheidungsproblem (German for decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ...

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. Avram Noam Chomsky (born December 7, 1928) is an American linguist, philosopher, political activist, author, and lecturer. ... The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ... A hierarchy (in Greek hieros = sacred, arkho = rule) is a system of ranking and organizing things. ... In computer science and linguistics, a formal grammar, or sometimes simply grammar, is a precise description of a formal language — that is, of a set of strings. ... In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. ...

Importance: Topic creator, Breakthrough, Influence

Finite automata and their decision problems

• 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 Michael Oser Rabin (born 1931 in Breslau, Germany, today in Poland) is a noted computer scientist and a recipient of the Turing Award, the most prestigious award in the field. ... Dana Stewart Scott (born 1932) is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California. ... For other uses, see IBM (disambiguation) and Big Blue. ... Fig. ... In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. ...

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. Michael Oser Rabin (born 1931 in Breslau, Germany, today in Poland) is a noted computer scientist and a recipient of the Turing Award, the most prestigious award in the field. ... A tree automaton is a type of finite state machine. ... Fig. ... In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics. ...

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. John Hopcroft John E. Hopcroft (born October 7, 1939) is a renowned theoretical computer scientist. ... Jeffrey D. Ullman (born November 22, 1942) is a renowned computer scientist. ... Pearson can mean Pearson PLC the media conglomerate. ...

Importance: Introduction

Computational complexity theory

As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ...

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 Kurt Gödel Kurt Gödel [kurt gøːdl], (April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. ... A separate article covers Saint John Neumann, the American priest. ... Kurt Gödel (IPA: ) (April 28, 1906 Brünn, Austria-Hungary (now Brno, Czech Republic) – January 14, 1978 Princeton, New Jersey) was an Austrian American mathematician and philosopher. ... Kurt Gödel Kurt Gödel [kurt gøːdl], (April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. ... For other persons named John Neumann, see John Neumann (disambiguation). ... Kurt Gödel Kurt Gödel [kurt gøːdl], (April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. ...

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 Michael Oser Rabin (born 1931 in Breslau, Germany, today in Poland) is a noted computer scientist and a recipient of the Turing Award, the most prestigious award in the field. ... As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ...

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. Jack Edmonds is a Professor in the Department of Combinatorics and Optimization at the University of Waterloo. ... As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ...

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. Juris Hartmanis (born July 7, 1928 in Riga, Latvia) is a prominent computer scientist who, with Richard E. Stearns, received the 1993 ACM Turing Award in recognition of their seminal paper which established the foundations for the field of computational complexity theory. Born in Latvia, he moved to Germany after... Richard Edwin Stearns is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award in recognition of their seminal paper which established the foundations for the field of computational complexity theory. Stearns is now Distinguished Professor Emeritus of Computer Science at the University at Albany, which... As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ...

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. Manuel Blum (born 26 April 1938 in Caracas, Venezuela) is a computer scientist who received the Turing Award in 1995 In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking. // Biography Blum attended MIT, where he received his bachelors... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. ...

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". Stephen A. Cook is a noted computer scientist. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... 3SAT redirects here. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... Leonid Levin (born November 2, 1948, USSR) is a computer scientist. ...

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. One of the most important results of computational complexity theory was Stephen Cooks 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. ... Richard M. Karp (born 1935) is a computer scientist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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. Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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."). A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the trapdoor. Trapdoor functions are widely used in cryptography. ... Andrew Chi-Chih Yao (姚期智, pinyin: Yáo Qīzhì) (born December 24, 1946) is a prominent computer scientist. ... A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the trapdoor. Trapdoor functions are widely used in cryptography. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...

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. Professor Oded Goldreich Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. ... Dr. Shafrira Goldwasser (born 1956) is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel. ... Silvio Micali (b. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... A one-way function is a function which is easy to calculate but hard to invert — it is difficult to calculate the input to the function given its output. ...

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. Dr. Shafrira Goldwasser (born 1956) is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel. ... Silvio Micali (b. ... Charles Rackoff is a noted modern cryptologist. ...

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. The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has... // Interactive Proof Systems In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. ...

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. // Interactive Proof Systems In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... Adi Shamir (‎; born 1952) is an Israeli cryptographer. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. ...

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 As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ... Christos Papadimitriou is a Professor in the Computer Science Division at the University of California, Berkeley, USA. He studied at the National Technical University of Athens (BS in Electrical Engineering, 1972) and at Princeton University (MS in Electrical Engineering, 1974 and PhD in Electrical Engineering and Computer Science, 1976). ... Pearson can mean Pearson PLC the media conglomerate. ... As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ...

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.

The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...

Probabilistic Checking of Proofs: A New Characterization of NP

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

The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...

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. The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...

Importance: Topic creator, Breakthrough, Influence

Computational Linguistics

Computational linguistics is an interdisciplinary field dealing with the statistical and logical modeling of natural language from a computational perspective. ...

Realization of Natural-Language Interfaces Using Lazy Functional Programming

• Richard A. Frost
• ACM Computing Surveys Volume 38 Issue 4 Article 11, December 2006
• Online copy

Description: This survey documents relatively less researched importance of lazy functional programming languages (i.e. Haskell) to construct Natural Language Processors and to accommodated many linguistic theories. Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...

Importance: Survey, Introduction.

Algorithms

See also List of algorithms. Flowcharts are often used to represent algorithms. ... The following is a list of the algorithms described in Wikipedia. ...

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. Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ... Martin Davis, (born 1926, New York City) is an American mathematician, known for his work on Hilberts tenth problem. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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. J. Alan Robinson is a philosopher (by training), mathematician and computer scientist. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic. ... For the idea of global unification, see globalization. ... Automated theorem proving (ATP) or automated deduction, currently the most well-developed subfield of automated reasoning (AR), is the proving of mathematical theorems by a computer program. ... Prolog is a logic programming language. ... Logic programming is a declarative programming paradigm in which a set of attributes that a solution should have are specified rather than set of steps to obtain such a solution. ...

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. Richard M. Karp (born 1935) is a computer scientist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985. ... The minimum spanning tree of a planar graph. ... In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... If a salesman starts at point A, and if the distances between every pair of points are known, what is the shortest route which visits all points and returns to point A? The traveling salesman problem (TSP) is a problem in discrete or combinatorial optimization. ... In computer science, approximation algorithms are an approach to attacking NP-hard optimization 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. Leonid Khachiyan Leonid Khachiyan (May 3, 1952 - April 29, 2005) was a Russian-born mathematician who taught Computer Science at Rutgers University. ... In mathematics, linear programming (LP) problems involve the optimization of a linear objective function, subject to linear equality and inequality constraints. ... Narendra K. Karmarkar (b. ... Narendra K. Karmarkar (b. ...

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. Michael Oser Rabin (born 1931 in Breslau, Germany, today in Poland) is a noted computer scientist and a recipient of the Turing Award, the most prestigious award in the field. ... The Miller-Rabin primality test or Rabin-Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. ... A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. ...

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. For other uses, see Annealing. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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. Cover of books The Art of Computer Programming[1] is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... A monograph is a scholarly book or a treatise on a single subject or a group of related subjects. ... Fascicles are sections of a book, usually a reference work, that because of its length, is issued in parts so that the information may be made available to the public as soon as possible rather than waiting years or decades to complete the entire work. ... In physics, the mixing (physics) of dynamical systems In chemistry, the interpenetration or interdiffusion of at least two gas, liquid or solid phases to a mixture. ... MMIX is a 64-bit RISC virtual machine designed by Donald Knuth, with significant contributions by John Hennessy (who designed the MIPS chip) and Dick Sites (who was the architect of the Alpha chip). ... This article does not cite any references or sources. ... Structured programming can be seen as a subset or subdiscipline of procedural programming, one of the major programming paradigms. ...

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. Niklaus E. Wirth (born February 15, 1934) is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering. ...

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. Dr. Alfred V. Aho is a computer scientist. ... John Hopcroft John E. Hopcroft (born October 7, 1939) is a renowned theoretical computer scientist. ... Jeffrey D. Ullman (born November 22, 1942) is a renowned computer scientist. ...

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. Pearson can mean Pearson PLC the media conglomerate. ...

Importance: Introduction

See Also: How to Solve It George Pólyas 1945 book How to Solve It (ISBN 0-691-08097-6) is a small volume describing methods of problem solving. ...

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. For other men with the same name, see Robert Sedgewick Robert Sedgewick is the author of the celebrated book series Algorithms, published by Addison-Wesley. ...

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. Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Election People This box:      Professor Ronald Lorin Rivest (born 1947, Schenectady, New York) is a cryptographer. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ...

Importance: Introduction, Influence

Algorithmic information theory

This article or section is in need of attention from an expert on the subject. ...

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. Ray Solomonoff (born 1926) invented the concept of algorithmic probability around 1960. ... This article or section is in need of attention from an expert on the subject. ... In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. ... In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. ... Andrey Nikolaevich Kolmogorov (Russian: Андре́й Никола́евич Колмого́ров) (April 25, 1903 - October 20, 1987) was a Soviet mathematician who made major advances in different academic fields (among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity). ... Ray Solomonoff (born 1926) invented the concept of algorithmic probability around 1960. ... Andrey Nikolaevich Kolmogorov (Russian: Андре́й Никола́евич Колмого́ров) (April 25, 1903 - October 20, 1987) was a Soviet mathematician who made major advances in different academic fields (among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity). ...

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. Gregory John Chaitin (born 1947) is an Argentine-American mathematician and computer scientist. ... This article or section is in need of attention from an expert on the subject. ...

Importance: Introduction

Information theory

Not to be confused with information technology, information science, or informatics. ...

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. The article entitled A Mathematical Theory of Communication, published in 1948 by mathematician Claude E. Shannon, was one of the founding works of the field of information theory. ... Claude Elwood Shannon (April 30, 1916 - February 24, 2001) has been called the father of information theory, and was the founder of practical digital circuit design theory. ... Bell System Technical Journal was the in-house journal of Bell Laboratories. ... There is much discussion in the academic world of communication as to what actually constitutes communication. ... Not to be confused with information technology, information science, or informatics. ...

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. Richard Wesley Hamming (February 11, 1915 – January 7, 1998) was a mathematician whose work had many implications for computer science and telecommunications. ... In information theory and coding, an error-correcting code or ECC is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. ... In telecommunication, a Hamming code is a linear error-correcting code named after its inventor, Richard Hamming. ... In information theory, the Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different. ...

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. Professor David A. Huffman (August 9, 1925 - October 7, 1999) was a pioneer in the Computer Science field. ... In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ...

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. Jacob Ziv, along with Abraham Lempel, developed the lossless LZ77 compression algorithm. ... Abraham Lempel is a computer scientist and one of the fathers of the LZ family of lossless data compression algorithms. ... The IEEE Transactions on Information Theory is a scientific journal published by the Institute of Electrical and Electronic Engineers (IEEE) It is dedicated to the study of information theory, the mathematics on communications. ... LZ77 and LZ78 are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. ...

Importance: Influence, Breakthrough

Elements of Information Theory

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

Description: A good and popular introduction to information theory. Thomas M. Cover (born August 7, 1938) is Professor jointly in the Departments of Electrical Engineering and Statistics at Stanford University. ... Look up Wiley in Wiktionary, the free dictionary. ...

Importance: Influence, Introduction

Operating systems

In computing, an operating system (OS) is the system software responsible for the direct control and management of hardware and basic system operations. ...

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. Fernando José Corbató (born July 1, 1926 in Oakland, California) is a prominent computer scientist, notable as a pioneer in the development of time-sharing operating systems. ... Alternate uses: see Timesharing Time-sharing is an approach to interactive computing in which a single computer is used to provide apparently simultaneous interactive general-purpose computing to multiple users by sharing processor time. ...

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. Peter J. Denning is a computer scientist and one of the team members of the Multics project. ... For other uses, see cache (disambiguation). ...

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. The program thinks it has a large range of contiguous addresses; but in reality the parts it is currently using are scattered around RAM, and the inactive parts are saved in a disk file. ... Multics (Multiplexed Information and Computing Service) was an extraordinarily influential early time-sharing operating system. ... Jack B. Dennis is an electrical engineer and a computer scientist. ...

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. Butler W. Lampson is a computer scientist, considered to be one of the most significant in the history of the field. ...

Importance: Influence

The UNIX Time-Sharing System

• Dennis M. Ritchie and Ken Thompson
• Communications of the ACM 7, 7, July 1974.
• Online copy (few formats)

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. Filiation of Unix and Unix-like systems Unix (officially trademarked as UNIX®, sometimes also written as or ® with small caps) is a computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs including Ken Thompson, Dennis Ritchie and Douglas McIlroy. ... Ken Thompson (left) with Dennis Ritchie (right) Dennis MacAlistair Ritchie (September 9, 1941- ) is a computer scientist notable for his influence on ALTRAN, B, BCPL, C, Multics, and UNIX. Born in Bronxville, New York, Ritchie graduated from Harvard with degrees in physics and applied mathematics. ... Ken Thompson Kenneth Thompson (born February 4, 1943) is a pioneer of computer science notable for his contributions to the development of the C programming language and the UNIX operating system. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... Filiation of Unix and Unix-like systems Unix (officially trademarked as UNIX®, sometimes also written as or ® with small caps) is a computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs including Ken Thompson, Dennis Ritchie and Douglas McIlroy. ... An operating system (OS) is the software that manages the sharing of the resources of a computer and provides programmers with an interface used to access those resources. ...

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. Butler W. Lampson is a computer scientist, considered to be one of the most significant in the history of the field. ...

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 John Ousterhout is the original force behind the scripting programming language Tcl and the platform-independent GUI toolkit Tk, which he developed when he was professor at the University of California, Berkeley. ... Coscheduling is a process used in concurrent systems that schedules related processes to run on different processors at the same time. ...

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. Marshall Kirk McKusick (b. ... William N. Joy (born 1954), commonly known as Bill Joy, co-founded Sun Microsystems in 1982 along with Vinod Khosla, Scott McNealy and Andy Bechtolsheim, and served as chief scientist at the company until 2003. ... For library and office filing systems, see Library classification. ... Filiation of Unix and Unix-like systems Unix (officially trademarked as UNIX®, sometimes also written as or ® with small caps) is a computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs including Ken Thompson, Dennis Ritchie and Douglas McIlroy. ...

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. John Ousterhout is the original force behind the scripting programming language Tcl and the platform-independent GUI toolkit Tk, which he developed when he was professor at the University of California, Berkeley. ... The Log-Structured File System (or LFS) is an implementation of a log-structured file system, originally developed for BSD. It was removed from FreeBSD and OpenBSD. In NetBSD, its still present, but it appears to be no longer completely functional as of NetBSD 2. ...

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. Graphical overview of a microkernel A microkernel is a minimal computer operating system kernel providing only basic operating system services (system calls), while other services (commonly provided by kernels) are provided by user-space programs called servers. ... Mach may refer to: Ernst Mach Mach number, as a measure of speed inertial mass GNU Mach The microkernel on which GNU Hurd is based Mach kernel, an operating systems kernel technology used in Mac OS X Mach band, an optical illusion Mach Five, the name of the car in... Graphical overview of a microkernel A microkernel is a minimal computer operating system kernel providing only basic operating system services (system calls), while other services (commonly provided by kernels) are provided by user-space programs called servers. ... Mac OS X (pronounced ) is a line of graphical operating systems developed, marketed, and sold by Apple Inc. ... The Windows NT operating system familys architecture consists of two layers (user mode and kernel mode), with many different modules within both of these layers. ... L4 is, collectively, a family of related computer programs. ...

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.. Margo Seltzer is a researcher in the area of computer systems. ... Member of the UCB Computer Science Research Group (CSRG) at the University of California, Berkeley, who created BSD. Worked at Berkeley Software Design, who produced BSD/OS (also known as BSDi), a commercial version of BSD. Now works at Sleepycat Software, who produce Berkeley DB. Author of nvi. ... Marshall Kirk McKusick (b. ...

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. Marshall Kirk McKusick (b. ...

Importance:

Databases

This article is about computing. ...

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. Edgar Frank Ted Codd (August 23, 1923 – April 18, 2003) was a British computer scientist who made seminal contributions to the theory of relational databases. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ...

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. Rudolf Bayer is Professor (emerit. ... Year 1971 (MCMLXXI) was a common year starting on Friday (link will display full calendar) of the 1971 Gregorian calendar, known as the year of cyclohexanol. ... B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ... A binary tree, a simple type of branching linked data structure. ...

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 Edgar Frank Ted Codd (August 23, 1923 – April 18, 2003) was a British computer scientist who made seminal contributions to the theory of relational databases. ...

Importance:

The Entity Relationship Model – Towards a Unified View of Data

• Peter 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. Dr. Peter Chen is the originator of the Entity-Relationship Model (ER Model). ... The Entity-Relationship model is a data model for high-level descriptions of conceptual data models, and it provides a graphical notation for representing such data models in the form of entity-relationship diagrams. ...

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 . Donald D. Chamberlin is best known as one of the principal designers of the original SQL language specification. ... Raymond ‘Ray’ Boyce grew up in New York, he went to college in Providence, Rhode Island and got his PhD in Purdue in 1971 [1] . After he left Purdue he worked on database projects for IBM in Yorktown Heights, New York. ... SQL (IPA: or ) is a computer language designed for the retrieval and management of data in relational database management systems, database schema creation and modification, and database object access control management. ...

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. A transaction is an agreement, communication, or movement carried out between separate entities or objects. ... Look up Consistency in Wiktionary, the free dictionary. ... For schedule in computer science, see schedule (computer science). ...

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 German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...

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. William Friedman. ... In cryptography, coincidence counting is the technique (invented by William F. Friedman) of putting two texts side-by-side and counting the number of times that a letter appears next to itself in both copies. ...

Importance: Breakthrough, Influence

Treatise on the Enigma

• Alan Turing
• Online version

Description: The breaking of the Enigma. Alan Mathison Turing, OBE, FRS (23 June 1912 – 7 June 1954) was an English mathematician, logician, and cryptographer. ... For a discussion of how Enigma-derived intelligence was put to use, see Ultra (WWII intelligence). ...

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. Communication Theory of Secrecy Systems is a paper published by Claude Shannon discussing cryptography from the viewpoint of information theory. ... Claude Elwood Shannon (April 30, 1916 - February 24, 2001) has been called the father of information theory, and was the founder of practical digital circuit design theory. ... Bell System Technical Journal was the in-house journal of Bell Laboratories. ... Not to be confused with information technology, information science, or informatics. ...

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. David Kahn is a US historian, journalist and writer. ...

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. Feistel 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. Horst Feistel (30 January 1915(1)–14 November 1990) was a cryptographer who worked on the design of ciphers at IBM, initiating research that would culminate in the development of the Data Encryption Standard (DES) in the 1970s. ... For other uses, see IBM (disambiguation) and Big Blue. ... In cryptography, a Feistel cipher is a block cipher with a symmetric structure, named after IBM cryptographer Horst Feistel; it is also commonly known as a Feistel network. ... The Data Encryption Standard (DES) is a cipher (a method for encrypting information) selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976, and which has subsequently enjoyed widespread use internationally. ...

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. The Data Encryption Standard (DES) is a cipher (a method for encrypting information) selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976, and which has subsequently enjoyed widespread use internationally. ... NBS can stand for: Nash Bargaining Solution in Economics National Banking System in Economics National Bureau of Standards which is, today, called NIST (National Institute of Standards and Technology). ... The Data Encryption Standard (DES) is a cipher (a method for encrypting information) selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976, and which has subsequently enjoyed widespread use internationally. ...

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. Whitfield Diffie Bailey Whitfield Whit Diffie (born June 5, 1944) is a US cryptographer and one of the pioneers of public-key cryptography. ... Martin Hellman - Wikipedia, the free encyclopedia /**/ @import /skins-1. ... The IEEE Transactions on Information Theory is a scientific journal published by the Institute of Electrical and Electronic Engineers (IEEE) It is dedicated to the study of information theory, the mathematics on communications. ... Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key, by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically. ... Diffie-Hellman (D-H) key exchange is a cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. ... Whitfield Diffie Bailey Whitfield Whit Diffie (born June 5, 1944) is a US cryptographer and one of the pioneers of public-key cryptography. ... Martin Hellman - Wikipedia, the free encyclopedia /**/ @import /skins-1. ...

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. Loren Kohnfelder is best known for his MIT Bsc thesis written in May 1978 describing a practical means of applying public key cryptography to secure network communications. ... Loren Kohnfelder is best known for his MIT Bsc thesis written in May 1978 describing a practical means of applying public key cryptography to secure network communications. ... Mapúa Institute of Technology (MIT, MapúaTech or simply Mapúa) is a private, non-sectarian, Filipino tertiary institute located in Intramuros, Manila. ... A certificate is an official document affirming some fact. ...

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. Ralph C. Merkle (born 2 February 1952) is a pioneer in public key cryptography, and more recently a researcher and speaker on molecular nanotechnology and cryonics. ...

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. Election People This box:      Professor Ronald Lorin Rivest (born 1947, Schenectady, New York) is a cryptographer. ... Adi Shamir (‎; born 1952) is an Israeli cryptographer. ... Leonard Adleman Leonard Adleman (born December 31, 1945) is a theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... In cryptography, RSA is an algorithm for public-key cryptography. ...

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. Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ...

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. Adi Shamir (‎; born 1952) is an Israeli cryptographer. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ...

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. Dorothy Elizabeth Denning (the daughter of C. Lowell and Helen Watson Robling on August 12, 1945) is an American information security researcher. ... Peter J. Denning is a computer scientist and one of the team members of the Multics project. ...

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. Non-interference may refer to: Noninterference (Buddhism), a Buddhist concept Non-interference (security), a security policy model Category: ...

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. Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. ... Dr. Shafrira Goldwasser (born 1956) is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel. ... Silvio Micali (b. ...

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. One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ... In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. ... In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. ...

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. Professor Oded Goldreich Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. ... Silvio Micali (b. ... Avi Wigderson is an Israeli mathematician and computer scientist who received the Nevanlinna Prize in 1994 for his work on computational complexity. ...

Importance: Breakthrough, Influence

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority

• Goldreich, O, Micali, S., Wigderson, A.
• STOC, pgs. 218-229, 1987
• Online copy(HTML)

Description: Seminal paper in secure function evaluation Professor Oded Goldreich Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. ... Silvio Micali (b. ... Avi Wigderson is an Israeli mathematician and computer scientist who received the Nevanlinna Prize in 1994 for his work on computational complexity. ...

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. Theodore Ted Tso is a software developer known for his contributions to the Linux kernel, in particular his contributions to filesystems. ... Kerberos is the name of a computer network authentication protocol, which allows individuals communicating over a non-secure network to prove their identity to one another in a secure manner. ... For other uses of the terms authentication, authentic and authenticity, see authenticity. ... A cryptographic protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods. ...

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. Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. ... Adi Shamir (‎; born 1952) is an Israeli cryptographer. ... Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. ...

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. Mitsuru Matsui is a Japanese cryptographer and senior researcher for Mitsubishi Electric Company. ... Eurocrypt (or EUROCRYPT) is an important conference for cryptography research. ... In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. ...

Importance: Breakthrough, Influence

Breaking and Fixing the Needham-Schroeder Public-Key protocol using FDR

• Gavin Lowe
• Software - concepts and tools 1996
• Online version

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. SHA redirects here. ...

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. Paul C. Kocher is an American cryptographer and cryptography consultant, currently the president of Cryptography Research, Inc. ... EFF Logo The Electronic Frontier Foundation (EFF) is an international non-profit advocacy and legal organization based in the United States with the stated purpose of being dedicated to preserving free speech rights such as those protected by the First Amendment to the United States Constitution in the context of... In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ... The Data Encryption Standard (DES) is a cipher (a method for encrypting information) selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976, and which has subsequently enjoyed widespread use internationally. ... A key is a piece of information that controls the operation of a cryptography algorithm. ...

Importance: Breakthrough (and break code), Influence

Artificial intelligence

AI redirects here. ...

Computing machinery and intelligence

• Alan Turing
• Mind, 59:433–460, 1950.
• Online copy

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 Alan Mathison Turing, OBE, FRS (23 June 1912 – 7 June 1954) was an English mathematician, logician, and cryptographer. ... For the Doctor Who novel named after the test, see The Turing Test (novel). ... AI redirects here. ...

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. John McCarthy (born September 4, 1927, in Boston, Massachusetts, sometimes known affectionately as Uncle John McCarthy), is a prominent computer scientist who received the Turing Award in 1971 for his major contributions to the field of Artificial Intelligence. ... Marvin Lee Minsky (born August 9, 1927), sometimes affectionately known as Old Man Minsky, is an American cognitive scientist in the field of artificial intelligence (AI), co-founder of MITs AI laboratory, and author of several texts on AI and philosophy. ... Claude Elwood Shannon (April 30, 1916 - February 24, 2001) has been called the father of information theory, and was the founder of practical digital circuit design theory. ... AI redirects here. ...

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. Lotfi A. Zadeh (2004) Lotfi Asker Zadeh (in Persian:لطفی علی‌عسکرزاده), (born February 4, 1921) is a mathematician and computer scientist, and a professor of computer science at the University of California at Berkeley. ... Fuzzy sets are an extension of classical set theory and are used in fuzzy logic. ...

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. Judea Pearl is a computer science professor at UCLA. He was one of the pioneers of Bayesian networks and the probabilistic approach to artificial intelligence. ... Bayesian refers to probability and statistics -- either methods associated with the Reverend Thomas Bayes (ca. ...

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. Artificial Intelligence: A Modern Approach (ISBN 0137903952) (AIMA) is the current standard college text book on Artificial Intelligence and is written by Stuart J. Russell and Peter Norvig. ... Stuart Russell is a computer scientist known for his contributions to artificial intelligence. ... Peter Norvig is currently the Director of Research (formerly Director of Search Quality) at Google Inc. ...

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:

Semi Human Instinctive Artificial Intelligence

• S.M.Mohammadzadeh and A.Norouzi
• ACM Press, 2006, ISBN 1-74052-130-7

Description: This paper proposes a nondeterministic decision making theory based on Semi Human Instincts implemented by learned potential fields, using neural networks and fuzzy logic offline and online learning algorithms, which enable the agent to perform in anonymous, dynamic and non-deterministic environments The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...

Importance:

Machine learning

As a broad subfield of artificial intelligence, machine learning is concerned with the design and development of algorithms and techniques that allow computers to learn. At a general level, there are two types of learning: inductive, and deductive. ...

Language identification in the limit

• E. M. Gold
• Information and Control, 10:447–474, 1967
• Online version(HTML)

Description: This paper created Algorithmic learning theory. Language identification in the limit is a formal model for inductive inference. ... Algorithmic learning theory (or inductive inference) is a framework for machine learning. ...

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. Vladimir Naumovich Vapnik is one of the main developers of Vapnik Chervonenkis theory. ... Alexey Chervonenkis is a Russian mathematician, and one of the main developers of the Vapnik Chervonenkis theory, an important part of computational learning theory. ... In statistics, computational learning theory is a mathematical field related to the analysis of machine learning algorithms. ... Vapnik Chervonenkis theory (also known as VC theory) was developed during 1960-1990 by Vladimir Vapnik and Alexey Chervonenkis. ... The VC dimension (for Vapnik Chervonenkis dimension) is a measure of the capacity of a classification algorithm. ...

Importance: Breakthrough, Influence

A theory of the learnable

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

Description: The Probably approximately correct learning (PAC learning) framework. Leslie Valiant was educated at Kings College, Cambridge, Imperial College London; and at Warwick University where he received his Ph. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... Probably approximately correct learning (PAC learning) is a framework of learning that was proposed by Leslie Valiant in his paper A theory of the learnable. ...

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. David E. Rumelhart has made many contributions to the formal analysis of human cognition, working primarily within the frameworks of mathematical psychology, symbolic artificial intelligence, and parallel distributed processing. ... Geoff Hinton invented the back-propogation algorithm which solved the problem of training multi-layer neural networks first identified by Marvin Minsky and Seymour Papert in 1969 in their book Perceptrons, which almost but not quite killed off neural-network research. ... Backpropagation is a supervised learning technique used for training artificial neural networks. ... An artificial neural network (ANN), often just called a neural network (NN), is a mathematical model or computational model based on biological neural networks. ... Paul Werbos is an scientist best known for his 1974 Harvard University Ph. ... Year 1974 (MCMLXXIV) was a common year starting on Tuesday (link will display full calendar) of the 1974 Gregorian calendar. ...

Importance: Influence

Induction of Decision Trees

• J.R. Quinlan
• Machine Learning, 1. 81--106, 1986.
• Online version(PDF)

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. Ross Quinlan is a pioneering researcher in data mining and decision theory. ... In operations research, specifically in decision analysis, a decision tree is a decision support tool that uses a graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. ...

Importance: Influence

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

• Nick Littlestone
• Machine Learning 2: 285-318, 1988
• Online version(PDF)

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. Richard S. Sutton is a professor and iCorechair in the department of computing science at the University of Alberta. ... Reinforcement learning refers to a class of problems in machine learning which postulate an agent exploring an environment in which the agent perceives its current state and takes actions. ...

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. Manfred K. Warmuth is a researcher and professor at the University of California, Santa Cruz. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... Probably approximately correct learning (PAC learning) is a framework of learning that was proposed by Leslie Valiant in his paper A theory of the learnable. ... The VC dimension (for Vapnik Chervonenkis dimension) is a measure of the capacity of a classification algorithm. ...

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. Leslie Valiant was educated at Kings College, Cambridge, Imperial College London; and at Warwick University where he received his Ph. ... Probably approximately correct learning (PAC learning) is a framework of learning that was proposed by Leslie Valiant in his paper A theory of the learnable. ...

Importance: Influence

The strength of weak learnability

• Robert E. Schapire
• Machine Learning, 5(2):197–227, 1990.
• Online version(HTML)

Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework. The proof was done by introducing the boosting method. Probably approximately correct learning (PAC learning) is a framework of learning that was proposed by Leslie Valiant in his paper A theory of the learnable. ... Boosting is a machine learning meta-algorithm for performing supervised learning. ...

Learning in the presence of malicious errors

• Michael Kearns
• Ming Li
• Journal on Computing, 22(4):807–837, August 1993.
• Online version(HTML)

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. Vladimir Naumovich Vapnik is one of the main developers of Vapnik Chervonenkis theory. ... Support vector machines (SVMs) are a set of related supervised learning methods used for classification and regression. ... In machine learning, the kernel trick is a method for converting a linear classifier algorithm into a non-linear one by using a non-linear function to map the original observations into a higher-dimensional space; this makes a linear classification in the new space equivalent to non-linear classification...

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. Researcher in the fields of Machine Learning, Artificial Intelligence, Bioinformatics. ... David Haussler is a Howard Hughes Medical Institute Investigator. ... The Proceedings of the National Academy of Sciences (USA), mostly commonly referred to as PNAS, is the official publication of the National Academy of Sciences of the United States of America. ... Gene expression, or simply expression, is the process by which the inheritable information which comprises a gene, such as the DNA sequence, is made manifest as a physical and biologically functional gene product, such as protein or RNA. Several steps in the gene expression process may be modulated, including the... Support vector machines (SVMs) are a set of related supervised learning methods, applicable to both classification and regression. ...

Importance: Breakthrough, Influence

Computer vision

Computer vision is the science and technology of machines that see. ...

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 Phase correlation is a frequency domain approach to determine the relative translative movement between two images. ... In mathematics, the Fourier transform is a certain linear operator that maps functions to other functions. ...

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 Optical flow is a concept which is close to, but not identical with the motion of objects within a visual representation. ...

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 In computer vision, sets of data acquired by sampling the same scene or object at different times, or from different perspectives, will be in different coordinate systems. ... Binocular vision is vision in which both eyes are used synchronously to produce a single image. ... Takeo Kanade is a notable researcher in Machine Vision. ...

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 The IEEE Transactions on Communications is an academic journal published by the IEEE Communications Society. ...

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 The condensation algorithm (Conditional Density Propagation) is a computer vision algorithm. ...

Importance: Influence

Compilers

A compiler is a computer program that translates a computer program written in one computer language (called the source language) into an equivalent program written in another computer language (called the output or the target language). ...

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. S-attributed grammars are a class of attribute grammars, comparable with L-attributed grammars but characterized by having no inherited attributes at all. ... LR-attributed grammars are a special type of attribute grammars. ...

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

• Stephen C. Johnson
• Unix Programmer's Manual Vol 2b, 1979
• Online copy (HTML)

Description: Yacc is a tool that made compiler writing much easier. Stephen Curtis Johnson spent nearly 20 years at Bell Labs and AT&T, where he wrote Yacc, Lint, and the Portable C Compiler. ... yacc is a computer program that serves as the standard parser generator on Unix systems. ... A diagram of the operation of a typical multi-language, multi-target compiler. ...

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. Susan L. Graham is a computer scientist. ... Marshall Kirk McKusick (b. ...

• Online copy

Description: The gprof profiler In computer programming, a profiler is a computer program that can track the performance of another program by checking information collected while the code is executed . ...

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. Dr. Alfred V. Aho is a computer scientist. ... Ravi Sethi (born 1947 is an Indian computer scientist retired from Bell Labs and now president of [Avaya Labs Research]. He is best known as one of three authors of the classic computer science textbook Compilers: Principles, Techniques and Tools, also known as the Dragon Book. ... Jeffrey D. Ullman (born November 22, 1942) is a renowned computer scientist. ... Monica Lam is a computer scientist on the faculty at Stanford, and one of the top 50 most cited computer scientists in the world. ... Pearson can mean Pearson PLC the media conglomerate. ... Dragon book may refer to: Principles of Compiler Design (the green dragon book), by Alfred Aho and Jeffrey Ullman Compilers: Principles, Techniques, and Tools (the red dragon book), by Aho, Ravi Sethi and Ullman Compilers: Principles, Techniques, and Tools (2nd Edition) (the purple dragon book) The Dragon Book of Verse...

Importance: Introduction, Influence

Formal verification

In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics. ...

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 (MS IExplorer only)
• PDF version of above page (verified to display properly with xpdf and acroread)

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". The Entscheidungsproblem (German for decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ... Alan Mathison Turing, OBE, FRS (23 June 1912 – 7 June 1954) was an English mathematician, logician, and cryptographer. ... The London Mathematical Society (LMS) is the leading mathematical society in England. ... is the 148th day of the year (149th in leap years) in the Gregorian calendar. ... Year 1936 (MCMXXXVI) was a leap year starting on Wednesday (link will display the full calendar) of the Gregorian calendar. ... is the 316th day of the year (317th in leap years) in the Gregorian calendar. ... Year 1936 (MCMXXXVI) was a leap year starting on Wednesday (link will display the full calendar) of the Gregorian calendar. ...

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. Robert W Floyd (June 8, 1936 - September 25, 2001) was an eminent computer scientist. ... Robert W Floyd (June 8, 1936 - September 25, 2001) was an eminent computer scientist. ...

Importance: Topic creator

An Axiomatic Basis for Computer Programming

• C.A.R. Hoare
• Communications of the ACM, 12:576–580, 1969
• online version (PDF)

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. Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, and perhaps even the worlds most widely used algorithm of any kind... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ...

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". Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ) was a Dutch computer scientist. ...

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. David Gries (born 26 April 1939 in Flushing, Queens, New York) is a computer scientist at Cornell University. ...

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. Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ) was a Dutch computer scientist. ...

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). Joe Stoy is a British computer scientist, although he originally studied physics at Oxford University. ...

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. Amir Pnueli (born April 22, 1941) is an Israeli computer scientist who received the Turing Award in 1996 for seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification. ... In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. ...

Importance: Topic creator, Impact

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

• Leslie Lamport
• CACM, 21(7):558-- 565, July 1978
• online version(PDF)

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. Leslie Lamport Dr. Leslie Lamport (born 1941) is an American computer scientist. ...

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. Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, and perhaps even the worlds most widely used algorithm of any kind...

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). Robin Milner is a prominent British computer scientist. ...

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. Cliff Jones FACM FBCS FIEE FREng is a British computer scientist, specializing in research into formal methods. ... Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ) was a Dutch computer scientist. ...

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. David Gries (born 26 April 1939 in Flushing, Queens, New York) is a computer scientist at Cornell University. ...

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. Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, and perhaps even the worlds most widely used algorithm of any kind...

Importance: Influence

Jean-Yves Girard. Linear logic. Theoretical Computer Science, 50:1-102, 1987.

Linear logic (1987)

• J.-Y, Girard
• 1987
• Online version

Description: Girard's linear logic was a breakthrough in designing typing systems for sequential and concurrent computation, especially for resource conscious typing systems. In mathematical logic, linear logic is a type of substructural logic that denies the structural rules of weakening and contraction. ...

Importance: Breakthrough

A Calculus of Mobile Processes (1989)

• R. Milner, J. Parrow, D. Walker
• 1989
• Online version: Part 1 and Part 2

Description: This paper introduces the Pi-Calculus, a generalisation of CCS which allows process mobility. The calculus is extremely simple and has become the dominant paradigm in the theoretical study of programming languages, typing systems and program logics. In theoretical computer science, the π-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker to model concurrency (just as the λ-calculus is a simple model of sequential programming languages). ...

Importance: Breakthrough

The Z Notation: A Reference Manual

• Mike Spivey
• 1989
• Online version

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). Mike Spivey is a computer scientist at the University of Oxford. ...

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. Robin Milner is a prominent British computer scientist. ...

Importance: Introduction

Software engineering

Software engineering (SE) is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software. ...

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 Software engineering (SE) is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software. ... This article is about the military alliance. ... Portrait of Peter Naur taken 1968, courtesy of Robert M. McClure. ... Brian Randell is a computer scientist, specializing in research in software fault tolerance and dependability. ...

Importance: Defined the field of Software engineering Software engineering (SE) is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software. ...

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. GOTO is a statement found in many computer programming languages. ... In computer science and related disciplines, considered harmful is a phrase popularly used in the titles of diatribes and other critical essays. ... Edsger Dijkstra Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002; IPA: ) was a Dutch computer scientist. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... Structured programming can be seen as a subset or subdiscipline of procedural programming, one of the major programming paradigms. ...

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 David Lorge Parnas (born February 10, 1941) is an early pioneer of software engineering who developed the concept of module design which is the foundation of object oriented programming today. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... In computer science, the principle of information hiding is the hiding of design decisions in a computer program that are most likely to change, thus protecting other parts of the program from change if the design decision is changed. ...

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. Professor emeritus Ole-Johan Dahl (October 12, 1931 – June 29, 2002) was a Norwegian computer scientist and is considered to be one of the fathers of Simula and object-oriented programming along with Kristen Nygaard. ... Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort (or Hoaresort), the worlds most widely used sorting algorithm, in 1960. ... Object-oriented programming (OOP) is a programming paradigm that uses objects and their interactions to design applications and computer programs. ...

Importance: Breakthrough , Influence

A technique for software module specification with examples

• David Parnas
• Comm. ACM 15, 5 [(May, 1972), 330-336.
• Online copy (PDF)

Description: software specification. David Lorge Parnas (born February 10, 1941) is an early pioneer of software engineering who developed the concept of module design which is the foundation of object oriented programming today. ... Specification may refer to several different concepts: Specification (standards) refers to specific standards Specificatio - a legal concept Specification (regression) refers to the practice of translating theory into a regression model Category: ...

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. Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, and perhaps even the worlds most widely used algorithm of any kind... In computing, the second-system effect or sometimes the second-system syndrome refers to the tendency to design the successor to a relatively small, elegant, and successful system as an elephantine, feature-laden monstrosity. ...

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... Book cover The Mythical Man-Month: Essays on Software Engineering is a book on software project management by Fred Brooks, whose central theme is that Adding manpower to a late software project makes it later. ... Frederick Phillips Brooks, Jr. ...

Importance: Influence

No Silver Bullet: Essence and Accidents of Software Engineering

• Brooks, Jr., F. P.
• Computer, 20(4):10–19, April 1987
• Online copy (HTML)

Description: We will keep having problems with software... No Silver Bullet - essence and accidents of software engineering is a well-known paper on software engineering written by Fred Brooks in 1986. ... Frederick Phillips Brooks, Jr. ... Computer is an IEEE Computer Society practitioner-oriented magazine issued to all members of the society. ...

Importance: Influence

The Cathedral and the Bazaar

• Raymond, E.S.
• First Monday, 3, 3 (March 1998)
• Online copy (HTML)

Description: Open source methodology. The Cathedral and the Bazaar (abbreviated CatB) is an essay by Eric S. Raymond on software engineering methods, based on his observations of the Linux kernel development process and his experiences managing an open source project, fetchmail. ... Eric S. Raymond Eric Steven Raymond (born December 4, 1957) (often referred to by his initials, ESR) is the author of The Cathedral and the Bazaar and the present maintainer of the Jargon File (also known as The New Hackers Dictionary). Though the Jargon File established his original reputation... First Monday is a peer-reviewed journal for articles about the Internet. ... Open source refers to projects that are open to the public and which draw on other projects that are freely available to the general public. ... This does not cite any references or sources. ...

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 This article is about the book by Gamma et al. ... Erich Gamma is a co-author of the influential computer science textbook, Design Patterns. ... Richard Helm is currently with The Boston Consulting Group where he consults on the strategic application of technology to business. ... Ralph E. Johnson is co-author of the influential Computer science textbook, Design Patterns. ... John M. Vlissides (?? - 24 November 2005) was one of the four authors (refered to as the Gang of Four) of the book Design Patterns: Elements of Reusable Object-Oriented Software. ... Pearson can mean Pearson PLC the media conglomerate. ... In software engineering, a design pattern is a general repeatable solution to a commonly occurring problem in software design. ...

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. Statecharts originally invented by David Harel in 1984 are an extension to state machines. ... Prof. ... Statecharts originally invented by David Harel in 1984 are an extension to state machines. ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... In the field of software engineering, the Unified Modeling Language (UML) is a standardized specification language for object modeling. ...

Importance: Influence

Technology of Automata-based programming

• Anatoly Shalyto

• Shalyto A. Logic Control and "Reactive" Systems: Algorithmization and Programming, Automation and Remote Control, 2001, Vol. 62, No. 1, pp. 1–29.

• Shalyto A. Technology of Automata-Based Programming. CodeProject. 2004.

• Gurov V., Mazin M., Narvsky A., Shalyto A. Tools for Support of Automata-Based Programming, Programming and Computer Software, 2007, Vol. 33, No. 6, pp. 343–355.

• Kuzmin E.V., Sokolov V.A. Modeling, Specification and Verification of Automaton Programs, Programming and Computer Software, 2008, Vol. 34, No. 1, pp. 27-43.

Description: Technology of Automata-based programming is a programming techology based on a principle of using finite state machine as a description of behavior and isomorphical transformation from state machine to code. Anatoly Shalyto Anatoly Abramovich Shalyto (Russian: , May 28 1948, Leningrad, Soviet Union) — professor, doctor of science, head of the Programming Technologies Department in St. ... Fig. ...

Importance: Influence

Parallel computing

Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ...

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. Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ) was a Dutch computer scientist. ... is the 125th day of the year (126th in leap years) in the Gregorian calendar. ... Year 1968 (MCMLXVIII) was a leap year starting on Monday (link will display full calendar) of the Gregorian calendar. ...

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. Leslie Lamport Dr. Leslie Lamport (born 1941) is an American computer scientist. ... The IEEE Transactions on Computers (TC) is a monthly journal published by the IEEE Computer Society. ...

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. Richard M. Karp (born 1935) is a computer scientist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985. ...

Importance: Influence

Computer networks

A computer network is an interconnection of a group of computers. ...

A Protocol for Packet Network Interconnection

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

Description: Packet Network Interconnection. Vinton Gray Cerf (born June 23, 1943) (last name pronounced just like the English word surf) is a American computer scientist who is commonly referred to as one of the founding fathers of the Internet for his key technical and managerial role, together with Bob Kahn, in the creation of... Robert E. Kahn, (born December 23, 1938), along with Vinton G. Cerf, invented the TCP/IP protocol, the technology used to transmit information on the modern Internet. ...

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. Robert Melancton Metcalfe (born 1946 in Brooklyn, New York) is an American technology pioneer who co-invented Ethernet with David Boggs, founded 3Com and formulated Metcalfes Law. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... Ethernet is a large, diverse family of frame-based computer networking technologies that operate at many speeds for local area networks (LANs). ...

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. The Internet Protocol (IP) is a data-oriented protocol used for communicating data across a packet-switched internetwork. ... The Internet Protocol (IP) is a data-oriented protocol used for communicating data across a packet-switched internetwork. ...

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). The Transmission Control Protocol (TCP) is one of the core protocols of the Internet protocol suite. ...

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. Bruce Nelson (Bruce Jay Nelson) was well-known primarily as being inventor of the remote procedure call for computer communications. ... Remote procedure call (RPC) is a protocol that allows a computer program running on one computer to cause a subroutine on another computer to be executed without the programmer explicitly coding the details for this interaction. ...

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

Distributed computing is a method of computer processing in which different parts of a program are run simultaneously on two or more computers that are communicating with each other over a network. ...

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. Leslie Lamport Dr. Leslie Lamport (born 1941) is an American computer scientist. ... The IEEE Computer Society Press is the publishing arm of the IEEE. It publishes conference proceedings and other professional books covering computing and computer science. ... In fault-tolerant distributed computing, a Byzantine failure is an arbitrary fault that occurs during the execution of an algorithm by a distributed system. ...

Importance: Influence, Breakthrough

Impossibility of Distributed Consensus with One Faulty process

• Michael J. Fischer, Nancy Lynch, Michael S. Paterson
• Online version

Description: Impossibility to achieve consensus in asynchronous systems if one process is faulty . Professor Nancy Lynch is the NEC Professor of Software Science and Engineering, at the Electrical Engineering and Computer Science department at Massachusetts Institute of Technology. ... For other uses, see Consensus (disambiguation). ... In a synchronous system, operations are coordinated under the centralized control of a fixed-rate clock signal or several clocks. ...

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 Professor Nancy Lynch is the NEC Professor of Software Science and Engineering, at the Electrical Engineering and Computer Science department at Massachusetts Institute of Technology. ...

Importance:

The Topological Structure of Asynchronous Computability

• Maurice Herlihy, Nir Shavit
• Journal of the ACM, Vol. 46 (1999), 858-923
• Online version (PDF)

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". Maurice Herlihy is a computer scientist active in the field of multiprocessor synchronization. ... The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory (ACM SIGACT). ...

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". The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory (ACM SIGACT). ...

Importance: Influence, Breakthrough

Internet

As We May Think

• Vannevar Bush
• The Atlantic Monthly, July 1945
• As we may think from the Atlantic Monthly archives

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 Vannevar Bushs essay As We May Think, first published in The Atlantic Monthly in July 1945, argued that as humans turned from war, scientific efforts should shift from increasing physical abilities to making all previous collected human knowledge more accessible. ... Vannevar Bush (March 11, 1890 – June 30, 1974) was an American engineer and science administrator, known for his political role in the development of the atomic bomb, and the idea of the memex—seen as a pioneering concept for the World Wide Web. ... The Atlantic redirects here; for the ocean, see Atlantic Ocean. ... Year 1945 (MCMXLV) was a common year starting on Monday (link will display the full calendar). ... This article is about modern humans. ... For other uses, see Knowledge (disambiguation). ... In computing, hypertext is a user interface paradigm for displaying documents which, according to an early definition (Nelson 1970), branch or perform on request. ... The tower of a personal computer. ... WWWs historical logo designed by Robert Cailliau The World Wide Web (commonly shortened to the Web) is a system of interlinked, hypertext documents accessed via the Internet. ... Speech recognition (in many contexts also known as automatic speech recognition, computer speech recognition or erroneously as voice recognition) is the process of converting a speech signal to a sequence of words in the form of digital data, by means of an algorithm implemented as a computer program. ... The idea to build a free encyclopedia using the Internet can be traced at least to the 1993 Interpedia proposal; it was planned as an encyclopedia on the Internet to which everyone could contribute materials. ... Wikipedia (IPA: , or ( ) is a multilingual, web-based, free content encyclopedia project, operated by the Wikimedia Foundation, a non-profit organization. ...

Importance: Influence

Grapevine: An Exercise in Distributed Computing

• Andrew D. Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder
• Communications of the ACMfR, 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. Roger Needham in 1999 Roger Michael Needham (February 9, 1935 - February 28, 2003) was a British computer scientist. ... Look up Grapevine in Wiktionary, the free dictionary Grapevine can refer to several things. ...

Importance: Influence

The Design Philosophy of the DARPA Internet Protocols

• David D Clark
• Proceedings of ACM SIGCOMM '88, August, 1988.
• Online version(PDF)

Description: The DARPA Internet Protocols (TCP/IP). The Defense Advanced Research Projects Agency (DARPA) is an agency of the United States Department of Defense responsible for the development of new technology for use by the military. ... The Transmission Control Protocol (TCP) is one of the core protocols of the Internet protocol suite. ... The Internet Protocol (IP) is a data-oriented protocol used for communicating data across a packet-switched internetwork. ...

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

Description: The Anatomy of a Search Engine, known today as Google. Sergey Mikhailovich Brin (Russian: ; born August 21, 1973) is a Russian-born American entrepreneur who co-founded Google with Larry Page. ... For the music producer/manager, see Larry Page (British singer and manager). ... This article is about the corporation. ...

Importance: Influence

Programming languages

A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...

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. John Backus (born December 3, 1924) is an American computer scientist, notable as the inventor of the first high-level programming language (FORTRAN), the Backus-Naur form (BNF, the almost universally used notation to define formal language syntax), and the concept of Function-level programming. ... Fortran (previously FORTRAN[1]) is a general-purpose[2], procedural,[3] imperative programming language that is especially suited to numeric computation and scientific computing. ... For other uses, see IBM (disambiguation) and Big Blue. ... A domain-specific programming language (domain-specific language, DSL) is a programming language designed to be useful for a specific set of tasks. ... Procedural, as an adjective, refers to the concept of procedure. ... Imperative programming, as opposed to functional programming, is a sort of programming employing side-effect as central execution feature. ...

Importance: Breakthrough, Influence

Recursive functions of symbolic expressions and their computation by machine, part I

• John McCarthy.
• Communications of the ACM, 3(4):184-195, April 1960.
• Several online versions

Description: This paper introduced LISP, the first functional programming language, which was used heavily in many areas of computer science, especially in AI. LISP also has powerful features for manipulating LISP programs within the language. “LISP” redirects here. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ... // This disambiguation page covers alternative uses of the terms Ai, AI, and A.I. Ai (as a word, proper noun and set of initials) can refer to many things. ...

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. It has been suggested that ALGOL object code be merged into this article or section. ... A diagram of the operation of a typical multi-language, multi-target compiler. ... Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ) was a Dutch computer scientist. ...

Importance: Influence

Simula 67

Description: Simula 67 introduced object orientation to the field of programming languages Simula is a name for two programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard. ...

Importance: Influence

Computer architecture

A typical vision of a computer architecture as a series of abstraction layers: hardware, firmware, assembler, kernel, operating system and applications (see also Tanenbaum 79). ...

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. A Colossus Mark II computer. ... Thomas (Tommy) Harold Flowers, MBE (22 December 1905 – 28 October 1998) was a British engineer. ... Cryptanalysis (from the Greek kryptós, hidden, and analýein, to loosen or to untie) is the study of methods for obtaining the meaning of encrypted information without access to the secret information which is normally required to do so. ... Combatants Allied powers: China France Great Britain Soviet Union United States and others Axis powers: Germany Italy Japan and others Commanders Chiang Kai-shek Charles de Gaulle Winston Churchill Joseph Stalin Franklin Roosevelt Adolf Hitler Benito Mussolini Hideki Tōjō Casualties Military dead: 17,000,000 Civilian dead: 33,000... The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... This article is about the machine. ...

Importance: Topic creator, Breakthrough , Influence

First Draft of a Report on the EDVAC

• John von Neumann
• June 30, 1945, the ENIAC project.
• First Draft of a report on the EDVAC (PDF)

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. The First Draft of a Report on the EDVAC (or First Draft) was an incomplete 101-page document written by John von Neumann and distributed on June 30, 1945 by Herman Goldstine, security officer on the classified ENIAC project. ... For other persons named John Neumann, see John Neumann (disambiguation). ... is the 181st day of the year (182nd in leap years) in the Gregorian calendar. ... Year 1945 (MCMXLV) was a common year starting on Monday (link will display the full calendar). ... ENIAC ENIAC, short for Electronic Numerical Integrator And Computer,[1] was the first large-scale, electronic, digital computer capable of being reprogrammed to solve a full range of computing problems,[2] although earlier computers had been built with some of these properties. ... Design of the Von Neumann architecture For the robotic architecture also named after Von Neumann, see Von Neumann machine The von Neumann architecture is a computer design model that uses a single storage structure to hold both instructions and data. ...

Importance: Topic creator, Breakthrough , Influence

Architecture of the IBM System/360

• Gene Amdahl, Fred Brooks, G. A. Blaauw
• IBM Journal of Research and Development, 1964.
• 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. Gene Myron Amdahl (born November 16, 1922) is a Norwegian American computer architect and hi-tech entrepreneur, chiefly known for his work on mainframe computers at International Business Machines (IBM) and later his own companies, especially Amdahl Corporation. ... Frederick Phillips Brooks, Jr. ... Gerrit Anne Blaauw (male, b. ... Also Nintendo emulator: 1964 (emulator). ... System/360 Model 65 operators console, with register value lamps and toggle switches (middle of picture) and emergency pull switch (upper right). ... For other uses, see Mainframe. ... For other uses, see IBM (disambiguation) and Big Blue. ... April 7 is the 97th day of the year in the Gregorian calendar (98th in leap years). ... Also Nintendo emulator: 1964 (emulator). ... A typical vision of a computer architecture as a series of abstraction layers: hardware, firmware, assembler, kernel, operating system and applications (see also Tanenbaum 79). ...

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. Reduced Instruction Set Computer (RISC), is a microprocessor CPU design philosophy that favors a smaller and simpler set of instructions that all take about the same amount of time to execute. ... CPU design is the hardware design of a central processing unit. ... CPU design is the hardware design of a central processing unit. ... In computer science, an instruction typically refers to a single operation of a processor within a computer architecture. ...

Importance: Breakthrough , Influence

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

• DW Clark, WD Strecker
• Computer Architecture News, 1980.
• Online version(PDF)

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. CRAY-1 at the EPFL in Switzerland. ... For other uses, see Supercomputer (disambiguation). ... Seymour Roger Cray (September 28, 1925 â€“ October 5, 1996) was a U.S. electrical engineer and supercomputer architect who founded the company Cray Research. ... Cray-2 supercomputer Cray Inc. ... Los Alamos National Laboratory, aerial view from 1995. ... Year 1976 Pick up sticks(MCMLXXVI) was a leap year starting on Thursday (link will display full calendar) of the Gregorian calendar. ...

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. Gene Myron Amdahl (born November 16, 1922) is a Norwegian American computer architect and hi-tech entrepreneur, chiefly known for his work on mainframe computers at International Business Machines (IBM) and later his own companies, especially Amdahl Corporation. ... The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ...

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. Randy Katz is a Professor of Electrical Engineering and Computer Science at the University of California, Berkeley. ... For other uses, see Raid. ...

Importance: Influence

Computer graphics

This article is about the scientific discipline of 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.

• Online version(PDF)

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. Nicholas Constantine Metropolis (June 11, 1915 – October 17, 1999) was a Greek-American mathematician, physicist, and computer scientist. ... Gian-Carlo Rota (April 27, 1932 – April 18, 1999, known as Juan Carlos Rota to Spanish speakers) was an Italian-born American mathematician and philosopher. ... Academic Press (London, New York and San Diego) was an academic book publisher that is now part of Elsevier. ...

Importance:

Computer science humor

Look up Humour in Wiktionary, the free dictionary. ...

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.

• The Complexity of Songs, Knuth, Donald E. (1984). (pdf)

Description: The article capitalizes on the tendency of popular songs to evolve from long and content-rich ballads to highly repetitive "content-free" texts. Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... The Complexity of Songs was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory. ... ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... For other uses, see Song (disambiguation). ... Illustration by Arthur Rackham of the ballad The Twa Corbies A ballad is a story, usually a narrative or poem, in a song. ...

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". Prof. ...

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
• Online version

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): This is a list of important publications in different fields of science. ... This list complements the software engineering article, giving more details and examples. ... This is a list of unsolved problems in computer science. ... DBLP, a computer science bibliography site, was originally a database and logic programming bibliography site, homed at Universität Trier, in Germany, and has existed at least since the 1980s. ... // Overview The Collection of Computer Science Bibliographies is one of the oldiest (if not the oldest) bibliography collection freely accessible in the Internet. ...

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

The Edsger W. Dijkstra Prize is a prize for outstanding papers on the principles of distributed computing, named after Edsger W. Dijkstra. ... Distributed computing is a method of computer processing in which different parts of a program are run simultaneously on two or more computers that are communicating with each other over a network. ... The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory (ACM SIGACT). ... Computer science (informally, CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ... The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. ...

External links

• Lots of video lectures on Computer Science
• Most cited articles in Computer Science (Cite.Seer Database)
• 50 most influential papers ACM SIGPLAN papers published in PLDI from 1979 through 1999; organized into a special SIGPLAN proceedings.

Academic Search Engines

• Google Scholar
• CiteSeer
• Live Academic

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.