CS 6810: Theory of Computing (Fall 2021)
Instructor: Eshan Chattopadhyay
(Office: Gates Hall 319), email
TA: Jyun-Jie Liao
Class schedule: Tuesdays and Thursdays, 11:25am-12:40pm
Location:
Statler Hall 351
Instructor Office hours:Thursdays, 3-4pm (Gates Hall 319), or by appointment.
TA Office hours:Mondays, 1-2pm (Rhodes 406).
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.
Grading
Performance in this course will be evaluated as follows:
- Homeworks: 30%. There will be 3 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: 25%. 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 28.
You may work in groups (up to 2 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.
- Lecture 1: Introduction, Turing Machines. Reading: Chapter 1 in A-B book. notes
- Lecture 2: Universal TM, Non-deterministic TM, NP. Reading: Chapter 2.1, 2.2, 2.3 in A-B book. notes
- Lecture 3: NP-completeness, Search vs Decision Problems, Time Hierarchy theorem. Chapters 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: Space Complexity I: Basics, Savitch's Theorem. Chapter 4.1, 4.2, 4.3.1 in A-B book.notes
- Lecture 7: Space Complexity II: More on PSPACE, L, NL. Chapter 4.3 in A-B book. notes
- Lecture 8: NL=coNL, introduction to Boolean Circuits. Chapter 4.4, 6.1 in A-B book. notes
- Lecture 9: Boolean Circuits: upper bounds, lower bounds. Turing Machines with advice. notes
- Lecture 10: Polynomial Hierarchy I: Basics, Alternating Turing Machines. Chapter 5.1, 5.2, 5.3 in A-B book notes
- Lecture 11: Polynomial Hierarchy II: Oracle definitions, Karp-Lipton Theorem. Chapter 5.5, 6.2 in A-B book. notes
- Lecture 12: Randomized Computation I: Probabilistic Turing Machines, related complexity classes, examples of randomized algorithms. Chapter 7.1, 7.2,7.3 in A-B book. notes
- Lecture 13: Randomized Computation II: Error reduction techniques, BPP in P/poly. Chapter 7.5, 7.6, in A-B book.notes
- Lecture 14: Randomized Computation III: BPP in PH, Randomness in logspace. Chapter 7.7, 7.10 in A-B book. notes
- Lecture 15: UPATH is in RL, Introduction to Interactive Proofs. Chapter 7.9, 8.1 in A-B book. (Notes in preparation)
- Lecture 16: Interactive Proofs II: GNI in IP, AM. Chapter 8.2, 8.3, 8.4 in A-B book. notes
- Lecture 17: More on Arthur-Merlin protocols. Chapter 8.4 in A-B book.notes
- Lecture 18: co-NP is in IP (hints towards proving IP=PSPACE). Chapter 8.4 in A-B book. notes
- Lecture 19: Zero-Knowledge Proofs. notes
- Lecture 20: PCPs and hardness of approximation. Chapter 18.1, 18.2 in A-B book. notes
- Lecture 21, 22: On the connection between PCPs and hardness of approximation, BLR linearity test. Chapter 18.2, 18.4.1 in A-B book (Scribe notes will contain proof of the BLR test that does not rely on Fourier analysis.). notes
- Lecture 23: PARITY is not in AC0 (based on the the Razborov-Smolensky proof technique). Guest Lecture by Jyun-Jie Liao. notes
- Lecture 24: NP is in PCP(poly(n),O(1)). notes
- Lecture 25: Computation with imperfect randomness. notes
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.