CS 6810: Theory of Computing (Fall 2023)
Instructor: Eshan Chattopadhyay
(Office: Gates Hall 319), email
TA: Mohit Gurumukhani, email
Class schedule: Tuesdays and Thursdays, 1:25pm-2:40pm
Location:
Hollister Hall 306
Instructor Office hours:Thursdays, 3-4pm (Gates Hall 319), or by appointment.
TA Office hours: M 1 pm - 2 pm (Rhodes 400)
Logistics: Syllabus (includes a tentative list of topics). We will use Canvas for HW submissions, and Ed for announcements & discussions.
About this course: Computational complexity theory is devoted to understanding the limitations of efficient computation (with respect to computational resources such as time, space and randomness). This course will be a graduate level introduction to various aspects of complexity theory.
A tentative list of topics:
- Time and space complexity
- Non-determinism and Alternation
- Randomness and derandomization
- Circuit Lower bounds
- Interactive Proofs
- Probabilistically Checkable Proofs and Hardness of Approximation
Prerequisites: Any of CS 4810, CS 4820 or CS 4814; or permission of instructor. In general, some mathematical maturity is expected. Familiarity with basic notions of algebra (such as finite fields, basics of vector spaces, polynomials), linear algebra, and discrete probability will come in handy.
Resources
While we will not follow a single book for this course, the following are useful references.
- Computational Complexity: A Modern
Approach by Sanjeev Arora and Boaz Barak.
You can find a draft of the book here.
- Computational Complexity: A Conceptual Perspective by Oded Goldreich.
You can find a draft of the book here.
- Mathematics and Computation by Avi Wigderson. You can find a draft of the book
here.
Link to a previous iteration of this course (taught in Fall 2021).
Grading
Performance in this course will be evaluated as follows:
- Homeworks: 40%. There will be 4 homeworks spread evenly accross the semester.
Solving problems will require original thinking, and it will be a good idea to start early.
You will be required to use LaTeX to typeset your solutions.
- Scribe notes: 15%. Students are required to scribe lecture notes.
You will be required to send in an initial draft of the scribed notes by 48 hours after the lecture. Here is template
that you can use.
- Final project: 40%. You are expected to pick a topic and send a project proposal by October 20 (Friday).
You may work in groups (up to 3 members).
- Class participation: 5%.
Homework collaboration policy: We encourage you to discuss with your peers in the course to brainstorm ideas for how to get through homework.
However, your solution must be written up completely on your own; you are not allowed to share digital or written notes or images of your work in any form with each other.
Your work must also include acknowledgements of all students with whom you collaborated. Additionally, you may make use of published material, provided that you acknowledge all sources used.
Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff.
I will include some reading references from the A-B book. Please also look at relevant sections of the other reference books.
(to be updated as semester progresses)
- Lecture 1: Introduction, Turing Machines. Reading: Chapter 1 in A-B book.
- Lecture 2: Universal TM, Non-deterministic TM, NP. Reading: Chapter 2.1, 2.2, 2.3 in A-B book. notes
- Lecture 3: NP, NP-completeness, Time Hierarchy Theorem. Chapter 2.4-7, 3.1 in A-B book. notes
- Lecture 4: Ladner's theorem. Chapter 3.4 in A-B book. notes
- Lecture 5: Oracle Turing Machines. Chapter 3.5 in A-B book. notes
- Lecture 6: Limits of diagonalization, Introduction to Space Complexity. Chapter 3.5, 4.1 and 4.2 in A-B book. notes
- Lecture 7: Savitch's theorem, NL-completeness. Chapter 4.3, 4.4 in the A-B book. notes
- Lecture 8: NL = co NL, PSPACE Completeness. Chapter 4.3, 4.4 in the A-B book. notes
- Lecture 9: Boolean Circuits I: Introduction. Chapter 6.1, 6.3 in the A-B book. notes
- Lecture 10: Boolean Circuits II: Turing Machines with advice, towards AC0 lower bounds. Chapter 6.1, 6.5, 13.2 in the A-B book. notes
- Lecture 11: Low-degree approximators for AC0. Chapter 13.2 in A-B book. notes
- Lecture 12: AC0 lower bounds against MAJORITY. Chapter 13.2 in A-B book. notes
- Lecture 13, 14, 15: AC0 lower via Random Restrictions. Chapter 13.1 in A-B book. notes (See also notes by Paul Beame.)
- Lecture 16: The Polynomial Hierarchy: Introduction. Chapter 5.1, 5.2 in A-B book. notes
- Lecture 17: The Polynomial Hierarchy: Alternating Turing Machines, Oracle definitions, Karp-Lipton Theorem. Chapter 5.3, 5.5, 6.2 in A-B book. notes
- Lecture 18: Probabilistic Complexity Classes, Error reduction in randomized algorithms. Chapter 7.1,7.2,7.3 in A-B book. notes
- Lecture 19: BPP in P/Poly, BPP in PH. Chapter 7.5, 7.6, 7.7 in A-B book. notes
- Lecture 20: Hardness vs Randomness: Introduction. Chapter 16.1, 16.2 in A-B book. notes
- Lecture 21: Hardness vs Randomness: Nisan-Wigderson Generator. Chapter 16.2 in A-B book. notes
- Lecture 22: Introduction to Interactive Proofs. Chapter 8.1, 8.2, 8.3 in A-B book. notes
- Lecture 23: GNI in AM, Perfect Completeness of MA. Chatper 8.4 in A-B book. notes
- Lecture 24: More on Arthur-Merlin Protocols, coNP in IP. Chapter 8.4 in A-B book. notes
Selected Course Projects
Undirected connectivity is in logspace (report). Sanjit Basker, Omkar Bhalerao, Esther Wang.
On basing one-way functions on NP not in BPP via hardness of meta-complexity (report). Yanyi Liu.
A Brief Introduction to Parameterized Complexity (report). Ishan Bansal, Haripriya Pulyassary.
Computational Complexity of Matrix Multiplication (report). Andy He, Evan Williams.
Constraint Satisfaction Problems (report). Ellie Fassman, Jiho Cha, Yunya Zhao.
Computational Complexity in Economics and Bounded Rationality (report). Daniel Brous, Tenghao Li, Ruqing Xu.
Survey of Differential Privacy (report). James Zhang, Owen Oertell and Stephanie Ma.
Inclusiveness
You should expect and demand to be treated by your classmates and the course staff with respect.
You belong here, and we are here to help you learn and enjoy this course.
If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the instructors know so that the issue can be addressed.
We are personally committed to this, and subscribe to the
Computer Science Department's Values of Inclusion.