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 one-period 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 (5-10 minutes per VDO) that would help you work on the DO-exercises (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 (3-5 students each) in a semi-random 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 two three 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. CS-C2160: Theory of computation; CS-E3190: Principles of Algorithmic Techniques; MS-A0402 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, non-uniform) 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 in-class exam. Your grades will be determined by online quizzes (30 points)discussion sessions (24 points), and take-home 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 multiple-choice 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 take-home questions that you need to work on and submit your written solutions. 

    • Discussion sessions. There will be group activities (e.g. problem solving or high-level 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 one-week chill-out (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 DO-exercises & 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: NP-completeness 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. Karp-Lipton theorem. 
    • Week 5: Probabilistic Computation and Counting - Probabilistic complexity classes. Relations to other classes. Valiant-Vazirani 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 error-correcting properties. Exponential-sized PCPs.