Instructor: Xue Chen

Email: xue.chen1@northwestern.edu

Location: Tech LG68

Time: TuTh 10:00-11:20 am

Office Hours: MW 1-2pm at Mudd 3217

Description: This graduate course is an introduction to computational complexity. Computational complexity studies the limits and capabilities of efficient computation, as well as tradeoffs between different computational resources. Apart from the central P versus NP question, we explore a variety of other fascinating topics, including the connection between learning theory and average-case complexity, hardness versus randomness (the BPP versus P question), and the surprising equivalence of probabilistically checkable proofs (PCPs) and the hardness of approximating certain optimization problems.

The tentative outline for the course is as follows:

• Introduction to basic complexity classes: P, BPP and NP.
• Adleman's theorem and introduction to circuits P/poly.
• AC0 circuits and Parity.
• Hastad's switching Lemma.
• Hardness vs Randomness: Nisan's PRG and P vs BPP.
• Fourier transform and LMN learning.
• Space Complexity.
• PCP and hardness of approximation.

Textbook and Other readings: There is no required textbook.

Two good books for references are Arora and Barak, Computational Complexity: A Modern Approach and Oded Goldreich, Computational Complexity: A conceptual Perspective.

Lecture notes for references: Luca Trevisan.

Evaluation: There will be 3-4 homework problem sets.

Collaboration policy: You are encouraged to collaborate on homework. However, you must write up your own solutions. You should also state the names of those you collaborated with on the first page of your submission.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it.

Submission policy: Homeworks are due at the beginning of class. No late homeworks will be accepted.

Canvas: We will use canvas to post homework and grades.

Grading: 20% Participation, 40% Homework, 40% final projection/presentation.

Additional material: Karger's algorithm and Impagliazzo's five worlds.