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 necessarily 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 fair amount of mathematical abstraction.  

    TEACHING STAFF:

    Parinya Chalermsook (responsible professor & co-instructor) 

    Nidia Obscura Acosta (co-instructor) 

    CHAT CHANNEL:

    TBA 

    FIRST MEETING: January 15, 2024.

    LEARNING ACTIVITIES:  You are strongly encouraged to attend these sessions if you find it difficult to study the materials independently. The sessions will be interactive and discussion-oriented.

    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. 

    3) EXERCISE HELP SESSIONS:
    You will get opportunities to ask for hints and clarifications about exercises. 

    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 (32 points) and 4 written exercises (>100 points). The due dates of these exercises will be: 

    • Feb 4, 2024 (28 points) 
    • Mar 3, 2024 (28 points) 
    • Mar 24, 2024 (28 points) 
    • Apr 21, 2024 (28 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.

    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 :)