Key Papers in Computer Science - Winter 2005/6
To: Bibliography and references
Handouts and Slides
Instructor: Moni Naor
When: Thursday 16:00--18:00
Where: Ziskind 1
The purpose of this course is to review key papers that shaped
the intellectual development of the field of computer science.
are expected to be familiar with algorithms, data structures,
probability theory, and linear algebra, at an undergraduate
level; a basic course in computability is assumed.
are required to present one of the papers and the background
leading to it, write a summary as well as attend all meeting,
read all papers, and participate in class discussion.
Deadline for reports: March 2nd 2006!
Computable Numbers, with an Application to the
By A. M. Turing,
- Random Graphs:
- P. Erdos and A. Renyi, On random graphs I,
Publicationes Mathematicae 6 (1959), 290--297.
- P. Erdos, Some
remarks on the theory of graphs, Bull. Amer. Math. Soc. 53
- P. Erdos. Graph
theory and probability. Canad. J. Math., Vol.11, 1959, pp.
- S. A. Cook, The complexity of
theorem-proving procedures, 1971 STOC,
- R.M. Karp. Reducibility among
combinatorial problems. In R.E. Miller and J.W. Thatcher,
Complexity of Computer Computations, pages 85--103. Plenum Press,
- L levin, Universal
Problems. Problemy Peredatsi Informatsii 9(3):265-266, 1973.
- Godel's letter to von
- Some review articles:
- B.A. Trakhtenbrot, A Survey of
Russian Approaches to Perebor (Brute-Force Searches)
IEEE Annals of the History of Computing, October-December 1984 (Vol. 6,
No. 4) pp. 384-400.
- Michael Sipser, The History and Status
of P vs. NP Question link
- Lance Fortnow, Beyond NP: the work
and legacy of Larry Stockmeyer (STOC 2005) link
- Christos Papadimitriou,
NP-completeness: A Retrospective link
- Scott Aaronson
Is P vs NP formally independent?
- Cryptography and Information Theory:
- C. Shannon, Communication Theory of
- C. Shannon, A mathematical Theory
of Communication, Bell System Technical Journal, vol.
27, pp. 379-423 and 623-656, July and
October, 1948. link
- Diffie and Hellman, New Directions in
Cryptography, IEEE Trans. on Information Theory, 1976 link
- Goldwasser and Micali, Probabilistic
Encryption. Journal of Computer and System Sciences,
28:270-299, 1984. link
- First Draft of the
Report on EDVAC. John von Neumann 1946; link
- also about Weizac
- E. F. Codd, A Relational Model of
Data for Large Shared Data Banks, Communications of the ACM,
- E. F. Codd, Relational Completeness
of Data Base Sublanguages, 1972
- Game Theory:
- John Nash, Non-Cooperative Games
, Annals of Mathematics 1951, link to paper (JSTOR)
John Nash's Homepage
Math reviews on his papers: An anemic review of the annoucnement in PNAS ,
An enthusiastic one (Gale) on the full paper
- R. J. Aumann,
and correlation in randomized strategies. Journal of Mathematical
Economics, 1:67--96, 1974 link to paper
Robert (Yisrael) Aumann's home page
- Computational issue: recent developments in PPAD-completeness of Nash-Equilibrium:
four players ,
- Game Theory and Networking:
- Arrow's impossibility Theorem:
A Difficulty in the Concept of Social Welfare
The Journal of Political Economy, 1950 328-346. Also
Choice and Individual Values, Wiley 1962
- Gale and Shapely, College
admissions and the stability of marriage,
American Mathematical Monthly, 1962. link
A history of the application to matching residents and hospitals
by Alvin Roth
- Networking: J. Jaffe,
Bottleneck Flow Control,
In IEEE Transactions on Communication, COM-29, 1(7), pp. 954-962, July
- FFT: Cooley and Tuckey An algorithm for the
machine calculation of complex Fourier series. Math.
Computation, 19:297--301, 1965. link
- A. M. Turing, Computing machinery and
intelligence - Mind Vol.59, pp 433-460 link (Abelard) , link
- Shannon: Programming a Computer
for Playing Chess, Philosophical Magazine, Ser.7, Vol. 41, No.
314, March 1950.
Reflections on the Turing Tests: Introduction Chapter
of "The Turing Test" by Stuart Shieber ,
Automated Turing Tests: Captcha ,
Verification of a human in the loop or identification via the Turing
- The Web:
- As We May Think.
Vannevar Bush, 1945, link
- The Anatomy of a Search
Engine by Brin and Page describing
- Jon Kleinberg. Authoritative
sources in a hyperlinked environment. Journal of the ACM
- Physics and Computing (Feynman)
- On Simulating physics
with computers IJTP 21 1982
- There's Plenty of Room at the Bottom
- Scott Aaronson
NP-complete Problems and Physical Reality ,
Are Quantum States Exponentially Long Vectors?
Paper on EPR: David Mermin,
Is the moon there when nobody looks? Reality and the quantum theory
- Software Engineering: Fred Brooks ,
The Mythical Man-Month:
Essays on Software Engineering
- Eric Raymond,
book The Cathedral and the Bazaar
Course close in nature to ours (and the inspiration
- Lecturer: Chirstos Papadimitriou, Reading the Classics,