## 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.
• Check this web page regularly for announcements.
• Previous versions of this course: 2011, 2009, 2008, 2006, 2005, 2004, 2003, 2002.

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