CSCE-637 Complexity Theory (Fall 2020)

Course Syllabus

Textbook
Christos H. Papadimitriou: Computational Complexity, 2nd ed., Addison-Wesley, 1994.

Supplementary Reading Materials

M. Find, et al.: A better-than-3n lower bound for the circuit complexity of an explicit function

A. Borodin, et al.: Parallel computation for well-endowed rings and space-bounded probabilistic machines

R. Williams: Nonuniform ACC circuit bounds

M. Agrawal, et al.: PRIMES is in P

Lecture Notes 1: Immerman-Szelepcsenyi Theorem

Lecture Notes 2: The classes BPP and P/poly

Lecture Notes 3: Karp-Lipton Theorem

Lecture Notes 4: Baker-Gill-Solovay Theorem

Lecture Notes 5: Tight bound on Johnson's algorithm for maximum satisfiability

R. O'Donnell: A history of the PCP Theorem

Schedule
(Lecture videos are available in the Zoom cloud)

Date	Topics	Slides	Book Sections	Quiz and Assignments
Aug. 20	Introduction	Slides	Chapter 1
Aug. 25	Turing machines, time and space	Slides	Chapter 2
Aug. 27	Halting problem, nondeterminisim	Slides	Sections 2.7, 3.1, 3.2
Sept. 1	Nondeterministic computation	Slides	Sections 2.7, 9.1
Sept. 3	Reductions and completeness	Slides	Sections 8.1, 8.2	Assignment #1 posted
Sept. 8	log-space computation and circuits	Slides	Sections 4.3, 15.3, 16.1
Sept. 10	Uniform circuit families	Slides	Section 11.4
Sept. 15	Circuit-Value and Circuit-SAT	Slides	Sections 8.2
Sept. 17	Space complexity and circuit families	Slides	Sections 16.1	Assignment #1 due
Sept. 22	Circuit families and PSPACE	Slides	Chapter 19	Solution to Assignment #1 posted
Sept. 24	Parallel complexity theory	Slides	Sections 15.1-15.3
Sept. 29	The NC hierarchy	Slides	Section 15.3
Oct. 1	Advanced circuit complexity theory	Slides	R. Williams' paper
Oct. 6	The class coNP	Slides	Sections 10.1-10.2	Assignment #2 posted
Oct. 8	The polynomial-time hierarchy	Slides	Chapter 17
Oct. 13	Immerman-Szelepcsenyi Theorem	Slides	Chapter 16, Lecture Notes 1
Oct. 15	Probabilistic complexity theory	Slides	Sections 11.1-11.2
Oct. 20	Relationships in probabilistic classes	Slides	Section 11.2	Assignment #2 due
Oct. 22	The classes BPP and ZPP	Slides	Lecture Notes 2
Oct. 27	BBP is a subclass of P/poly	Slides	Lecture Notes 2	Assignment #3 posted
Oct. 29	Karp-Lipton Theorem	Slides	Lecture Notes 3	Solution to Assignment #2 posted
Nov. 3	Relationships in complexity classes	Slides	Lecture Notes 3
Nov. 5	Relativized complexity	Slides	Lecture Notes 4	Project proposal due
Nov. 10	Approximation algorithms	Slides	Section 13.1	Assignment #3 due
Nov. 12	Ratio of approximation algorithms	Slides	Section 13.1
Nov. 17	The Maximum Satisfiability Problem	Slides	Lecture Notes 5
Nov. 19	The PCP Theorem	Slides	Sections 13.2, 13.3
Nov. 24	Course summary	Slides	O'Donnell's article on PCP Theorem	Solution to Assignment #3 posted

Assignments
(Assignments are due on the designated due dates at the beginning of the class)

Assignment	Due Date	Solution
Assignment #1	September 17	Solutions
Assignment #2	October 20	Solutions
Assignment #3	November 10	Solutions
Course Project	December 1	Instruction of submission