CAS 705: Computability and Complexity
Fall 2013

• Instructor: Michael Soltys, email: soltys@mcmaster.ca
• Course Outline
• Lectures: Wednesdays, 9:00-12:00, in ITB-222. First lecture on September 11th.
• Course outline: This course is an introduction to the topics of computability and computational complexity. We are going to start with languages, alphabets and basic computational models, such as automata and grammars. We are going to present fundamental results in computability, such as the Turing Halting problem. Finally, we are going to examine the foundations of complexity: the P vs NP problem, the Polynomial Time Hierarchy, etc. Throughout the course, we are going to emphasize the connections between computability/complexity and logic.
• Textbook:

  Michael Soltys. An introduction to computational complexity [Click here for a sample] 2009 Published by the Jagiellonian University Press.

• Check this web page regularly for announcements.
• Previous versions of this course: 2011, 2009, 2008, 2006, 2005, 2004, 2003, 2002.
• Please Read: McMaster Academic Integrity Statement.

Announcements:

• Dec 6: Two very useful papers.
• Nov 29: The take home exam has bee revised: here is the new version (this is now the same PDF as the one below, in the Assignments section).
• Nov 28: On December 4th we have four presentations; this means that I will only lecture on the seminal result of Immerman-Szelepcsényi, i.e., the Inductive Counting Technique. On December 11th we have only one presentation, so I will dedicate the lecture to cryptography/security.
• Nov 27: The solutions to assignment 3 have been posted below, and so has the final take home exam.
• Nov 21: For assignment 3, in problem 1, you have to answer in one of two ways: the given problem is polytime, or it is not. If it is, give a polytime algorithm, if it is not, provide a justification (such NP-hardness, under the assumption that P is not equal to NP), or that the problem is undecidable (in which case it is definitely not polytime).
• Nov 5: Assignment 3 has been posted below; this assignment explores the P versus NP problem. It is due on November 27th, at the beginning of the lecture, since we will discuss the solutions the same day.
• Nov 5: Remember that assignment 2 is due tomorrow, at the beginning of the lecture. We are going to hand out and discuss the solutions. We are going to finish chapter 10 tomorrow.
• Oct 22: On Oct 23, lecture number 7, we are going to finish talking about recursive functions and their relationship with URIMs, and we are going to start covering chapter 10, P and NP.
• Oct 18: I finished grading A1 and I will return it in class on Wednesday Oct 23.
• Oct 18: Remember that there is no lecture on Oct 30; we will make up for it with an extra lecture on Dec 11.
• Oct 9: Assignment 1 has been reposted with solutions; assignment 2 has been posted below.
• Sept 27: On October 9th, the class will be from 9:30 until 11:30, since we have faculty candidates visiting the department — I will be hosting them.
• Sept 12: The first assignment has been posted below.
• Sept 12: The first class too place yesterday, Sept 11th; our next class is Sept 18th.

Assignments and Exam:

• First assignment (with solutions), due on October 9th in class.
• Second assignment, due on Nov 6th in class.
• Third assignment, due on Nov 27th in class.
• Final Exam, take home, due Dec 11 in class (Revised on Nov 29, 2013).
• Papers for presentations

  Name	First Presentation	Second Presentation
  Neerja Pophli	A new approach to non-repetitive sequences on Sept 25	Unshuffling a Square is NP-Hard as the 2nd presentation, on November 27th
  Yasmine Sharoda	A short proof of the pigeonhole principle using resolution, on Oct 2	Are there hard examples for Frege systems, on Nov 20
  Robert Fuller	Cook's paper on P vs NP, on Oct 16	Propositional proof complexity: Past, present, and future by Beame and Pitassi on December 4
  Simon Broadhead	The Status of the P versus NP Problem by Fortnow, on Oct 16	On the hardness of graph isomorphism by Jacobo Toran on December 11
  Dhruv Gairola	F. Borneman, PRIMES is in P: A breakthrough for "Everyman" on October 23	A theory of the learnable by L.G. Valiant, on November 13
  Raazia Shafqat	Boolean Satisfiability, on October 2	Probabilistically Checkable Proofs by Madhu Sudan, on December 4
  Mohammed Alabbad	The History and Status of the P versus NP Question by Michael Sipser, on Oct 16	Section 5 of The complexity of propositional proofs by Alasdair Urquhart, on December 4
  Zhipeng Hu	Kolmogorov Complexity on Oct 2	Propositional Proof Complexity: An Introduction by Sam Buss, on Nov 20
  Musa Al-hassy	A constructive proof of the general Lovasz Local Lemma by Moser and Tardos on Nov 20	IP=PSPACE, Chapter 11, section 3, in the textbook. This is an important result about protocols, and a good introduction to cryptography; December 4