Key Papers in Computer Science  Winter 2005/6
To: Bibliography and references
Handouts and Slides
Instructor: Moni Naor
Grader:
When: Thursday 16:0018:00
Where: Ziskind 1
DESCRIPTION:
The purpose of this course is to review key papers that shaped
the intellectual development of the field of computer science.
PREREQUISITES: Students
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.
REQUIREMENTS: Students
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!
SCHEDULE:
BIBLIOGRAPHY:
 On
Computable Numbers, with an Application to the
Entscheidungsproblem
By A. M. Turing,
link
 Random Graphs:
 P. Erdos and A. Renyi, On random graphs I,
Publicationes Mathematicae 6 (1959), 290297.
 P. Erdos, Some
remarks on the theory of graphs, Bull. Amer. Math. Soc. 53
(1947)
292294.
 P. Erdos. Graph
theory and probability. Canad. J. Math., Vol.11, 1959, pp.
3438.
 NPcompleteness:
 S. A. Cook, The complexity of
theoremproving procedures, 1971 STOC,
 R.M. Karp. Reducibility among
combinatorial problems. In R.E. Miller and J.W. Thatcher,
editors,
Complexity of Computer Computations, pages 85103. Plenum Press,
1972 link
 L levin, Universal
Search
Problems. Problemy Peredatsi Informatsii 9(3):265266, 1973.
 Godel's letter to von
Neumann link
 Some review articles:
 B.A. Trakhtenbrot, A Survey of
Russian Approaches to Perebor (BruteForce Searches)
Algorithms,
IEEE Annals of the History of Computing, OctoberDecember 1984 (Vol. 6,
No. 4) pp. 384400.
 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,
NPcompleteness: A Retrospective link
 Scott Aaronson
Is P vs NP formally independent?
 Cryptography and Information Theory:
 C. Shannon, Communication Theory of
Secrecy Systems,
link
 C. Shannon, A mathematical Theory
of Communication, Bell System Technical Journal, vol.
27, pp. 379423 and 623656, July and
October, 1948. link
 Cryptography:
 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:270299, 1984. link
 First
Computers:
 First Draft of the
Report on EDVAC. John von Neumann 1946; link
 also about Weizac
 Database:
 E. F. Codd, A Relational Model of
Data for Large Shared Data Banks, Communications of the ACM,
1970 link
 E. F. Codd, Relational Completeness
of Data Base Sublanguages, 1972
 Game Theory:
 John Nash, NonCooperative 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,
Subjectivity
and correlation in randomized strategies. Journal of Mathematical
Economics, 1:6796, 1974 link to paper

Robert (Yisrael) Aumann's home page
 Computational issue: recent developments in PPADcompleteness of NashEquilibrium:
four players ,
two players
 Game Theory and Networking:
 Arrow's impossibility Theorem:
Kenneth Arrow,
A Difficulty in the Concept of Social Welfare
,
The Journal of Political Economy, 1950 328346. Also
Social
Choice and Individual Values, Wiley 1962
 Gale and Shapely, College
admissions and the stability of marriage,
American Mathematical Monthly, 1962. link
(JSTOR)

A history of the application to matching residents and hospitals
by Alvin Roth
 Networking: J. Jaffe,
Bottleneck Flow Control,
In IEEE Transactions on Communication, COM29, 1(7), pp. 954962, July
1981.
 FFT: Cooley and Tuckey An algorithm for the
machine calculation of complex Fourier series. Math.
Computation, 19:297301, 1965. link
(JSTOR)
 AI:
 A. M. Turing, Computing machinery and
intelligence  Mind Vol.59, pp 433460 link (Abelard) , link
(JSTOR)
 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
Test
 The Web:
 As We May Think.
Vannevar Bush, 1945, link
 The Anatomy of a Search
Engine by Brin and Page describing
PageRank link
 Jon Kleinberg. Authoritative
sources in a hyperlinked environment. Journal of the ACM
46(1999) link
 Physics and Computing (Feynman)
 On Simulating physics
with computers IJTP 21 1982
 There's Plenty of Room at the Bottom
link
 Scott Aaronson
NPcomplete 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 ManMonth:
Essays on Software Engineering
 Eric Raymond,
book The Cathedral and the Bazaar
Course close in nature to ours (and the inspiration
to it):
 Lecturer: Chirstos Papadimitriou, Reading the Classics,
UC Berkeley
link