In Semester 2, 2015-2016, I will be teaching COL 705: Theory of Computation and Complexity Theory.
Administrative Information.
When and Where.
Classes are held on Tuesday, Wednesday and Friday 12-1 pm. Location for Tue/Fri: Bharti building, Room 204. Location for Wed: Bharti 425.
Office Hours and Teaching Assistants.
The teaching assistants for the course are listed below. Please email them for setting up meeting times. I do not hold fixed office hours but will be happy to meet you anytime, just drop me an email!
- Ishaan Preet Singh. Email:cs5110280@cse.iitd.ac.in
- Aditya Ahuja. Email:aditya.ahuja@cse.iitd.ac.in
Pre-requisites.
Data Structures (equivalent of COL106) and (undergraduate) Theory of Computation (equivalent of COL 352).
Requirements.
- Homeworks (4): 20%.
- Minor 1 and 2: 20% each.
- Major Exam: 35%
- Class Participation: 5%
Policies and Grades.
Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help
you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning grades.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class.
Lecture Notes and Handouts.
We will follow the text
Computational Complexity: A Modern Approach by Barak and Arora. The specific portions that we will cover will be announced on a per-class basis, but a tentative list of topics is below.
- Introduction, Review of Automata Theory, Time Complexity, P and NP, NP Completeness.
- Time Hierarchy theorems, Ladner's theorem, Diagonalization and its limits.
- Space Complexity, Savitch's theorem, PSPACE completeness.
- NL completeness, NL=co-NL, Polynomial hierarchy.
- Boolean circuits: non-uniform and uniform circuit complexity.
- Randomized Computation.
- The power of interaction: IP, IP=PSPACE, Arthur Merlin, MIP.
- PCP and hardness of approximation, quantum computation, cryptography
Here are topics that we covered in class, and slides/notes that we used.
- Lec 1 (Jan 4): Introduction to computation, complexity, questions we will study and open problems in the area. Also, class policies, grading scheme. Slides were used and are available here.
- Lec 2 (Jan 5): Recap: Automata theory. Slides were used and are available here.
- Lec 3 (Jan 8): Turing machines: definition and the construction of a universal turing machine. A good reference for the material is here.
- Lec 4 (Jan 12): DTIME, NTIME, P, NP. Slides were used and are available here.
- Lec 5 (Jan 15): NP Completeness. Slides are available here.
- Jan 18, Jan 19: No class, instructor not well. We will hold a makeup class later.
- Lec 6 (Jan 22): Deterministic time hierarchy theorem. Good lecture notes are here.
- Lec 7 (Jan 25): Non deterministic time hierarchy theorem. Good lecture notes are here.
- Jan 26: No class. Happy republic day!
- Lec 8 (Jan 27) (Make-up class for Jan 18) Ladner's theorem for existence of NP intermediate language. Good lecture notes are here and here.
- Lec 9 (Jan 29): Finishing proof of Ladner's theorem. Start limits of diagonalization.
- Lec 10 (Feb 2): Show that the P versus NP question cannot be resolved using arguments that relativize. A good reference is here.
- Lec 11, 12 (Feb 3 and 5):Finishing proof from last time. Started space complexity. Definitions of important classes, proof that TQBP is PSPACE complete. A good reference is here.
- Lec 13 (Feb 9): Problem solving session in preparation for the minor.
- Feb 10, Feb 12: No class due to Minor 1.
- Lec 13, 14 (Feb 16, 17): More on Space Complexity: NL and NL completeness. PATH is NL complete, NL \subset P, Savitch's theorem. The Immerman-Szelepcsenyi Theorem (NL=coNL). A good reference is here.
- Lec 15 (Feb 19): Polynomial Hierarchy. Discussion of MAX-IND-SET, MIN-CNF. Generalisation of NP and co-NP, definition of Sigma_i and Pi_i. Proof that hierarchy collapses if \Sigma_i = \Pi_i. A good reference is here.
- Lec 16 (Feb 23): More on Polynomial Hierarchy. Oracle machines, and alternating Turing machines. Slides are available here and here.
- Lec 17 (Feb 24): Finishing up polynomial hierarchy. Returning graded Minor 1 and discussing solutions.
- Mid Semester Break.
- Lec 18 (Mar 8): Introduction to non-uniform computation. Definition and motivation for Boolean circuits. The Power of Boolean circuits (any function can be computed by a Boolean circuit). Proof that every function is in SIZE(n 2^n). A good reference is here.
- Lec 19 (Mar 9): Proof that there exists a function that cannot be computed by a circuit of size (1-\epsilon) n/2^n. Two alternate definitions of P/poly, using circuits and non uniform TMs. A good reference is here.
- Lec 20 (Mar 11): Discuss two definitions of non-uniform TMs. Argued that they are equivalent. Proved that TIME(t(n)) \subseteq SIZE(T(n) log(T(n)). A good reference is here. Started Karp-Lipton Theorem that if NP \in P/poly, then \Sigma_2 = \Pi_2. A good reference is here.
- Lec 21 (Extra class, Mar 14): Finish Karp Lipton Theorem. Begin circuit lower bounds. Show that Threshold function T_n^k needs a circuit of size at least 2n-4. A good reference is here. Another referene is Theorem 2.5 in the book Algorithms and Complexity by Gerard Meurant.
- Lec 22, 23 (Mar 15 and 16): Define NC, AC classes. Parity Lower bound. A good reference is here.
- Lec 24 (Mar 18: ) Problem solving session in preparation for Minor 2.
- Break for Minor 2. Good luck!
- Lec 25, 26 (Mar 29, 30): Randomized time complexity. Definitions of RP, BPP, ZPP. Probability amplification of BPP. Randomized algorithms: polynomial identity testing, perfect matching in bipartite graphs. Useful notes are here.
- Lec 27 (Apr 1): BPP is in P/Poly. BPP is in Sigma_2 intersect Pi_2. Useful notes are here.
- Apr 5: No class. Will hold makeup class later.
- Lec 28, 29 (Apr 6 and 8): Why BPP does not have natural complete problems. Randomized space complexity. Definitions of RL, BPL. Discuss solutions for Minor 2. Useful notes are here.
- Lec 30 (Apr 12): Show that undirected connectivity UCONN is in RL. Description of randomized algorithm. Useful notes are here and here.
- Lec 31 (Apr 13): Complete analysis of UCONN \in RL. Discuss randomized algorithm for 2SAT. Useful notes are here.
- Lec 32 and 33 (Apr 18 and 19): Interactive proofs. Discussion of how randomization and communication help. Proof system for BPP with perfect completeness. Graph Non-isomorphism is in IP. Public coin proof systems. Useful notes are here.
- Lec 34 (Apr 22): Graph Non-isomorphism is in AM. Useful notes are here.
- Lec 35 (Apr 25): Co-NP is in IP. Useful notes are here.
- Lec 36 and Lec 37 (Apr 26 and 29): IP=PSPACE. Useful notes are here.
That's it folks! Good luck for the exam :).
Reading Material and References.
The textbook for the course is
Computational Complexity: A Modern Approach by Barak and Arora.
The following are useful additional references:
- Lecture notes by Luca Trevisan. See also these.
- Lecture slides by Manoj Prabhakaran.
- Lecture notes by Sandeep Sen.
- Lecture notes by Jon Katz.
- Helpful overview slides.
Homeworks.