Instructor: Xue Chen
Email: xuechen@gmu.edu
Location: Online (Zoom Link available on Blackboard)
Class Time: Tuesday 4:30-7:10 pm
Office Hour: Monday/Friday 4:30 - 6:00 pm and Tuesday after the class, or by appointment.
Course homepage: https://sites.google.com/view/xuechencs/home/theoryofcomp2020fall
TA: Yong Yang (email: yyang29@masonlive.gmu.edu) Office Hour: Monday 2 -3 pm (Zoom link on Blackboard)
This graduate course is an introduction to computational complexity. Computational complexity studies the limits and capabilities of various computation models, as well as tradeoffs between different computational resources. The goal for the class is to be broad rather than deep. Our plan is to touch upon the following areas. This is a tentative list of topics that might be covered in the class; we will select material adaptively based on the background, interests, and rate of progress of the students.
(1) Automata and Language Theory (2 weeks)
Finite automata, regular expressions, push-down automata, context free grammars, pumping lemmas.
(2) Computability Theory (2 weeks)
Turing machines, decidability, halting problem.
(3) Complexity Theory (8 weeks)
P and NP, polynomial-time reductions, randomized computation BPP, circuit complexity P/poly, polynomial hierarchy, space complexity, PSPACE and proof systems.
(4) Connections between complexity theory and other areas (1 week depending on the progress)
Hardness vs Randomness: Nisan's PRG and P vs BPP, average case complexity and computation learning theory.
The course is very proof heavy. Except CS 583, I will assume some mathematical sophistication (familiar with proofs by induction and contradiction, discrete math, basic probability theory and combinatorics counting).
40% Homework, 30% midterm exam and 30% final exam.
The two exams, including the final, each cover about a half of the semester. So the final is not cumulative. All testing is open book, but you may find it will be helpful to prepare 2-3 sheets of notes.
Both exams will be held online. The midterm exam will be on Tuesday, October 6 from 4:30 to 7:00 pm. The date of the final exam, as specified by the university, is Tuesday, Dec 15 from 4:30 to 7:00 pm. I will not offer any makeup exams, so students should plan accordingly.
Most weeks a problem set will be assigned.
I strongly recommend students to type their answers. Here is one LaTex template file and a LaTex reference from the previous course (Thanks Dov!).
There is no required textbook.
But it will be good to have a copy of the textbook Introduction to the Theory of Computation by Sipser, which is very useful through the whole course. Another good reference is the notes from CS 600 in 2018 by Prof. Dov Gordon.
The textbook Computational Complexity: A Modern Approach by Arora and Barak is helpful for further reading, and the preliminary version is freely available on the web.
All coursework is to be done independently WITHOUT reading any published literature or websites besides the class text and material in blackboard. Plagiarizing the homework will be penalized by maximum negative credit and cheating on the exam will earn you an F in the course. See the GMU Honor Code System and Policies at George Mason University Honor Code.
Collaboration policy: You are encouraged to discuss the material BEFORE you write the homework. But You must write your solutions independently. You should also state the names of those you collaborated with on the first page of your submission. Homework that appear overly similar will be considered to violate the honor code.
No late homework will be accepted.
If you have a learning or physical difference that may affect your academic work, you will need to furnish appropriate documentation to the Disability Resource Center. If you qualify for accommodation, the DRC staff will give you a form detailing appropriate accommodations for your instructor. In addition to providing your professors with the appropriate form, please take the initiative to discuss accommodation with them at the beginning of the semester and as needed during the term. Because of the range of learning differences, faculty members need to learn from you the most effective ways to assist you. If you have contacted the Disability Resource Center and are waiting to hear from a counselor, please tell me.