### CS-E4530 - Computational Complexity Theory D, 01.03.2021-16.04.2021

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: 01.03.2021 - 16.04.2021

Teacher in charge (valid 01.08.2020-31.07.2022): Parinya Chalermsook

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

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

CEFR level (applies in this implementation):

Language of instruction and studies (valid 01.08.2020-31.07.2022):

Teaching language: English

Languages of study attainment: English

##### Content
• Valid 01.08.2020-31.07.2022:

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.

• Applies in this implementation:

In 2021 iteration of the course, we cover the following topics:

• Turing machines
• NP-completeness
• Diagonalization
• Space Complexity
• Polynomial Hierarchies
• Circuits
• Probabilistic Complexity
• Counting Complexity
• Optimization problems.
• Probabilistically checkable proofs and Walsh-Hadamard Codes.

##### Assessment Methods and Criteria
• Valid 01.08.2020-31.07.2022:

Exams and exercises.

• Applies in this implementation:

We do not have exams in 2021 iteration. Instead, we have:

• Written assignments (60 points)
• Collaborative exercise sessions (24 points)
• Online quizzes (30 points)

Our course focuses on mathematical reasoning.

• Applies in this implementation:

The same set of activities repeat each week. We expect each week to consume around 20-24 hours of the student's time. This can be broken down roughly as follows.

• Monday: 4 hours for watching vdo lectures and studying lecture notes.
• Tuesday: 4 hours for studying lecture notes and the quizzes.
• Wednesday: 4 hours for attending sessions.
• Thursday: 4 hours for independent study and/or Q&A sessions.
• Friday: 4 hours for finalizing the written assignment.

Note that this is the workload estimate for those who have done necessarily backgrounds for the course. If you do not have the right background, this workload could be higher.

#### DETAILS

##### Study Material
• Valid 01.08.2020-31.07.2022:

Lecture slides and exercises.

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