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, ASSESSMENT AND WORKLOAD
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.
Workload
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.
C. Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
Applies in this implementation:
There will be lecture notes by the teaching staff.
Prerequisites
Valid 01.08.2020-31.07.2022:
Automata and formal languages. Deterministic and nondeterministic Turing machines. Decidable and undecidable problems (e.g. CS-C2150 Theoretical Computer Science, CS-C2160 Theory of Computation). Basics of discrete mathematics.
- Teacher: Chalermsook Parinya
- Teacher: Gadekar Ameet
- Teacher: Obscura Acosta Nidia
- Teacher: Yingchareonthawornchai Sorrachai