CS 505 Computability and Complexity Theory
Spring, 2020
Time and location:
Monday, Wednesday and Friday 2:00-2:50pm, ARC 239
Intructor:
Anastasios Sidiropoulos,
sidiropo@uic.edu,
office hours: TBA
Overview
This course discusses fundametal concepts in compatability and complexity theory. The topics covered include models of computation, undecidability, polynomial-time computation and the classes P and NP, diagonalization, space complexity and the classes PSPACE and NL, the polynomial hierarchy, circuit complexity, randomized computation, interactive proofs, cryptography, quantum computation, and hardness of approximation.
The standard prerequisite course is CS 301 or an equivalent one.
The course will also require general mathematical maturity (i.e. the ability to read and write proofs).
No other special background will be necessary.
Textbooks
Evaluation
There will be one midterm, a final exam, and several homeworks.
The final exam will be comprehensive.
Each homework will be due before the beginning of a predetermined lecture.
No late assignments will be accepted.
The final score is computed using the formula: 0.35 × homeworks + 0.3 × midterm + 0.35 × final.
The final letter gades will be curved.
Lectures
-
Jan 13, 2020. Lecture 1: Introduction. Turing machines (Chapter 1).
-
Jan 15, 2019. Lecture 2: Universal Turing machines (Chapter 1).
-
Jan 17, 2019. Lecture 3: Uncomputability (Chapter 1).
-
Jan 22, 2019. Lecture 4: The classes P and NP (Chapter 2).
-
Jan 24, 2019. Lecture 5: Polynomial time reductions, NP-completeness (Chapter 2).
-
Jan 27, 2019. Lecture 6: The Cook-Levin theorem (Chapter 2).
-
Jan 29, 2019. Lecture 7: The Cook-Levin theorem (cont.).
-
Jan 31, 2019. Lecture 8: Diagonalization. Time and space hierarchies (Chapter 3).
-
Feb 3, 2020. Lecture 9: Nondeterministic time hierarchy (Chapter 3).
-
Feb 5, 2020. Lecture 10: Ladner's Theorem. Oracle machines (Chapter 3).
-
Feb 7, 2020. Lecture 11: Space complexity. PSPACE completeness (Chapter 4).
-
Feb 10, 2020. Lecture 12: PSPACE-completeness of TQBF. Savitch's theorem (Chapter 4).
-
Feb 12, 2020. Lecture 13: NL (Chapter 4).
-
Feb 14, 2019. Lecture 14: The polynomial hierarchy (Chapter 5).
-
Feb 17, 2019. Lecture 15: The polynomial hierarchy (cont.).
-
Feb 19, 2020. Lecture 16: Circuit complexity. P/poly (Chapter 6).
-
Feb 21, 2020. Lecture 17: Circuit lower bounds (Chapter 6).
-
Feb 24, 2020. Lecture 18: NC and AC (Chapter 6).
-
Feb 26, 2020. Lecture 19: Circuits and the polynomial hierarchy (Chapter 6).
-
Feb 28, 2020. Lecture 20: Randomization. BPP, RP, coRP, ZPP (Chapter 7).
-
Mar 2, 2020. Lecture 21: Sipser-Gacs Theorem (Chapter 7).
-
Mar 4, 2020. Lecture 22: Average-case complexity (Chapter 18).
-
Mar 6, 2020. Lecture 23: distP (Chapter 18).
-
Mar 9, 2020. Lecture 24: distNP (Chapter 18).
-
Mar 11, 2020. Lecture 25: Fine-grained average-case complexity.
-
Ball M, Rosen A, Sabin M, Vasudevan PN. Average-case fine-grained hardness. STOC 2017.
-
Mar 13, 2020. Lecture 26: Fine-grained average-case complexity (cont.).
-
Mar 16, 2020. Lecture 27: Fine-grained average-case complexity (cont.).
-
Mar 30, 2020. Lecture 28: Fine-grained average-case complexity (cont.).
-
Apr 1, 2020. Lecture 29: Cryptography.
-
Apr 3, 2020. Lecture 30: Cryptography.
-
Apr 6, 2020. Lecture 31: Cryptography.