CS 505 Computability and Complexity Theory
Spring, 2019
Time and location:
Monday, Wednesday and Friday 2:002:50pm, Thomas Beckham Hall (TBH), Room 180E
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, polynomialtime 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 14, 2019. Lecture 1: Introduction. Turing machines (Chapter 1).

Jan 16, 2019. Lecture 2: Universal Turing machines. Uncomputability (Chapter 1).

Jan 18, 2019. Lecture 3: The classes P and NP (Chapter 2).

Jan 23, 2019. Lecture 4: Polynomial time reductions, NPcompleteness (Chapter 2).

Jan 25, 2019. Lecture 5: The CookLevin theorem (Chapter 2).

Jan 28, 2019. Lecture 6: Diagonalization. Time and space hierarchies (Chapter 3).

Feb 1, 2019. Lecture 7: Nondeterministic time hierarchy (Chapter 3).

Feb 4, 2019. Lecture 8: Ladner's Theorem. Oracle machines (Chapter 3).

Feb 6, 2019. Lecture 9: Space complexity. PSPACE completeness (Chapter 4).

Feb 8, 2019. Lecture 10: PSPACEcompleteness of TQBF. Savitch's theorem (Chapter 4).

Feb 11, 2019. Lecture 11: NL (Chapter 4).

Feb 13, 2019. Lecture 12: The polynomial hierarchy (Chapter 5).

Feb 15, 2019. Lecture 13: Circuir complexity. P/poly (Chapter 6).

Feb 18, 2019. Lecture 14: Circuit lower bounds (Chapter 6).

Feb 20, 2019. Lecture 15: NC and AC (Chapter 6).

Feb 22, 2019. Lecture 16: Circuits and the polynomial hierarchy (Chapter 6).

Feb 25, 2019. Lecture 17.

Feb 27, 2019. Lecture 18.

Mar 1, 2019. Lecture 19.

Mar 4, 2019. Lecture 20.

Mar 6, 2019. Lecture 21.

Mar 8, 2019. Lecture 22. IP = PSPACE.

Mar 11, 2019. Lecture 23.

Mar 13, 2019. Lecture 24.

Mar 15, 2019. Lecture 25.

Mar 18, 2019. Lecture 26.

Mar 20, 2019. Lecture 27. Cryptography.

Mar 22, 2019. Lecture 28. Cryptography.

Apr 1, 2019. Lecture 29. Cryptography.

Apr 3, 2019. Lecture 30. Quantum computing. Basic definitions.

Apr 5, 2019. Lecture 31. Quantum computing.