CAS 705: Computability and Complexity
Fall 2008

• Instructor: Michael Soltys, email: my last name at mcmaster.ca
• Course Information (Revised Sept 4)
• Lectures: Tuesday and Thursday 17:30-19:00, in ITB-222.
• Course outline: The relationship between problems, algorithms, and languages. Computability: finite automata, rewriting systems, Turing machines (linear speedup, robustness, and the Universal Turing machine). Recursive functions and Cobham's Theorem. Determinism and non-determinism. Recursive and recursively enumerable languages. The Halting problem and the diagonalization technique. Church-Turing thesis, and Rice's theorem. Complexity: classes defined in terms of time, space, and circuits. Uniformity. The reachability method (Savitch's theorem, and the Immerman-Szelepscenyi theorem). The P versus NP problem (and Cook's Theorem), reductions and completeness. The Time and Space Hierarchy Theorems. Randomized and parallel computations. NP and co-NP, propositional proof systems, and Horn clauses. Kolmogorov complexity, and the Shannon principle. This year the course will also contain a substantial component of cryptography and logic.
• Textbook: An introduction to computational complexity, by Michael Soltys. See the preface and table of contents.
• Check this web page regularly for announcements.
• Previous versions of this course: 2006, 2005, 2004, 2003.
  This course was also taught in 2002 as cas776 -- Fall 2002.
• Please Read: McMaster Academic Integrity Statement.

Announcements:

• Nov 22: A new set of notes, on public key cryptography, has been posted below.
• Nov 14: New notes have been posted below (a set of notes on the Rabin-Miller algorithm and its correctness, as well as a set of notes with some Number theory and Group theory background).
• Nov 14: For a free implementation of PGP (“Pretty Good Privacy”) that was mentioned in class, go to GnuPG. This is nice, since you can see all the ideas mentioned in class actually implemented.
• Nov 14: Here are some important changes:
  • Test 5 is canceled--the exam is the week after.
  • The November 18th lecture, when Test 5 was originally supposed to take place, is also cancelled, and instead we are going to have an extra lecture on December 2, same time and place. As this lecture is after the exam, I will use it to talk about “what else is there in complexity.”
  • The final exam will be on November 27 as planned. The exam is only going to cover cryptography, that is, the material starting on October 30. As Test 5 is canceled, the exam will be worth 40% of the course, another 40% for the tests, and 20% for attendance.
  • I have started writing up some notes on the cryptography material, which I am going to post as soon as they are ready. As always, I will appreciate your feedback. Please, email me if you have any concerns and questions regarding these changes!
• Oct 31: Last day of classes is Monday December 1. Thus we have 8 more lectures before the end of term. We need to write two more tests, and the final exam (on the last day). So I propose the following schedule; let me know if there are problems:
  • Thursday Nov 6: Test 4
  • Tuesday Nov 18: Test 5
  • Thursday Nov 27: Final Exam (5:30-7:00, i.e., usual lecture time)
• Oct 24: We start Cryptography on Thursday October 30.
• Oct 24: Test 3 will take place on Tuesday, October 28. The test will cover chapter 4, SPACE, but you are not responsible for Theorem 4.10 and section 4.3.2. Make sure that you have the latest version of the chapter (October 24).
• Oct 9: Recall that I am giving a talk on Tuesday: October 14, 16:30-17:30, ITB 201:

  Title: An overview of cryptography

  In this talk we are going to take a bird-eye view of cryptography, from a computational perspective. That is, rather then examine cryptographic protocols, we are going to look at the mathematical principles behind the algorithms used in cryptography. First RSA, ElGamal, and the Rabin-Miller algorithm, then algorithms in Elliptic-curve based cryptography, and finally we will end with lattice-based cryptography. No background will be assumed.

• Oct 7: Test 2 will take place on Thursday October 16.
• Oct 6: Here are a few comments:
  • The tests are marked and will be returned tomorrow (Tuesday, Oct 7)--the tests were well written.
  • We need to schedule Test 2, and we have two possibilities: (i) this Thursday (Oct 9) or (ii) next Thursday (Oct 16). The advantage of the former is less material, and the advantage of the latter is delay. I propose (i), but we can discuss it in class tomorrow.
  • Next Tuesday (Oct 14) instead of the lecture, I am going to give an overview presentation of cryptography at 4:30 in the optimization seminar.
  • Chapter 4 notes (SPACE) have been posted below.
• Sept 20: On October 14, instead of the 5:30 lecture, we shall meet at the Optimization Seminar at 4:30 where I will present an overview of cryptography.
• Sept 18: The first test will take place on Thursday Sept 25. It will cover chapter 1 only.
• Sept 4: Note the slight change of lecture times; no lectures on Mondays, but we start half an hour earlier on Tuesday and Thursday. Thus, the lectures are Tuesdays and Thursdays 17:30-19:00 in ITB-222.
• Sept 4: An excellent way to participate in the course (but not the only one!) is to point out mistakes in my book ;)
• Sept 2: The first meeting will be on Thursday Sept 4, at 18:00 in ITB-222.

Lecture Notes:

• Chapter 1: Preface
• Chapter 2: Turing machines (Revised Sept 22)
• Chapter 3: P and NP (Revised Sept 22)
• Chapter 4: Space (Revised Oct 24)
• Primality (part of chapter 8)
• Number theory and group theory background
• Public Key Cryptography (new!) (Revised Nov 24)

Tests:

• Test 1 (September 25)
• Test 2 (October 16)
• Test 3 (October 28)
• Test 4 (November 6)