CS294-17:  Reading the Classics

Instructor:  Christos H. Papadimitriou
Soda 689,  christos@cs, (510) 642-1559

Office Hours:  Mondays and Thursdays 5-6pm, and by appointment

Meets:  Tuesdays 3:00-5:00pm, in Soda 310.

Units:  two. See me for ways to take it for 4 units.

Course  Format:  Presentations by participants and discussion. 

Course Requirements:

Attend all meetings, read all papers, and participate in the discussion. 

Present (possibly in a group) one of the classics, and write a paper about it (including a summary of the presentation and the discussion).

Examples of classics: 

• Euler's paper on the Konigsberg bridges; do you know of a translation?  (or Latin?)
• On computable numbers, with an application to the Entscheidungsproblem. Alan Turing 1936
• As We May Think. Vannevar Bush, 1945
• First Draft of the Report on EDVAC. John von Neumann 1946
• A Mathematical Theory of Communication. Claude E. Shannon 1948
• The Turing Test paper, Alan Turing 1950
• Non-Cooperative Games.  John Nash, 1951
• Letter from Gödel to von Neumann, 1956; see J. Hartmanis's "Godel, von Neumann and the P=?NP problem," Bulletin of the European Association for Theoretical Computer Science (EATCS), 38 (1989), pp. 101--107.

• Edmonds, Jack , Paths, trees, and flowers, Canadian Journal of Mathematics, Vol 17, No -, 449-467, 1965
• Three papers on 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; and  Levin, Universal Search Problems. [Problemy Peredatsi Informatsii] 9(3):265-266, 1973 (c). Annals of the History of Computing 6(4):384-400, 1984.

• Two papers on the relational model
• A Relational Model of Data for Large Shared Data Banks. E. F. Codd 1970
• Relational Completeness of Data Base Sublanguages. E. F. Codd, 1972
• New Directions in Cryptography, Diffie and Hellman, 1976
• Simulating physics with computers. Feynman, IJTP 21 1982

Readings in the philosophy and history of science

First Two Meetings: I talked about Godel's Theorem and the Birth of the Computer . For Gödel’s paper see this translation.

Third Meeting, September 4: I talked about Turing’s paper on computable numbers.

Fourth Meeting, September 11: Greg Valiant and Thomas Vidick presented Feynman’s paper, as well as a subsequent paper by Deutsch .

Fifth Meeting, September 18: Bryce Lee, Tracy Wang, David Poll and Krish Eswaran presented Nash's paper

Sixth Meeting, September 25: James Cook, Sridhar Ramesh, and Jimmy Yang presented Shannon's Mathematical Theory of Communication

Seventh Meeting, October 2: Juliet Rubinstein and Jessica Schoen presented Edmonds’ paper

No meeting October 9

Eighth meeting, October 16: Scott Beamer and Ari Rabkin told us about New Directions in Cryptography, Diffie and Hellman, 1976

Ninth meeting, October 23: John McKernan told us about the Antikythera mechanism (here are three papers )

Tenth meeting, October 30: Danielle Cassley and Ephrat Biton spoke on As We May Think. Vannevar Bush, 1945

Eleventh meeting, November 6: Albert Chae, Christos Stergiou and Vishal Talwar presented John McCarthy's Lisp paper

Twelfth meeting, November 13: Yaron Singer and Jacob Burnim spoke about the origins of graph theory and some recent developments, here is Euler's paper in translation and a survey (they’ll cover sections 4 and 6)

Thirteenth meeting, November 20 Tyson Condi, Eirinaios Michelakis, and Daisy Wang will tell us about the beginnings of relational databases

Fourteenth meeting, November 27 Benjamin Culpepper and Dan will tell us about NP-completeness (the papers by Cook, Karp, Levin, Gödel’s letter, etc.)

Fifteenth meeting, December 4 We will discuss two classics that we ended up not covering: The Turing Test paper and von Neumann’s EDVAC report.

Sixteenth meeting, possibly December 6 (a Thursday, and in room 380!) Lorenzo Orecchia and Alexandre Staufer will tell us about linear programming. here is a list of readings.

Please take the time to read the papers!