Citizendia

This is a list of important publications in computer science, organized by field. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their

Some reasons why a particular publication might be regarded as important:


Contents

Computability

On computable numbers, with an application to the Entscheidungsproblem

Description: This article set the limits of computer science. It defined the Turing Machine, a model for all computations. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm On the other hand it proved the undecidability of the halting problem and Entscheidungsproblem and by doing so found the limits of possible computation. 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 In Mathematics, the Entscheidungsproblem ( German for ' Decision problem ' is a challenge posed by David Hilbert in 1928

Importance: Topic creator, Breakthrough, Influence

On certain formal properties of grammars

Description: This article introduced what is now known as the Chomsky hierarchy, a containment hierarchy of classes of formal grammars that generate formal languages. Within the field of Computer science, specifically in the area of Formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger A containment hierarchy is a Hierarchical collection of strictly nested sets. In Formal semantics, Computer science and Linguistics, a formal grammar (also called formation rules) is a precise description of a Formal A formal language is a set of words, ie finite strings of letters, or symbols.

Importance: Topic creator, Breakthrough, Influence

Finite automata and their decision problems

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

Importance: Topic creator, Breakthrough, Influence, Introduction

Decidability of second order theories and automata on infinite trees

Description: The paper presented the tree automaton, an extension of the automata. A tree automaton is a type of State machine. Tree automata deal with Tree structures rather than the strings of more conventional state machines The tree automaton had numerous applications to proofs of correctness of programs. In the context of hardware and software systems formal verification is the act of proving or disproving the Correctness of intended Algorithms underlying

Importance: Topic creator, Breakthrough, Influence, Introduction

Computability: An introduction to recursive function theory

Description: A popular textbook.

Importance: Introduction

Introduction to Automata Theory, Languages, and Computation

Description: A popular textbook. John Edward Hopcroft (born October 7, 1939) is a renowned theoretical Computer scientist. Jeffrey D Ullman (born November 22, 1942) is a renowned Computer scientist. Rajeev Motwani is a professor of Computer Science at Stanford University. Addison-Wesley is a Book publishing imprint of Pearson PLC, best known for computer books

Importance: Introduction

Computational complexity theory

Letter from Gödel to von Neumann

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

Importance: Breakthrough

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

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

Importance: Topic creator, Breakthrough

Paths, trees, and flowers

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. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources Jack R Edmonds is a Canadian --> Mathematician, regarded as one of the most important contributors to the field of Combinatorial optimization. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources For more information see.

Importance: Influence

On the computational complexity of algorithms

Description: This paper gave computational complexity its name and seed. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources

Importance: Topic creator, Breakthrough, Influence

A machine-independent theory of the complexity of recursive functions

Description: The Blum axioms. In Computational complexity theory the Blum axioms or Blum complexity axioms are Axioms which specify desirable properties of complexity measures on the

Importance: Breakthrough, Influence

The complexity of theorem proving procedures

Description: This paper introduced the concept of NP-Completeness and proved that Boolean satisfiability problem(SAT) is NP-Complete. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties Note that similar ideas were developed independently slightly later by Leonid Levin at "Levin, Universal Search Problems. Leonid Anatolievich Levin (לאוניד אנטולייביץ לוין Леонид Анатольевич Левин born November (Problemy Peredatsi Informatsii) 9(3):265-266, 1973".

Importance: Topic creator, Breakthrough, Influence

Reducibility among combinatorial problems

Description: This paper showed that 21 different problems are NP-Complete and showed the importance of the concept. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties

Importance: Influence

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

Description: The main importance of this book is due to its extensive list of more than 300 NP-Complete problems. Michael R Garey is a Computer science researcher and co-author (with David S David Stifler Johnson (born December 9, 1945) is a Computer scientist specializing in Algorithms and optimization In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties This list became a common reference and definition. Though the book was published only few years after the concept was defined such an extensive list was found.

Importance: Introduction, Influence, Latest and greatest

Theory and Applications of Trapdoor functions

Description: This paper creates a theoretical framework for Trapdoor functions and described some of their applications, like in cryptography. 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) Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" Note that the concept of trapdoor functions was brought at "New directions in cryptography" six years earlier (See section V "Problem Interrelationships and Trap Doors. ").

Importance: Topic creator, Breakthrough

How to Construct Random Functions

Description: This paper showed that the existence of one way functions leads to computational randomness. A one-way function is a function that is easy to compute but "hard to invert" (in the sense defined below

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

The Knowledge Complexity of Interactive Proof Systems

Description: This paper introduced the concept of zero knowledge.

Importance: Topic creator, Breakthrough

Algebraic methods for interactive proof systems

Description: This paper showed that PH is contained in IP. In Computational complexity theory, the Complexity class PH is the union of all complexity classes in the Polynomial hierarchy: \mbox{PH} In computational complexity theory the class IP is the class of problems solvable by an Interactive proof system.

Importance: Breakthrough

IP = PSPACE

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 Computational complexity theory, an interactive proof system is an Abstract machine that models Computation as the exchange of messages between two parties In this paper, Shamir extended the technique of the previous paper by Lund, et al. , to show that PSPACE is contained in IP, and hence IP = PSPACE, so that each problem in one complexity class is solvable in the other.

Importance: Breakthrough

Computational Complexity

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

Importance: Introduction

Interactive Proofs and the Hardness of Approximating Cliques

Probabilistic Checking of Proofs: A New Characterization of NP

Proof Verification and the Hardness of Approximation Problems

Description: These three papers established the surprising fact that certain problems in NP remain hard even when only an approximative solution is required.

Importance: Topic creator, Breakthrough, Influence

Computational Linguistics

Realization of Natural-Language Interfaces Using Lazy Functional Programming

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. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation The following is a list of the algorithms described in Wikipedia

A machine program for theorem proving

Description: The DLL algorithm. The basic algorithm for SAT and other NP-Complete problems. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties

Importance: Breakthrough, Influence

A Machine-Oriented Logic Based on the Resolution Principle

Description: First description of resolution and unification used in automated theorem proving; used in Prolog and logic programming. In Mathematical logic and Automated theorem proving, resolution is a rule of Inference leading to a refutation Theorem-proving technique In Mathematical logic, in particular as applied to Computer science, a unification of two terms is a join (in the lattice sense with respect Automated theorem proving ( ATP) or automated deduction, currently the most well-developed subfield of Automated reasoning (AR is the Prolog is a Logic programming language It is a general purpose language often associated with Artificial intelligence and Computational linguistics Logic programming is in its broadest sense the use of mathematical logic for computer programming

Importance: Topic Creator, Breakthrough, Influence

The traveling-salesman problem and minimum spanning trees

Description: The use of an algorithm for minimum spanning tree as an approximation algorithm for the NP-CompleteTravelling salesman problem. Given a connected, Undirected graph, a spanning tree of that graph is a Subgraph which is a tree and connects all the vertices together In Computer science and Operations research, approximation algorithms are Algorithms used to find approximate solutions to Optimization problems In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization. Approximation algorithms became a common method for coping with NP-Complete problems. In Computer science and Operations research, approximation algorithms are Algorithms used to find approximate solutions to Optimization problems

Importance: Breakthrough, Influence

A polynomial algorithm in linear programming

Description: For long, there was no provably polynomial time algorithm for the linear programming problem. In Mathematics, linear programming (LP is a technique for optimization of a Linear Objective function, subject to Linear equality 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). Narendra K Karmarkar (born 1957 is an Indian mathematician renowned for developing Karmarkar's algorithm. Narendra K Karmarkar (born 1957 is an Indian mathematician renowned for developing Karmarkar's algorithm. "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol 4, nr. 4, p. 373–395.

Importance: Influence

Probabilistic algorithm for testing primality

Description: The paper presented the Miller-Rabin primality test and outlined the program of randomized algorithms. 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

Description: This article described simulated annealing which is now a very common heuristic for NP-Complete problems. Simulated annealing (SA is a generic probabilistic Meta-algorithm for the Global optimization problem namely locating a good approximation to the In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties

Importance: Influence

The Art of Computer Programming

Description: This monograph has three popular algorithms books and a number of fascicles. The Art of Computer Programming is a comprehensive Monograph written by Donald Knuth that covers many kinds of Programming Algorithms Donald Ervin Knuth (kəˈnuːθ (born 10 January 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer A monograph ( Classical Greek, "One Writer" or "Single Writing") is a work of writing upon a single subject usually also by a single The algorithms are written in both English and MIX assembly language (or MMIX assembly language in more recent fascicles). MIX is a hypothetical computer used in Donald Knuth &rsquos monograph The Art of Computer Programming ( TAOCP) MMIX may also refer to the year 2009, in Roman numerals. MMIX (pronounced em-mix) is a 64-bit RISC 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. In Computer science, a low-level programming language is a language that provides little or no abstraction from a computer's microprocessor. Structured programming can be seen as a subset or subdiscipline of Procedural programming, one of the major Programming paradigms It is most famous for removing or

Importance: Influence

Algorithms + Data Structures = Programs

Description: An early, influential book on algorithms and data structures, with implementations in Pascal. Niklaus Emil Wirth (b February 15, 1934) is a Swiss computer scientist, best known for designing several Programming languages including

Importance: Influence

The Design and Analysis of Computer Algorithms

Description: One of the standard texts on algorithms for the period of approximately 1975–1985. Alfred Vaino Aho (born 9 August 1941, Timmins Ontario) is a Canadian Computer scientist. John Edward 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

Description: Explains the Whys of algorithms and data-structures. Prentice Hall is a leading educational publisher It is an Imprint of Pearson Education Inc Explains the Creative Process, the Line of Reasoning, the Design Factors behind innovative solutions.

Importance: Introduction

See Also: How to Solve It

Algorithms

Description: A very popular text on algorithms in the late 1980s. George Pólya 's 1945 Book How to Solve It is a small volume describing methods of Problem solving. Robert Sedgewick is the author of the celebrated book series Algorithms, published by Addison-Wesley. It was more accessible and readable (but more elementary) than Aho, Hopcroft, and Ullman. There are more recent editions.

Importance: Influence

Introduction to Algorithms

Description: As its name indicates this textbook is a very good introduction to algorithms. This book became so popular that it is almost the de facto standard for basic algorithms teaching.

Importance: Introduction, Influence

Algorithmic information theory

A formal theory of inductive inference

Description: This was the beginning of Algorithmic information theory and Kolmogorov complexity. Algorithmic information theory is a subfield of Information theory and Computer science that concerns itself with the relationship between computation In Algorithmic information theory (a subfield of Computer science) the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin Note that though Kolmogorov complexity is named after Andrey Kolmogorov, he said that the seeds of that idea are due to Ray Solomonoff. In Algorithmic information theory (a subfield of Computer science) the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin Andrey Nikolaevich Kolmogorov (Андрей Николаевич Колмогоров ( April 25, 1903 - October 20, 1987) was a Soviet Ray Solomonoff (born 1926 Cleveland Ohio son of Russianimmigrants invented Algorithmic Probability in 1960 Andrey Kolmogorov contributed a lot to this area but in later articles. Andrey Nikolaevich Kolmogorov (Андрей Николаевич Колмогоров ( April 25, 1903 - October 20, 1987) was a Soviet

Importance: Topic creator, Breakthrough, Influence

Algorithmic information theory

Description: A good introduction to Algorithmic information theory by one of the important people in the area. Algorithmic information theory is a subfield of Information theory and Computer science that concerns itself with the relationship between computation

Importance: Introduction

Information theory

A mathematical theory of communication

Description: This paper created communication theory and information theory. Information theory is a branch of Applied mathematics and Electrical engineering involving the quantification of Information. "A Mathematical Theory of Communication" is an influential 1948 article by Mathematician Claude E Claude Elwood Shannon (April 30 1916 – February 24 2001 an American Electronic engineer and Mathematician, is "the father of Information Bell Labs Technical Journal is the in-house journal for scientists of Bell Labs / Alcatel-Lucent. There is much discussion in the academic world of Communication as to what actually constitutes communication Information theory is a branch of Applied mathematics and Electrical engineering involving the quantification of Information.

Importance: Topic creator, Breakthrough, Introduction, Influence

Error detecting and error correcting codes

Description: In this paper, Hamming introduced the idea of error-correcting code. In Telecommunication and Information theory, forward error correction (FEC is a System of Error control for Data transmission, whereby He created the Hamming code and the Hamming distance and developed methods for code optimality proofs. In Telecommunication, a Hamming code is a linear Error-correcting code named after its inventor Richard Hamming. Examples The Hamming distance between 1011101 and 1001001

Importance: Topic creator, Breakthrough, Introduction, Influence

A Method for the Construction of Minimum Redundancy Codes

Description: The Huffman coding. History In 1951 David A Huffman and his MIT information theory classmates were given

Importance: Influence, Breakthrough

A Universal Algorithm for Sequential Data Compression

Description: The LZ77 compression algorithm. LZ77 and LZ78 are the names for the two Lossless data compression Algorithms published in papers by Abraham Lempel and Jacob Ziv in

Importance: Influence, Breakthrough

Elements of Information Theory

Description: A good and popular introduction to information theory.

Importance: Influence, Introduction

Operating systems

An experimental timesharing system. An operating system (commonly abbreviated OS and O/S) is the software component of a Computer system that is responsible for the management and coordination

Description: This paper discuss time-sharing as a method of sharing computer resource. Time-sharing refers to sharing a computing resource among many users by multitasking. This idea changed the interaction with computer systems.

Importance: Influence

The Working Set Model for Program Behavior

Description: The beginning of cache. In Computer science, a cache (kæʃ like "cash") is a collection of data duplicating original For more information see SIGOPS Hall of Fame.

Importance: Influence, Breakthrough

Virtual Memory, Processes, and Sharing in MULTICS

Description: The classic paper on the most ambitious operating system in the early history of computing. Difficult reading, but it describes the implications of trying to build a system that takes information sharing to its logical extreme. Most operating systems since Multics have incorporated a subset of its facilities.

Importance: Influence, Breakthrough

A note on the confinement problem

Description: This paper addresses issues in constraining the flow of information from untrusted programs. It discusses covert channels, but more importantly it addresses the difficulty in obtaining full confinement without making the program itself effectively unusable. The ideas are important when trying to understand containment of malicious code, as well as aspects of trusted computing.

Importance: Influence

The UNIX Time-Sharing System

Description: The Unix operating system and its principles were described in this paper. Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer An operating system (commonly abbreviated OS and O/S) is the software component of a Computer system that is responsible for the management and coordination The main importance is not of the paper but of the operating system, which had tremendous effect on operating system and computer technology.

Importance: Influence, Breakthrough

Weighted voting for replicated data

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

Description: This is the classic paper on synchronization techniques, including both alternate approaches and pitfalls.

Importance: Influence

Scheduling Techniques for Concurrent Systems

Description: Algorithms for coscheduling of related processes were given

Importance: Influence

A Fast File System for UNIX

Description: The file system of UNIX. In Computing, a file system (often also written as filesystem) is a method for storing and organizing Computer files and the data they contain to make Unix (officially trademarked as UNIX, sometimes also written as Unix with Small caps) is a computer One of the first papers discussing how to manage disk storage for high-performance file systems. Most file-system research since this paper has been influenced by it, and most high-performance file systems of the last 20 years incorporate techniques from this paper.

Importance: Influence

The Design and Implementation of a Log-Structured File System

Description: Log-structured file system. A log-structured filesystem is a File system design first proposed by John K

Importance: Influence

Microkernel operating system architecture and Mach

Description: This is a good paper discussing one particular microkernel architecture, and the benefits over more monolithic kernel approaches to system design. A microkernel is a minimal Computer Operating system kernel which in its purest form provides no operating-system services at all only the 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. Mac OS X (mæk oʊ ɛs tɛn is a line of computer Operating systems developed marketed and sold by Apple Inc, the latest of which is pre-loaded on all currently Windows NT 31, Windows NT 35, Windows NT 351, Windows NT 40, Windows 2000, Windows XP, Windows Server 2003, Windows L4 is a family of second-generation Microkernels based on theoriginal designs and implementations by German Computer scientist Jochen Liedtke.

Importance: Influence

An Implementation of a Log-Structured File System for UNIX

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. Margo I Seltzer is a researcher in the area of computer systems Keith Bostic is a Computer programmer from the United States. Marshall Kirk McKusick (b January 19, 1954 in Wilmington Delaware) is a computer scientist, known for his extensive work on BSD While "The Design and Implementation of a Log-Structured File System" was certainly the first, this one was important in bringing the research idea to a usable system. .

Importance: Influence

Soft Updates: A Solution to the Metadata Update problem in File Systems

Description: A new way of maintaining filesystem consistency.

Importance:

Databases

A relational model for large shared data banks

Description: This paper introduced the relational model for databases. A Computer Database is a structured collection of records or data that is stored in a computer system Edgar Frank "Ted" Codd ( August 23, 1923 – April 18, 2003) was a British computer scientist who while working Communications of the ACM ( CACM) is the flagship monthly Journal of the Association for Computing Machinery (ACM This model became the number one model.

Importance: Topic creator, Breakthrough, Influence

Binary B-Trees for Virtual Memory

Description: This paper introduced the B-Trees data structure. In Computer science, a B-tree is a Tree data structure that keeps data sorted and allows searches insertions and deletions in logarithmic amortized A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently This model became the number one model.

Importance: Influence

Relational Completeness of Data Base Sublanguages

Description: Completeness of Data Base Sublanguages

Importance:

The Entity Relationship Model – Towards a Unified View of Data

Description: This paper introduced the Entity-relationship diagram(ERD) method of database design. Dr Peter Pin-Shan Chen (Chinese 陳品山 is an American Computer scientist and Professor of Computer Science at Louisiana State University, who is known for the An entity-relationship model (ERM is an abstract conceptual representation of structured data

Importance: Breakthrough, Influence

SEQUEL: A structured English query language

Description: This paper introduced the SQL language .

Importance: Influence

The notions of consistency and predicate locks in a database system

Description: This paper defined the concepts of transaction, consistency and schedule. It also argued that a transaction needs to lock a logical rather than a physical subset of the database.

Importance: Breakthrough, Influence

Mining association rules between sets of items in large databases

Description: Association rules, a very common method for data mining.

Importance: Topic creator, Introduction, Influence

Principles of Transaction-Oriented Database Recovery

Description: Introduced the ACID paradigm for transactions.

Importance: Introduction, Influence

Cryptography

The index of coincidence and its applications in cryptology

Description: Presented the index of coincidence method for codebreaking. In Cryptography, coincidence counting is the technique (invented by William F

Importance: Breakthrough, Influence

Treatise on the Enigma

Description: The breaking of the Enigma. Alan Mathison Turing, OBE, FRS (ˈt(jʊ(ərɪŋ (23 June 1912 &ndash 7 June 1954 was an English Mathematician The Enigma machine is any one of a family of related electro-mechanical Rotor machines used to generate Ciphers for the Encryption and decryption of

Importance: Breakthrough, Influence

Communication Theory of Secrecy Systems

Description: Information theory based analysis of cryptography. Information theory is a branch of Applied mathematics and Electrical engineering involving the quantification of Information. The original form of this paper was a confidential Bell Labs report from 1945, not the one published.

Importance: Breakthrough, Introduction, Influence

The Codebreakers, The Story of Secret Writing

Description: Almost nothing had been published in cryptography in several decades and very few non-government researchers were thinking about it. The Codebreakers, a popular and not academic book, made many more people aware and contains a lot of technical information, although it requires careful reading to extract it. Its 1967 appearance was followed by the appearance of many papers over the next few years.

Importance: Influence

Cryptographic Coding for Data-Bank Privacy

Description: Feistel ciphers are a form of cipher of which DES is the most important. In Cryptography, a Feistel cipher is a symmetric structure used in the construction of Block ciphers named after the German IBM cryptographer Horst The Data Encryption Standard ( DES) is a Cipher (a method for Encrypting information selected by NBS as an official Federal Information 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.

Importance: Influence

Data Encryption Standard

Description: DES is not only one of the most widely deployed ciphers in the world but has had a profound impact on the development of cryptography. The Data Encryption Standard ( DES) is a Cipher (a method for Encrypting information selected by NBS as an official Federal Information Roughly a generation of cryptographers devoted much of their time to attacking and improving DES.

Importance: Influence

New directions in cryptography

Description: This paper suggested public key cryptography and presented Diffie-Hellman key exchange. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key Diffie-Hellman key exchange ( D-H) is a Cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret For more information about this work see: W.Diffie, M.E.Hellman, "Privacy and Authentication: An Introduction to Cryptography", in Proc. Bailey Whitfield 'Whit' Diffie (born June 5 1944) is a US Cryptographer and one of the pioneers of Public-key cryptography. Martin Edward Hellman (born October 2, 1945) is a cryptologist, famous for his invention of Public key cryptography in cooperation with IEEE, Vol 67(3) Mar 1979, pp 397-427.

Importance: Topic creator, Breakthrough, Introduction, Influence

On the Signature Reblocking Problem in Public Key

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 A certificate is an official Document affirming some fact For example a Birth certificate or Death certificate testifies to basic facts regarding

Importance: Topic creator, Breakthrough, Influence

Secure Communications Over Insecure Channels

Description: This paper introduced a branch public key cryptography, known as public key distribution systems. Merkle work predated "New directions in cryptography" though it was published after it. The Diffie-Hellman key exchange is an implementation of such a Merkle system. Hellman himself has argued that the more correct name would be Diffie-Hellman-Merkle key exchange.

Importance: Influence

A Method for Obtaining Digital Signatures and Public Key Cryptosystems

Description: The RSA encryption method. In Cryptography, RSA is an Algorithm for Public-key cryptography. The first public key encryption method.

Importance: Breakthrough, Influence

Using encryption for authentication in large networks of computers

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 Journal of the Association for Computing Machinery (ACM

Importance: Breakthrough, Influence

How to Share a Secret

Description: A safe method for sharing a secret.

Importance: Topic creator, Breakthrough

Data Security

Description: A paper that surveys the problems in creating secure systems. The description of database inference is particularly chilling; after reading this you'll understand why it is very difficult to publish aggregated information such as census data without accidentally exposing the private information of individuals.

Importance: influence

Security policies and security models

Description: Noninterference is the study of when interaction by one user with a system can affect what a second user sees. It can be applied to trying to stop an attacker disrupting the second user's view of the system, or to analysing whether a high-security first user can pass information to a low-level second user via a covert channel. This paper was the first to give a useful characterisation of this property.

Importance: influence

On the security of public key protocols

Description: Introduced the model of the adversary against which almost all cryptographic protocols are judged.

Importance: influence

Probabilistic Encryption

Description: The paper provides a rigorous basis to encryption (e. g. , partial information) and shows that it possible to equate the slightest cryptanalysis to solve a pure math problem. Second, it introduces the notion of Computational Indistinguishability that has and will underpin our understanding of the world, since ultimately we all are bounded computational entities.

Importance: Breakthrough, influence

Fast, rigorous factorization and discrete logarithm algorithms

Description: First published sub exponential algorithm to the Discrete logarithm problem. In Mathematics, specifically in Abstract algebra and its applications discrete logarithms are group-theoretic analogues of ordinary Logarithms The Discrete logarithm problem is the base of many cryptographic systems. In Mathematics, specifically in Abstract algebra and its applications discrete logarithms are group-theoretic analogues of ordinary Logarithms Pomerance algorithm is second chronologically to the work of Rich Schroeppel's work. Schroeppel rarely published and preferred to circulate his work to interested researchers. Schroeppel's work is referenced at Knuth, vol. 2, 2nd edition, pages 383-384.

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design

Description: This paper explains how to construct a zero-knowledge proof system for any language in NP.

Importance: Breakthrough, Influence

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

Description: Seminal paper in secure function evaluation

Importance: Breakthrough, Influence

The Digital distributed system security architecture

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

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. Kerberos is a Computer network Authentication protocol, which allows individuals communicating over a non-secure network to prove their identity to one Authentication (from Greek αυθεντικός real or genuine from authentes author is the act of establishing or confirming something (or someone as A security protocol ( cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security -related function

Importance: Influence

Differential Cryptanalysis of DES-like Cryptosystems

Description: The method of Differential cryptanalysis. Differential cryptanalysis is a general form of Cryptanalysis applicable primarily to Block ciphers but also to Stream ciphers and Cryptographic hash

Importance: Breakthrough, Influence

A new method for known plaintext attack of FEAL cipher

Description: The method of Linear cryptanalysis. 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

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

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

Importance: Breakthrough, Influence

EFF DES cracker

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. Paul Carl Kocher (born June 11, 1973) is an American Cryptographer and Cryptography Consultant, currently the 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 The Data Encryption Standard ( DES) is a Cipher (a method for Encrypting information selected by NBS as an official Federal Information In Cryptography, a key is a piece of information (a Parameter) that determines the functional output of a cryptographic algorithm The aim in doing this was to prove that DES's key is not long enough to be secure.

Importance: Breakthrough (and break code), Influence

Artificial intelligence

Computing machinery and intelligence

Description: This paper discusses whether machine can think and suggested the Turing test as a method for checking it. The Turing test is a proposal for a test of a Machine 's ability to demonstrate intelligence In a sense, this was the beginning of artificial intelligence

Importance: Topic creator, Breakthrough, Influence

A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence

Description: This summer research proposal marks the areas of research in artificial intelligence since then. Claude Elwood Shannon (April 30 1916 – February 24 2001 an American Electronic engineer and Mathematician, is "the father of Information It was a very long summer.

Importance: Influence

Fuzzy sets

Description: The seminal paper published in 1965 provides details on the mathematics of fuzzy set theory. Fuzzy sets are sets whose elements have degrees of membership

Importance: Topic creator, Influence

Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference

Description: This book introduced Bayesian methods to AI. Judea Pearl is a Computer scientist and Philosopher, best known for developing the probabilistic approach to Artificial intelligence, in

Importance: Topic creator, Influence

Artificial Intelligence: A Modern Approach

Description: The standard textbook in Artificial Intelligence. Artificial Intelligence A Modern Approach (ISBN 0-13-790395-2 (AIMA is a college textbook on Artificial Intelligence, written by Stuart J Stuart Russell (born 1962) is a computer scientist known for his contributions to Artificial intelligence. Peter Norvig is an American computer scientist. He is currently the Director of Research (formerly Director of Search Quality at Google Inc The book web site lists over 1000 colleges and universities in 93 countries using it.

Importance: Introduction, Influence

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

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

Importance:

Semi Human Instinctive Artificial Intelligence

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

Importance:

Machine learning

Language identification in the limit

Description: This paper created Algorithmic learning theory. Algorithmic learning theory (or algorithmic 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

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 Jakovlevich Chervonenkis (Алексей Яковлевич Червоненкис born 7 September 1938) is a Russian mathematician and with In Theoretical computer science, 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. In Computational learning theory, the VC dimension (for Vapnik-Chervonenkis dimension) is a measure of the Capacity of a Statistical classification

Importance: Breakthrough, Influence

A theory of the learnable

Description: The Probably approximately correct learning (PAC learning) framework. Leslie Gabriel Valiant (born 28 March 1949) is a British computer scientist and Computational theorist. Communications of the ACM ( CACM) is the flagship monthly Journal of the Association for Computing Machinery (ACM In Computational learning theory, probably approximately correct learning (PAC learning is a framework for mathematical analysis of Machine learning.

Importance: Topic creator, Breakthrough, Influence

Learning representations by back-propagating errors

Description: Development of Backpropagation algorithm for artificial neural networks. Backpropagation, or propagation of error, is a common method of teaching Artificial neural networks how to perform a given task An artificial neural network (ANN, often just called a "neural network" (NN is a Mathematical model or Computational model based on Biological neural Note that the algorithm was first described by Paul Werbos in 1974. Paul Werbos is a 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

Description: Decision Trees are a common learning algorithm and a decision representation tool. In Operations research, specifically in Decision analysis, a decision tree (or tree diagram is a decision support tool that uses a graph or Development of decision trees was done by many researchers in many areas, even before this paper. Though this paper is one of the most influential in the field.

Importance: Influence

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

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

Importance: Influence

Learning to predict by the method of temporal differences

Description: The temporal differences method for reinforcement learning. Richard S Sutton is professorof computer science and iCorechair at the University of Alberta. Inspired by related psychological theory in Computer science, reinforcement learning is a sub-area of Machine learning concerned with how an agent

Importance: Influence

Learnability and the Vapnik-Chervonenkis dimension

Description: The complete characterization of PAC learnability using the VC dimension. In Computational learning theory, probably approximately correct learning (PAC learning is a framework for mathematical analysis of Machine learning. In Computational learning theory, the VC dimension (for Vapnik-Chervonenkis dimension) is a measure of the Capacity of a Statistical classification

Importance: Breakthrough, Influence

Cryptographic limitations on learning boolean formulae and finite automata

Description: Proving negative results for PAC learning. In Computational learning theory, probably approximately correct learning (PAC learning is a framework for mathematical analysis of Machine learning.

Importance: Influence

The strength of weak learnability

Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework. In Computational learning theory, probably approximately correct learning (PAC learning is a framework for mathematical analysis of Machine learning. The proof was done by introducing the boosting method. Boosting is a Machine learning Meta-algorithm for performing Supervised learning.

Learning in the presence of malicious errors

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

Importance: Breakthrough, Influence

A training algorithm for optimum margin classifiers

Description: This paper presented support vector machines, a practical and popular machine learning algorithm. Support vector machines ( SVMs) are a set of related Supervised learning methods used for classification and regression. Support vector machines utilize the kernel trick, a generally used method. In Machine learning, the kernel trick is a method for using a Linear classifier algorithm to solve a non-linear problem by mapping the original non-linear observations

Importance: Breakthrough, Influence

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

Description: The first application of supervised learning to gene expression data, in particular Support Vector Machines. Nello Cristianini is a Professor of Artificial Intelligence at the University of Bristol and a current holder of the Royal Society-Wolfson Research Merit Award David Haussler is a Howard Hughes Medical Institute Investigator The Proceedings of the National Academy of Sciences of the United States of America, usually referred to as PNAS, is the official journal of the United Gene expression is the process by which inheritable information from a Gene, such as the DNA sequence, is made into a functional Gene product, such Support vector machines ( SVMs) are a set of related Supervised learning methods used for classification and regression. The method is now standard, and the paper one of the most cited in the area.

Importance: Breakthrough, Influence

Computer vision

The Phase Correlation Image Alignment Method

Description: A correlation method based upon the inverse Fourier transform

Importance: Influence

Determining Optical Flow

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

Importance: Influence

An Iterative Image Registration Technique with an Application to Stereo Vision

Description: This paper provides efficient technique for image registration

Importance: Influence

The Laplacian Pyramid as a compact image code

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

Importance: Influence

Snakes: Active contour models

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

Importance: Influence, topic creator

Condensation -- conditional density propagation for visual tracking

Description: A technique for visual tracking

Importance: Influence

Compilers

On the translation of languages from left to right

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.

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 characterized by having no inherited attributes LR-attributed grammars are a special type of Attribute grammars They allow the attributes to be evaluated on LR parsing.

Importance: Breakthrough, Influence

A program data flow analysis procedure

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

A Unified Approach to Global Program Optimization

Description: Formalized the concept of data-flow analysis as fixpoint computation over lattices, and showed that most static analyses used for program optimization can be uniformly expressed within this framework. Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a Computer program. In Mathematics, a fixed point (sometimes shortened to fixpoint) of a function is a point that is mapped to itself by the function In Mathematics, a lattice is a Partially ordered set (also called a poset) in which every pair of elements has a unique Supremum (the elements'

YACC: Yet another compiler-compiler

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. The Computer program yacc is a Parser generator developed by Stephen C A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another

Importance: Influence

gprof: A Call Graph Execution Profiler

SIGPLAN Notices 17, 6, Boston, MA. Marshall Kirk McKusick (b January 19, 1954 in Wilmington Delaware) is a computer scientist, known for his extensive work on BSD June 1982.

Description: The gprof profiler

Compilers: Principles, Techniques and Tools

Description: This book became a classic in compiler writing. It is also known as the Dragon book, after the (red) dragon that appears on its cover.

Importance: Introduction, Influence

Formal verification

On computable numbers, with an application to the Entscheidungsproblem

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

Importance: Breakthrough

Assigning Meaning to Programs

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

Importance: Topic creator

An Axiomatic Basis for Computer Programming

Description: Tony Hoare's paper An Axiomatic Basis for Computer Programming describes a set of inference (i. Sir Charles Antony Richard Hoare ( Tony Hoare or CAR Hoare, born January 11, 1934) is a British computer scientist, probably Communications of the ACM ( CACM) is the flagship monthly Journal of the Association for Computing Machinery (ACM e. formal proof) rules for fragments of an Algol-like programming language described in terms of (what are now called) Hoare-triples.

Importance: Breakthrough

Guarded Commands, Nondeterminacy and Formal Derivation of Programs

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. Edsger Wybe Dijkstra ( May 11, 1930 &ndash August 6, 2002; ˈɛtsxər ˈwibə ˈdɛɪkstra was a Dutch computer scientist e. post facto), programs and their formal proofs should be developed hand-in-hand (using predicate transformers to progressively refine weakest pre-conditions), a method known as program (or formal) refinement (or derivation), or sometimes "correctness-by-construction".

Importance: Topic creator

Proving Assertions about Parallel Programs

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

Importance: Breakthrough

An Axiomatic Proof Technique for Parallel Programs I

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

Importance: Breakthrough

A Discipline of Programming

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 &ndash August 6, 2002; ˈɛtsxər ˈwibə ˈdɛɪkstra was a Dutch computer scientist

Importance: Influence

Denotational Semantics

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. He originally studied Physics at Oxford University.

Importance: Introduction

The Temporal Logic of Programs

Description: The use of temporal logic was suggested as a method for formal 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

Description: The ordering of events is critical to consistency and correctness of many algorithms used in distributed computer systems. Dr Leslie Lamport (born February 7, 1941 in New York City) is an American computer scientist. This paper discusses how such ordering can be managed consistently and introduces a set of rules for managing virtual time in such systems. These rules are the basis for many subsequent algorithms for ordering events in distributed system.

Importance: Influence. It received the PODC Influential Paper Award in 2000[1]. The prize is given for outstanding papers on the principles of distributed computing whose significance and impact on the theory and/or practice of distributed computing has been evident for at least 2000 ( MM) was a Leap year that started on Saturday of the Common Era, in accordance with the Gregorian calendar.

Communicating Sequential Processes (1978)

Description: Tony Hoare's (original) Communicating Sequential Processes (CSP) paper introduces the idea of concurrent processes (i. Sir Charles Antony Richard Hoare ( Tony Hoare or CAR Hoare, born January 11, 1934) is a British computer scientist, probably e. programs) that do not share variables but instead cooperate solely by exchanging synchronous messages.

Importance: Influence

A Calculus of Communicating Systems

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 FRS (born 1934 is a prominent British Computer scientist.

Importance: Breakthrough

Software Development: A Rigorous Approach

Description: Cliff Jones' textbook Software Development: A Rigorous Approach is the first full-length exposition of the Vienna Development Method (VDM), which had 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. This page refers to the British computer scientist For other persons named Cliff Jones see Cliff Jones (disambiguation. Edsger Wybe Dijkstra ( May 11, 1930 &ndash August 6, 2002; ˈɛtsxər ˈwibə ˈdɛɪkstra was a Dutch computer scientist

Importance: Influence

The Science of Programming

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)

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 CAR Hoare, born January 11, 1934) is a British computer scientist, probably

Importance: Influence

Linear logic (1987)

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)

Description: This paper introduces the Pi-Calculus, a generalisation of CCS which allows process mobility. In Theoretical computer science, the \pi-calculus is a Process calculus originally developed by Robin Milner, Joachim Parrow and The calculus is extremely simple and has become the dominant paradigm in the theoretical study of programming languages, typing systems and program logics.

Importance: Breakthrough

The Z Notation: A Reference Manual

Description: Mike Spivey's classic textbook The Z Notation: A Reference Manual summarises the formal specification language Z which, although originated by Jean-Raymond Abrial, had evolved (principally) at Oxford University over the previous decade. Mike Spivey is a computer scientist at the University of Oxford.

Importance: Influence

Communication and Concurrency

Description: Robin Milner's textbook Communication and Concurrency is a more accessible, although still technically advanced, exposition of his earlier CCS work. Robin Milner FRS (born 1934 is a prominent British Computer scientist.

Importance: Introduction

Software engineering

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

Description: Conference of leading figures in software field circa 1968

Importance: Defined the field of Software engineering

Go To Statement Considered Harmful

Description: Don't use goto – the beginning of structured programming. Software engineering is the application of a systematic disciplined quantifiable approach to the development operation and maintenance of Software. GOTO is a statement found in many computer Programming languages It is a combination of the English words go and to In Computer science and related disciplines considered harmful is a phrase popularly used in the titles of diatribes and other critical essays (there are at least 65 such works Edsger Wybe Dijkstra ( May 11, 1930 &ndash August 6, 2002; ˈɛtsxər ˈwibə ˈdɛɪkstra was a Dutch computer scientist Communications of the ACM ( CACM) is the flagship monthly Journal of the Association for Computing Machinery (ACM Structured programming can be seen as a subset or subdiscipline of Procedural programming, one of the major Programming paradigms It is most famous for removing or

Importance: Topic creator, Influence

On the criteria to be used in decomposing systems into modules

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

Importance: Breakthrough , Influence

Hierarchical Program Structures

Description: The beginning of Object-oriented programming. Object-oriented programming (OOP is a Programming paradigm that uses " objects " and their interactions to design applications and computer programs This paper argued that programs should be decomposed to independent components with small and simple interfaces. They also argued that objects should have both data and related methods.

Importance: Breakthrough , Influence

A technique for software module specification with examples

Description: software specification.

Importance: Influence

The Emperor's Old Clothes

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

Importance: Influence

The Mythical Man-Month: Essays on Software Engineering

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

Importance: Influence

No Silver Bullet: Essence and Accidents of Software Engineering

Description: We will keep having problems with software. 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 (born April 19, 1931) is a Software engineer and Computer scientist, best-known for managing the development Computer is an IEEE Computer Society practitioner-oriented magazine issued to all members of the society . .

Importance: Influence

The Cathedral and the Bazaar

Description: Open source methodology. The Cathedral and the Bazaar (abbreviated CatB) is an essay by Eric S Eric Steven Raymond (born December 4 1957 often referred to as ESR, is a Computer programmer, author and Open source software advocate First Monday is an electronic peer-reviewed Journal for articles about the Internet. Open source is a development methodology which offers practical accessibility to a product's source (goods and knowledge A software development process is a structure imposed on the development of a software product

Importance: Influence

Design Patterns: Elements of Reusable Object Oriented Software

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

Importance: Topic creator, Influence

Statecharts: A Visual Formalism For Complex Systems

Description: Statecharts are a visual modeling method. State diagrams is a Diagram used in the field of Computer science, representing the behavior of a system which is composed of a finite number of states 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. Unified Modeling Language ( UML) is a standardized general-purpose Modeling language in the field of Software engineering.

Importance: Influence

Technology of Automata-based programming

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 Abramovich Shalyto (Анато́лий Абра́мович Шалы́то May 28 1948 Leningrad, Soviet Union) is a Russian scientist developer

Importance: Influence

Parallel computing

The Structure of "THE"-Multiprogramming System

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

Importance: Breakthrough, Influence

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

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

Importance: Breakthrough, Influence

LogP: Towards a realistic model of parallel computation

Description: The LogP framework for parallel computing was suggested. The LogP provided a way to bridge the gap between theoretical analysis of algorithm and building real world systems.

Importance: Influence

Computer networks

A Protocol for Packet Network Interconnection

Description: Packet Network Interconnection. A computer network is a group of interconnected Computers. Networks may be classified according to a wide variety of characteristics Vinton Gray "Vint" Cerf His contributions have been recognized repeatedly with honorary degrees and awards that include the National Medal of Technology, and Robert Elliot Kahn, (born December 23 1938) invented the TCP protocol and along with Vinton G

Importance: Influence

Ethernet: Distributed packet switching for local computer networks

Description: The Ethernet protocol. Communications of the ACM ( CACM) is the flagship monthly Journal of the Association for Computing Machinery (ACM Ethernet is a family of frame -based Computer networking technologies for Local area networks (LANs

Importance: Influence, Latest and greatest

End-To-End Arguments in System Design

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

Description: The Internet Protocol (IP). The Internet Protocol ( IP) is a protocol used for communicating data across a Packet-switched Internetwork using the Internet Protocol This paper describes the he Internet Protocol (IP), a fundamental protocol that drive the Internet. The Internet Protocol ( IP) is a protocol used for communicating data across a Packet-switched Internetwork using the Internet Protocol Required (but quite technical) reading for anyone who wants to understand networking.

Importance: influence

Transmission Control Protocol

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

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. Remote procedure call ( RPC) is an Inter-process communication technology that allows a Computer program to cause a Subroutine or procedure to

Importance: Influence

A Dynamic Network Architecture

Description: Network software in distributed systems.

Importance: Influence

Distributed computing

The Byzantine Generals Problem

Description: Impossibility result for distributed computing, see Byzantine failure. The IEEE Computer Society Press is the publishing arm of the IEEE.

Importance: Influence, Breakthrough

Impossibility of Distributed Consensus with One Faulty process

Description: Impossibility to achieve consensus in asynchronous systems if one process is faulty . Consensus has two common meanings One is a general agreement among the members of a given group or Community, each of which exercises some discretion in 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

Description: input/output automata

Importance:

The Topological Structure of Asynchronous Computability

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

Importance: Influence, Breakthrough

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

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

Importance: Influence, Breakthrough

Internet

As We May Think

Description: The paper argued that as humans turned from war, scientific efforts should shift from increasing physical abilities to making all previous collected human knowledge more accessible. The Internet is a global system of interconnected Computer networks As We May Think is an essay by Vannevar Bush, first published in The Atlantic Monthly in July 1945 Vannevar Bush ( March 11, 1890 &ndash June 30, 1974; pronounced "VAN-ee-var" ˈvæˌniː The Atlantic (formerly known as The Atlantic Monthly) is an American Magazine founded in Boston in 1857 Year 1945 ( MCMXLV) was a Common year starting on Monday (link will display the full calendar Human beings, humans or man (Origin 1590–1600 L homō man OL hemō the earthly one (see Humus Knowledge is defined ( Oxford English Dictionary) variously as (i expertise and skills acquired by a person through experience or education the theoretical or practical understanding As We May Think predicted many kinds of technology invented after its publication, including hypertext, personal computers, the Internet, the World Wide Web, speech recognition, and online encyclopedias such as Wikipedia

Importance: Influence

Grapevine: An Exercise in Distributed Computing

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

Importance: Influence

The Design Philosophy of the DARPA Internet Protocols

Description: The DARPA Internet Protocols (TCP/IP). The Defense Advanced Research Projects Agency (DARPA is an agency of the United States Department of Defense responsible for the development of new Technology The Transmission Control Protocol (TCP is one of the core protocols of the Internet Protocol Suite. The Internet Protocol ( IP) is a protocol used for communicating data across a Packet-switched Internetwork using the Internet Protocol

Importance: Influence

The Anatomy of a Large-Scale Hypertextual Web Search Engine

Description: The Anatomy of a Search Engine, known today as Google. Google Inc is an American public corporation, earning revenue from advertising related to its Internet search, e-mail, online

Importance: Influence

Programming languages

The FORTRAN Automatic Coding System

Description: This paper describes the design and implementation of the first FORTRAN compiler by the IBM team. Fortran (previously FORTRAN) is a general-purpose, procedural, imperative Programming language that is especially suited to International Business Machines Corporation abbreviated IBM and nicknamed "Big Blue", is a multinational Computer Technology Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing. The term domain-specific language ( DSL) has become popular in recent years in Software development to indicate a Programming language or Specification Procedural, as an adjective refers to the concept of Procedure.

Importance: Breakthrough, Influence

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

Description: This paper introduced LISP, the first functional programming language, which was used heavily in many areas of computer science, especially in AI. Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax In Computer science, functional programming is a Programming paradigm that treats Computation as the evaluation of mathematical functions and LISP also has powerful features for manipulating LISP programs within the language.

Importance: Breakthrough, Influence

ALGOL 60

Description: Algol 60 introduced block structure.

Importance: Influence

Simula 67

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

Importance: Influence

Computer architecture

Colossus computer

Description: The Colossus machines were early computing devices used by British codebreakers to read encrypted German messages during World War II. World War II, or the Second World War, (often abbreviated WWII) was a global military conflict which involved a majority of the world's nations, including Colossus was an early binary electronic digital computer. The binary numeral system, or base-2 number system, is a Numeral system that represents numeric values using two symbols usually 0 and 1. A computer is a Machine that manipulates data according to a list of instructions. The design of Colossus was later described in the referenced paper.

Importance: Topic creator, Breakthrough , Influence

First Draft of a Report on the EDVAC

Description: It contains the first published description of the logical design of a computer using the stored-program concept, which has come to be known as the von Neumann architecture. The von Neumann architecture is a design model for a stored-program Digital computer that uses a processing unit and a single separate storage structure

Importance: Topic creator, Breakthrough , Influence

Architecture of the IBM System/360

Description: The IBM System/360 (S/360) is a mainframe computer system family announced by IBM on April 7, 1964. The IBM System/360 ( S/360) is a Mainframe computer system family announced by IBM on April 7, 1964. Mainframes (often colloquially referred to as Big Iron) are Computers used mainly by large organizations for critical applications typically bulk data International Business Machines Corporation abbreviated IBM and nicknamed "Big Blue", is a multinational Computer Technology Events 529 - First draft of Corpus Juris Civilis (a fundamental work in Jurisprudence) is issued by Eastern Roman Emperor Year 1964 ( MCMLXIV) was a Leap year starting on Wednesday (link will display full calendar of the 1964 Gregorian calendar. It was the first family of computers making a clear distinction between architecture and implementation. In Computer engineering, computer architecture is the conceptual design and fundamental operational structure of a Computer system

Importance: Breakthrough , Influence

The case for the reduced instruction set computer

Description: The reduced instruction set computer( RISC) CPU design philosophy. CPU design is the Design engineering task of creating a Central processing unit (CPU a component of Computer hardware. The RISC is a CPU design philosophy that favors a reduced instruction set as well as a simpler set of instructions. CPU design is the Design engineering task of creating a Central processing unit (CPU a component of Computer hardware. In Computer science, an instruction is a single operation of a processor defined by an Instruction set architecture.

Importance: Breakthrough , Influence

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

Description:

Importance:

The CRAY-1 Computer System

Description: The Cray-1 was a supercomputer designed by a team including Seymour Cray for Cray Research. The Cray-1 was a Supercomputer designed by a team including Seymour Cray for Cray Research. A supercomputer is a Computer that is at the frontline of processing capacity particularly speed of calculation (at the time of its introduction Seymour Roger Cray ( September 28, 1925 – October 5, 1996) was a U Cray Inc ( is a Supercomputer manufacturer based in Seattle Washington. 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. Los Alamos National Laboratory (LANL (previously known at various times as Site Y, Los Alamos Laboratory, and Los Alamos Scientific Laboratory) is a Year 1976 ( 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

Description: The Amdahl's Law. Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement

Importance:

A Case for Redundant Arrays of Inexpensive Disks (RAID)

Description: This paper discusses the concept of RAID disks, outlines the different levels of RAID, and the benefits of each level. RAID — which stands for Redundant Array of Inexpensive Disks,or alternatively Redundant Array of Independent Disks (a less specific name and thus now the It is a good paper for discussing issues of reliability and fault tolerance of computer systems, and the cost of providing such fault-tolerance.

Importance: Influence

Computer graphics

The Rendering Equation

Elastically deformable models

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

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

Importance: Influence

History of computation

The Computer from Pascal to von Neumann

Description: Perhaps the first book on the history of computation. The Princeton University Press is an independent publisher with close connections to Princeton University.

Importance:

A History of Computing in the Twentieth Century

edited by:

Description: Several chapters by pioneers of computing. Gian-Carlo Rota ( April 27, 1932 &ndash April 18, 1999, known as Juan Carlos Rota Academic Press ( London, New York and San Diego) was an Academic Book Publisher that is now part of Elsevier.

Importance:

Computer science humor

The Complexity of Songs

Description: The article capitalizes on the tendency of popular songs to evolve from long and content-rich ballads to highly repetitive "content-free" texts. A song is a Musical composition. Songs contain vocal parts that are performed 'sung' and generally feature Words ( Lyrics) commonly followed A ballad is a Poem usually set to Music; thus it often is a story told in a Song.

Importance: humor is considered healthy

On Folk Theorems

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

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

How to prove it

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

Importance: When treated seriously, highly pedagogic

See also

Awards for publications (and not for general contribution):

External links

Academic Search Engines

References

  1. ^ Neiger, Gil (2003-01-23). Year 2003 ( MMIII) was a Common year starting on Wednesday of the Gregorian calendar. Events 393 - Roman Emperor Theodosius I proclaims his nine year old son Honorius co-emperor PODC Influential Paper Award: 2000. Retrieved on 2007-02-02. Year 2007 ( MMVII) was a Common year starting on Monday of the Gregorian calendar in the 21st century. Events 962 - Translatio imperii: Pope John XII crowns Otto I Holy Roman Emperor, the first Holy Roman Emperor

Further reading

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic