Key Papers in Computer Science - Winter 2005/6
To: Bibliography and references
Handouts and Slides
Instructor: Moni Naor
Grader:
When: Thursday 16:00--18: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), 290--297.
- P. Erdos, Some
remarks on the theory of graphs, Bull. Amer. Math. Soc. 53
(1947)
292-294.
- P. Erdos. Graph
theory and probability. Canad. J. Math., Vol.11, 1959, pp.
34--38.
- NP-completeness:
- 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,
editors,
Complexity of Computer Computations, pages 85--103. Plenum Press,
1972 link
- L levin, Universal
Search
Problems. Problemy Peredatsi Informatsii 9(3):265-266, 1973.
- Godel's letter to von
Neumann link
- Some review articles:
- B.A. Trakhtenbrot, A Survey of
Russian Approaches to Perebor (Brute-Force Searches)
Algorithms,
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
Secrecy Systems,
link
- C. Shannon, A mathematical Theory
of Communication, Bell System Technical Journal, vol.
27, pp. 379-423 and 623-656, 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:270-299, 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, 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,
Subjectivity
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 ,
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 328-346. 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, COM-29, 1(7), pp. 954-962, July
1981.
- FFT: Cooley and Tuckey An algorithm for the
machine calculation of complex Fourier series. Math.
Computation, 19:297--301, 1965. link
(JSTOR)
- AI:
- A. M. Turing, Computing machinery and
intelligence - Mind Vol.59, pp 433-460 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
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
to it):
- Lecturer: Chirstos Papadimitriou, Reading the Classics,
UC Berkeley
link