Topic outline

  • General

    This course will be conducted physically on campus. Contact sessions could not be participated virtually and will not be VDO recorded.

    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 - responsible professor 

    Ameet Gadekar - instructor

    Nidia Obscura Acosta - senior TA


    ALERT: We will likely need help with grading. If you have done many proof-based courses and are interested in doing part-time jobs as a grader, write us an email.

    WARNING: This is a one-period course. About 20 hours per week are expected from your time. 

    FIRST MEETING: February 28, 2022.

    LEARNING ACTIVITIES:  All activities are conducted physically on campus (except for (1)).

    1) INTRODUCTORY VDOs. Watch before attending any other activities on that topic.

    2) LECTURES: Monday & Wednesday 10:15 to noon, Room T3

    3) RECITATION: Thursday 14:15-16:00, Room T3 

    4) COLLABORATIVE EXERCISE SESSIONS: Thursday 16:15, Room T4


    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 (12 points), practice problems (10 points), and midterm&final take-home problem sets (30 & 30 points plus bonuses). 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 you miss today, it is possible to try next time)