CS-E4530 - Computational Complexity Theory D, Lecture, 8.1.2024-11.4.2024

Guest access
Please note! Course description is confirmed for two academic years, which means that in general, e.g. Learning outcomes, assessment methods and key content stays unchanged. However, via course syllabus, it is possible to specify or change the course execution in each realization of the course, such as how the contact sessions are organized, assessment methods weighted or materials used.

LEARNING OUTCOMES

Once you have taken the course, you master the central concepts of computational complexity theory and are able to use these concepts to analyse the complexity of computational problems. You can formulate a concrete real-world computational task as a formal computational problem and formally reason about its computational complexity in comparison with well-known problems and complexity classes. You can use reductions and other complexity-theoretic concepts to identify which algorithmic tools such as randomisation, approximation, parameterisation and parallelism can and cannot help with the efficient solution of a given problem.

Credits: 5

Schedule: 08.01.2024 - 11.04.2024

Teacher in charge (valid for whole curriculum period):

Teacher in charge (applies in this implementation): Parinya Chalermsook

Contact information for the course (applies in this implementation):

CEFR level (valid for whole curriculum period):

Language of instruction and studies (applies in this implementation):

Teaching language: English. Languages of study attainment: English

CONTENT, ASSESSMENT AND WORKLOAD

Content

  • valid for whole curriculum period:

    Basic concepts of complexity theory: models of computation, complexity measures including time and space, reductions, complexity classes and completeness. Complexity classes: P, NP and coNP; PSPACE, LOGSPACE, EXPTIME. Advanced topics such as the polynomial hierarchy, approximation, randomised computation, circuits and parallel computation, fine-grained complexity, and relativisations.

Assessment Methods and Criteria

  • valid for whole curriculum period:

    Exams and exercises.

DETAILS

Study Material

  • valid for whole curriculum period:

    Lecture slides and exercises.

    S. Arora and B. Barak: Computational Complexity A Modern Approach, Cambridge U.P. 2009.

    C. Papadimitriou: Computational Complexity, Addison-Wesley, 1994. 

Substitutes for Courses
Prerequisites

FURTHER INFORMATION

Further Information

  • valid for whole curriculum period:

    Teaching Language : English

    Teaching Period : 2022-2023 Spring IV - V
    2023-2024 Spring IV - V

    Enrollment :

    Registration for Courses: In the academic year 2021-2022, registration for courses will take place on Sisu (sisu.aalto.fi) instead of WebOodi.

Rules of Conduct - Students´ Rights and Responsibilities (in force from 1 August 2020)

Aalto University Code of Academic Integrity and Handling Violations Thereof