CSE4530  Computational Complexity Theory D, 01.03.202116.04.2021
This course space end date is set to 16.04.2021 Search Courses: CSE4530
Topic outline

Computational complexity theory is a field that systematically studies the intrinsic complexity of computational problems, i.e. given a computational problem, what can be achieved using limited computational resources (such as space and time)? Various notions of the "hardness" of computational problems will be formalized and mathematically studied in this course. Unlike algorithmic subjects, the goal of computational complexity is NOT to argue about a specific problem but rather the whole class of algorithmic problems that share the same intrinsic properties. This means the course will necessarily involve a large amount of mathematical abstraction.
This course will be online. Subject to Aalto rules, small tutorial sessions may be conducted physically if there are sufficient demands. In any case, there will be an option to do online tutorial sessions.
TEACHING STAFF:
Parinya Chalermsook  responsible professor
Ameet Gadekar  teaching assistant
Nidia Obscura Acosta  teaching assistant
Sorrachai Yingchareonthawornchai  teaching assistant
WARNING: This is a oneperiod course. About 20 hours per week are expected from your time.
FIRST MEETING: March 1, 2021
OVERVIEW LECTURES: Monday 11:00 12:00 (exactly 1 hour). The instructor will give a short overview of the materials in each week. This is supposed to help you work through the technical reading, but the lectures will be far from being comprehensive. The VDOs of these sessions will be posted, so do not worry if you miss them.
There will also be several companion short VDOs (510 minutes per VDO) that would help you work on the DOexercises (i.e. exercises for the sake of doing  no submission). You can only watch these VDOs AFTER you have attempted the quiz.
OTHER CONTACT SESSIONS: These sessions will NOT be VDO recorded. Students are expected to make an effort to attend them.
 RECITATION. Wednesday 10:15  11:45. A teaching assistant will present some material or exercise solutions that would help strengthen conceptual understanding. At the end of each session, we will take up to 4 volunteers who would summarize the discussion. Each volunteer will receive 5 bonus points. Each student may only volunteer at most once.
 SMALL GROUP EXERCISES. Wednesday 14:00  16:00. We work on selected problems in the exercise sheet. These sessions are run by two TAs. Bonus points will be rewarded for attendance & participation in the activities. The structure of these sessions is as follows.
 Spend 15 minutes as a big group to clarify the questions.
 We split students into small groups (35 students each) in a semirandom manner [to be made precise]. The small groups discuss for 1 hour. TAs may walk into your sessions to give hints (or you may request for their presence).
 In the second part, reconvene as a large group. Each group gets to say something for 5 minutes giving the executive summary of the discussion: ranking of the problem difficulty, which problems can you solve, which one is way too difficult.
 Finally, during the remaining time, you can ask TAs for hints.
You get 4 points for each session participation. If you are more than 15 minutes late, you will not be admitted into the sessions.
 Q&A SESSIONS. Thursday 16:15. 18:00. Two TAs will be avaiable in the session. There are
twothree purposes of these sessions. (1) For students to ask questions of your choice (e.g. about materials or about exercises), and (2) for students to claim points in the bonus exercises (to be handed over the semester) by trying to convince a TA in 10 minutes, and (3) Parinya will be there at least 0.5  1 hour every week, in case you need a chat.
PREREQUISITES : Mathematical maturity and knowledge in algorithms. In particular, students should be familiar with the following course content. CSC2160: Theory of computation; CSE3190: Principles of Algorithmic Techniques; MSA0402 Foundations of Discrete Mathematics. Without the proper backgrounds, it is still however possible to understand this course but would require much more time.INTENDED LEARNING OUTCOME:
Students will be able to formalize various aspects of computations (deterministic, randomized, nondeterministic, nonuniform) and their resource requirements (time, space, circuit gates). Moreover, abilities to make mathematical reasoning about such concepts will be expected.
GRADING:
There will be no inclass exam. Your grades will be determined by online quizzes (30 points), discussion sessions (24 points), and takehome problem sets (60+ points). The total number of available points will likely be a lot more than 100. If you get the score of at least 80, it will guarantee Grade 5. The score of at least 40 in total would guarantee to pass the course.
Here is some more detail.
 Online Quizzes. There will be online quizzes posted on MyCourses. These are multiplechoice questions. Each quiz set carries 5 points. The quizzes are due on Tuesday 23:59 (before midnight).
 Exercise sheets. There will be 6 rounds of exercises. Each round carries 10 points and is due on Sunday 23:59 (before midnight). Your submissions will be graded by each Wednesday. There are two types of exercises: (i) the recitation exercises (DO exercises) and (ii) 4 takehome questions that you need to work on and submit your written solutions.
 Discussion sessions. There will be group activities (e.g. problem solving or highlevel discussions in small groups). Attendance gives you points. Bonus point opportunities will be offered in these sessions.
LATE POLICIES: Since the total number of available points is really large (120+), no late submission will be accepted. (i.e. if you miss today, try the next chance)
LEARNING GUIDELINES:
Here is an example of a good study plan. The abundant total number of points (120 or so) should make it possible to have a oneweek chillout (i.e. doing nothing for one week, you would miss around 20 points).
Plan your life in a way that works best for you :) Monday: Attend the Monday's overview session. Read the lecture notes.
 Tuesday: Read the lecture notes. Submit the quizzes. Work on the DOexercises & watch companion VDOs.
 Wednesday: Attend recitation & group exercise sessions.
 Thursday: Work on the exercise sheet. Ask the TAs in the Q&A session if something is not clear or you need a hint.
 Friday: Work on the exercise sheet.
 Saturday & Sunday: Optional, in case you cannot stop enjoying the exercises :) Submit the solutions before midnight on Sunday.
LIST OF TOPICS
We will have 6 weeks of activities. Each week covers the following content.
 Week 1: Course Overview and Complexity Classes  Define Turing machine, complexity classes in particular P and NP.
 Week 2: NPcompleteness and Diagonalization techniques  The existence of completeness problems for NP. The use of diagonalization in general and in complexity.
 Week 3: Space complexity  Completeness, Savitch's theorem, and NL= coNL.
 Week 4: Polynomial Hierarchies and Circuit Complexity  PH and its collapse. Complete problems for PH. Circuits. KarpLipton theorem.
 Week 5: Probabilistic Computation and Counting  Probabilistic complexity classes. Relations to other classes. ValiantVazirani theorem. Approximate counting in \( \textbf{BPP}^{\textbf{NP}} \).
 Week 6: Optimization, Codes, and PCPs  Equivalence between hardness of approximation and proof checking. Hadamard codes and errorcorrecting properties. Exponentialsized PCPs.
 RECITATION. Wednesday 10:15  11:45. A teaching assistant will present some material or exercise solutions that would help strengthen conceptual understanding. At the end of each session, we will take up to 4 volunteers who would summarize the discussion. Each volunteer will receive 5 bonus points. Each student may only volunteer at most once.