Topic outline

  • General

    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.  

    TEACHING STAFF:

    Parinya Chalermsook

    Ameet Gadekar

    Nidia Obscura Acosta

    CHAT CHANNEL:

    https://join.slack.com/t/aalto-znb1168/shared_invite/zt-1myaouw9e-auI0Cisd9M0KAGIGSNhXnA 

    FIRST MEETING: January 9, 2023.

    LEARNING ACTIVITIES:  You are strongly encouraged to attend these sessions if you find it difficult to study the materials independently.

    1) OVERVIEW LECTURES:
    We will give an overview and intuitive explanation of the material. Details will be omitted.

    2) DETAILED TUTORIAL:
    We will go over some selected detailed explanation of the materials. The presentation will be scientifically driven. We will show you how we would learn the content or solve the exercises (instead of simply presenting the fully baked products).

    Events (1) and (2) will happen on Monday 14:15 to 16:00, Room T6 or Wednesday 10:15-12:00, Room T3.

    3) COLLABORATIVE EXERCISE SESSIONS: Thursday 16:15, Room T5
    Students are divided into small groups (3-4) and work on the exercises together. Points will be awarded for participating in the discussions.

    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 exam. Your grades will be determined by online quizzes (20 points), discussion sessions (20 points), practice problems (20 points), and midterm&final take-home problem sets (25& 25 points plus BONUS). 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.

    LATE POLICIES: Since the total number of available points is really large (120+), no late submission will be accepted, i.e., if today is bad, try tomorrow :)